Размещено на http://www.allbest.ru/

КУРСОВА РОБОТА

з інформатики

на тему: Розфарбування графів як математична модель прикладних задач

2015 рік

Зміст

• Вступ
• Розділ 1. Задача розфарбування графів: постановка задачі
• 1.1 Історія виникнення задачі
• 1.2 Деякі відомості з теорії графів
• 1.3 Математична модель задачі
• 2. Задача розфарбування графів як типовий приклад задачі np класу
• 2.1 Алгоритмічна складність задачі
• 2.2 Методи отримання точних розв'язків задачі розфарбування графів
• 2.2.1 Алгоритм мурашиної колонії для розфарбування графів
• 2.2.2 Алгоритм розфарбування графу методом неявного перебору
• 3. Комп'ютерна реалізація розв'язку задачі розфарбування графів
• 3.1 Аналіз типових задач та існуючих програмних продуктів
• 3.2 Опис програмного продукту
• 3.3 Машинна реалізація продукту
• Висновки
• Список використаних джерел
• Додатки

Вступ

У даній курсовій роботі розглядаються прикладні задачі, які зводяться в теорії графів до оптимального розфарбування планарних графів та знаходження їх хроматичного числа.

Метою роботи є систематизувати та поглибити знання з дискретної математики, теорії алгоритмів, зокрема застосування теорії графів у дослідженні прикладних задач, пов'язаних із розфарбуванням графів; вивчити можливості інформаційних технологій у полегшенні процесу цього дослідження.

Для досягнення поставленої мети потрібно:

– проаналізувати та систематизувати теоретичні та практичні досягнення в дослідженні задачі розфарбування графів;

– дослідити типи прикладних задач, що зводяться до задачі розфарбування графів та існуючи методи їх розв'язання;

– проаналізувати можливості автоматизації такого роду задач.

Об'єкт дослідження - теорія графів та її застосування у дослідженні прикладних задач.

Предмет дослідження - методи розв'язання задач NP класу на прикладі задачі розфарбування графів.

Курсова робота містить Вступ, основну частину поділену на 3 розділи, Висновки, список використаних джерел та Додатки. Перший розділ задача розфарбування графів містить: історію виникнення задачі, деякі відомості з теорії графів та математичну модель задачі.

Другий розділ має назву: задача розфарбування графів, як типовий приклад задачі NP класу, поділений на два підрозділи, останній з яких в свою чергу на два пункти, де більш детально описано алгоритмічну складність задачі та деякі найпоширеніші алгоритми розв'язування.

розфарбування граф програмний продукт

Третій розділ присвячений аналізу типових задач та існуючих програмних продуктів, машинну реалізацію конкретно наведеного прикладу.

Розділ 1. Задача розфарбування графів: постановка задачі

1.1 Історія виникнення задачі

В математиці теорема про чотири кольори говорить, що будь-яку розташовану на сфері карту можна розмалювати чотирма кольорами так, щоб дві любі області, які мають спільні зони границі, були розмальовані в різні кольори. Ця теорема була сформульована Ф. Гутрі в 1652 р. але довести її не могли довгий час.

Теорема Хівуда (полягає в тому, що будь-який граф можна розмалювати 5 різними кольорами) була доведена в 1890 р. Понизити верхню планку для хроматичного числа будь-якого планарного графа з 5 до 4, тобто підтвердити гіпотезу про чотири кольори не вдавалося майже 90 років. У 1969 р. задача була зведена до розгляду кінцевого, але досить великого числа конкретних випадків, пізніше їх число було скорочене до "всього лиш" 1482. Нарешті в 1976 р. К. Аппель і В. Хейкен за допомогою комп'ютерної програми розібрали всі ці конкретні випадки (витративши на це приблизно 2000 годин роботи потужного на той час комп'ютера). В результаті вони довели наступну теорему.

Теорема про чотири кольори.

Хроматичне число будь-якого планарного графа не перевищує 4.

Доведення цієї теорем стало першим випадком "комп'ютерного" вирішення важкої і давно суто математичної проблеми.

1.2 Деякі відомості з теорії графів

Граф - це сукупність об'єктів із зв'язками між ними.

Об'єкти - вершини графу, а зв'язки - дуги та ребра графу. Для різних областей використання видів графів можуть відрізнятися орієнтованістю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра. Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представленні графами. Наприклад, будову Вікіпедії можна змоделювати за допомого орієнтованого графа, в якому статті це вершини, а посилання на інші статті це дуги (орієнтовані ребра).

граф G - це впорядкована пара G: = (V,E), для якої виконуються наступні умови:

V - множина вершин або вузлів,

E - множина пар (у випадку неорієнтованого графу - невпорядкованих) вершин з V, які називають ребрами.

V (і так само E) зазвичай вважаються скінченними множинами. Велика кількість результатів, отриманих для скінченних графів, невірна (або інша) для нескінченних графів.

Планарний граф - граф, який може бути зображений на площині без перетину ребер.

Хроматичне число графа G - мінімальна кількість кольорів, в які можна розфарбувати вершини графа G, таким чином, щоб кінці будь-якого ребра мали різні кольори.

K-розфарбований граф - граф, хроматичне число якого не перевищує K. Тобто його вершини можна розфарбувати K різними кольорами так, що кінці будь-якого ребра будуть різних кольорів.

Хроматичний клас графа G - мінімальна кількість кольорів, в які можна розфарбувати ребра графа G так, щоб суміжні ребра були різних кольорів. Проблема ребрового розфарбовування довільного плоского кубічного графа без мостів трьома кольорами еквівалентна відомій Проблемі чотирьох фарб. Реброве розфарбовування визначає 1-факторизацію графа.

1.3 Математична модель задачі

Маємо граф G = (V, Е), де V - множина вершин, Е - множина ребер між ними. Необхідно призначити кожній вершині v ЎК V колір так, щоб загальна кількість кольорів була мінімальним.

Нехай:

· k - кількість кольорів, в які можна розфарбувати граф, причому k ? | V |. розумніше спочатку знайти будь-яку розмальовку за допомогою швидкої евристики з деяким числом кольорів col і покласти k = col, інакше необхідно покласти k =| V |.

· де =1 якщо вершині і призначений колір h , де =1, якщо колір h використаний в розфарбуванні

(1)

(2)

(3)

(4)

(5)

Функція (1) мінімізує кількість кольорів, використаних в розфарбуванні. Обмеження (2) вимагають, щоб кожній вершині був призначений рівно один колір. Обмеження (3) вимагають, щоб суміжним вершинам були призначені різні кольори. Нарешті, обмеження (4) і (5) задають можливі значення змінних - 0 або 1.

2. Задача розфарбування графів як типовий приклад задачі np класу

2.1 Алгоритмічна складність задачі

Складність алгоритмів вимірюється за необхідними ресурсами, в основному, це тривалість обчислень або необхідний обсяг пам'яті.

P-задача - це задача, для розв'язку якої існує поліноміальний алгоритм.

NP-задачею називається задача, яка може бути розв'язана на детермінованій машині Тьюринга за поліноміальний час O (n^m), де n - розмір задачі.

Якщо ж обмежитися детермінованими алгоритмами, то для вирішення будь-якої NP-задачі можна використовувати схему перебору з поверненням або подібні до неї перебірні схеми. Подібні алгоритми є експоненційними по своїй суті, і задачі, які вимагають застосування таких алгоритмів, відносяться до класу важко вирішуваних. Втім, це не виключає існування поліноміальних алгоритмів, і для ряду задач, які мають характер пошуку на дереві, такі алгоритми дійсно були знайдені. Позначимо через P клас P-задач, а через NP - клас NP-задач Ясно, що P - підмножина NP. Але питання про те, чи є це включення строгим, залишається відкритим.

Розфарбування графа мінімальною кількістю кольорів є комбінаторною задачею, яку відносять до класу NP-складних задач. Ця задача може бути сформульоване як рекурентне завдання розфарбування графа мінімальною кількістю кольорів. Спочатку задається певне число кольорів, (обґрунтоване з точки зору можливості розфарбування, тобто з відповідним хроматичним числом), а пізніше виконується алгоритм з подальшим зменшенням їх кількості.

Проблемами цієї задачі є швидкість знаходження розв'язку, а також точність розв'язання.

Результати тестувань відомого генетичного алгоритму на складних графах (700-1000) вершин показали, що використання Tabu Search (метаевристика - назва для стохастичних алгоритмів які використовують випадковий пошук, або пошук перебором, шлях вирішення цих задач) та певного кодування істотно покращують виконання генетичного алгоритму розфарбування графа.

До задач класу складності NP також належать:

· Розв'язність логічного виразу.;

· Три-кольорове розфарбування графу.;

· Побудова кліки з вершин на неорієнтованому графі;

· Покриття множин;

· Розбиття множин;

· Існування гамільтонового циклу на неорієнтованому графі;

· Задача пакування рюкзака;

· Розбиття на дві частини;

· Задача комівояжера.

Кажуть, що задача A поліноміальне зводиться до задачі B, якщо рішення задачі A може бути отримано з рішення задачі B за поліноміальний час.

Задача називається NP-складною, якщо до неї за поліноміальний час зводиться будь-яка NP - задача.

Якщо NP-складна задача є NP-задачею, така задача називається NP-повною. Поняття NP-повної задачі має велике значення. Якщо для будь-якої NP-повної задачі буде знайдений поліноміальний алгоритм, це означатиме, що поліноміальний алгоритм існує для будь-якої NP-задачі, і тоді виявиться, що P=NP. Але таких алгоритмів поки що знайдено не було, і шансів на їх знаходження залишається все менше і менше.

2.2 Методи отримання точних розв'язків задачі розфарбування графів

Для NP-повних задач не відомо кращого методу рішення, ніж повний перебір всіх можливих варіантів, і, на думку більшості математиків, малоймовірно, щоб кращий метод був колись знайдений. Оскільки такий повний пошук практично нездійсненний для великого числа міст, то евристичні методи використовуються для знаходження прийнятних, хоч і неоптимальних рішень.

2.2.1 Алгоритм мурашиної колонії для розфарбування графів

Цей алгоритм використовується для стійкого розфарбування і є NP-складною задаче комбінаторної оптимізації. Розв'язувати цю задачу краще за допомогою метаевристичних.

Даний алгоритм був запропонований М. Доріго у 1992 році. В ідеї алгоритму лежить здатність колонії мурах знаходити найкоротший шлях між мурашником та їжею. Кожна мураха залишає за собою слід секрету (феромонів) і, рухаючись в навколишньому середовищі, намагається дотримуватися стежок із секрету, що залишили інші мурахи. Чим більше мурах проходить цією дорогою, тим більше секретів залишається, тож імовірність що мураха вибере саме цей шлях значно зростає. Алгоритм уникає локальних мінімумів.

Стежини по яких рухаються мурахи можна представити у вигляді ребра графа, що має назву конструкційного. Кожне ребро має свою вагу - час проходження шляху. Мурахи повинні знайти найкоротший шлях між вершинами (мурашником та їжею). Розробка будь-якого алгоритму мурашиної колонії розпочинається з визначення будови конструкційного графу.

Суть полягає в тому, що вершина в графі буде обрана лише один раз, обхід вершин, забезпечує їх розфарбування, при цьому враховується вага ребер, тобто найкоротший шлях до вершини.

Алгоритм ефективно розв'язує задачі з графами до 50 вершин включно. На більших графах більш відоміші алгоритми показують кращий час виконання та якості. Подальші дослідження алгоритму передбачають оптимізацію знаходження ваги ребер і визначення оптимальних складових переходу мурахи до наступної вершини конструкційного графу.

2.2.2 Алгоритм розфарбування графу методом неявного перебору

Робота алгоритму поділяється на дві фази.

Під час першої будується початкова допустима розфарбування графа за наступним правилом: перша вершина фарбується в перший колір, а далі для кожної вершини вибирається мінімальний за номером колір, такий щоб ніяка із суміжних з даною раніше забарвлених вершин не мала цього кольору.

Під час другої фази, якщо це можливо, шукають покращення розфарбування, що використовує менше число кольорів. На першому кроці другої фази відшукується перша за номером вершина, пофарбована у колір, від якого ми хочемо позбутися. І з неї здійснюється так званий крок повернення, а саме - в множині вершин, суміжних з даною, з меншим, ніж у неї, номером знаходимо максимальну (вона була пофарбована пізніше за інших, нехай це x-а вершина) і намагаємося перефарбувати її в інший допустимий колір з номером більшим за її власний, але меншим за номер " зайвого " кольору. Якщо це вдається, то далі за правилом першої фази перефарбовуються наступні вершини з (х +1) - ої до кінця. Якщо жодна з них не потребують кольору, від якого ми позбавляємося, отже ми досягли оптимальніше розфарбування з меншою кількістю кольорів і зупиняємося або починаємо роботу по алгоритму з початку.

3. Комп'ютерна реалізація розв'язку задачі розфарбування графів

3.1 Аналіз типових задач та існуючих програмних продуктів

До задачі правильного розфарбування графів зводиться багато типових задач, наприклад:

Задача про розфарбування карти. Знайти оптимальне розфарбування (а отже і хроматичне число) планарного графа, що відповідає політичній карті світу.

Задача розподілу обладнання. Є деяка кількість робіт і механізмів для їх здійснення. Для виконання кожної роботи потрібно один і той самий час. При цьому жоден з механізмів не може бути зайнятий одночасно більше ніж в одній роботі. Потрібно розподілити механізми так, щоб загальний час виконання робіт було мінімально можливим.

Для перекладу цього завдання на мову теорії графів розглянемо граф G, вершинами якого є роботи, причому дві різні вершини суміжні тоді і тільки тоді, коли для виконання відповідних робіт потрібно хоча б один загальний механізм. При правильному розфарбовуванні цього графа вершини, розфарбовані одним і тим же кольором, відповідають роботам, які можна проводити одночасно. Тому завдання зводиться до знаходження оптимального розфарбування графа G. Розглянемо приклад. На підприємстві планується виконати 8 робіт ,,…,. Для виконання цих робіт необхідні механізми ,,…,. Використання механізмів для кожної з робіт визначається наступною таблицею:

Механізм	Робота
	+		+				+	+
		+		+
			+			+	+
	+	+		+	+
			+		+			+
					+	+		+

Жоден із механізмів не може бути використаний одночасно на двох роботах. Виконання кожної роботи займає 1 годину. Як розподілити механізми так, щоб сумарний час виконання всіх робіт був мінімальним і який цей час?

Рішення. Розглянемо граф G, вершинами якого є плановані роботи ,,…,, а ребра з'єднують роботи, в яких бере участь хоча б один загальний механізм (і які, з цієї причини, не можна проводити одночасно). Цей граф зображений на мал.2. Вершини ,,, породжують підграф графа G ізоморфний . Отже, .

Цифри в дужках на мал.3.1 вказують правильну розмальовку графа G в 4 кольори. Отже, . Таким чином, всі роботи можна виконати за 4 години. Для цього, відповідно до знайденого розфарбування графа G, треба в 1-у годину виконувати роботи і , у 2-й - роботи і , в 3-й - роботи і , в 4-й - роботи і .

Мал. 3.1

Задача призначення телевізійних каналів. Передавальні станції зображають вершинами графа. Якщо відстань між будь-якими двома станціями менша за одиницю, то відповідно вершини графа з'єднуються ребром. Граф розфарбовують зіставляючи різним кольорам вершин різні канали. Мінімальна кількість каналів відповідає розфарбуванню графа мінімальною кількістю кольорів.

Задача складання розкладу. Припустимо, що потрібно прочитати декілька лекцій у найкоротший термін. Кожна лекція окремо займає одну годину, але деякі лекції не можна читати одночасно (наприклад, якщо це робить один і той самий лектор, або лекції читаються одній та тій самій групі студентів). Побудуємо граф G, вершини якого взаємно однозначно відповідають лекціям, і дві вершини суміжні тоді й тільки тоді, коли відповідні лекції не можна читати одночасно. Очевидно, що будь-яке розфарбування цього графа задає можливий розклад: лекції, які відповідають вершинам одноколірного класу, читають одночасно. Навпаки, будь-який можливий розклад задає розфарбування графа G. Оптимальні розклади відповідають розфарбуванням мінімальною кількістю кольорів, а час, потрібний для читання всіх лекцій, дорівнює ч (G).

Перекладемо це завдання на мову графів. Побудуємо граф G, в якому вершини відповідають лекціям та дві різні вершини суміжні тоді і тільки тоді, коли відповідні лекції не можуть читатися одночасно. Очевидно, що будь-яке правильне розфарбування графа G визначає допустимий розклад (якщо при цьому розфарбовуванні використано k кольорів, то для всякого i = 1, 2,.,k вершини, розфарбовані i-м кольором, дають список лекцій, які треба читати на i-й парі). І навпаки, будь-який допустимий розклад визначає правильне розфарбування графа G. Таким чином, складання оптимального розкладу зводиться до знаходження оптимального розфарбування побудованого нами графа.

Розглянемо приклад завдання на складання розкладу. У студентських групах І-31 і І-32 треба провести заняття з алгебри, дискретної математики, математичного аналізу та історії України (по одному заняттю з кожному предмету). Заняття по кожному предмету проводяться з кожною групою окремо. Заняття з алгебри та з дискретної математики веде викладач X, з математичного аналізу - викладач Y, з історії України - викладач Z. Знайти мінімальне число пар, в які можна "укласти" всі заняття, і скласти відповідний розклад.

Рішення. Побудуємо граф з вершинами А1, А2, Д1, Д2, Ml, М2, І1 і І2 (літера відповідає предмету, а цифра - номеру групи). З'єднаємо ребрами вершини, що відповідають парам, які не можна проводити одночасно. Отримаємо граф, зображений на мал. 1 ліворуч. Вершини А1, А2, Д1 і Д2 цього графа породжують в цьому графі підграф, ізоморфний графу . Отже, хроматичне число нашого графа не менше 4. На мал. 3.2 праворуч вказана правильне розфарбування нашого графа в 4 кольори. Отже, хроматичне число графа дорівнює 4, тобто всі заняття можна провести за 4 пари. Відповідний розклад вказано в таблиці.

Мал. 3.2

	І-31	І-32
1 пара	Алгебра	Математичний аналіз
2 пара	Математичний аналіз	Алгебра
3 пара	Історія України	Дискретна математика
4 пара	Дискретна математика	Історія України

Задача комівояжера. Задача комівояжера є оптимізаційною задачею, що часто виникає на практиці. Вона може бути сформульована таким чином: на території держави X розташоване n міст, між деякими парами яких прокладені дороги (не обов'язково двонаправлені). Кожна з них характеризується числом - своєю довжиною. З одного міста в інше веде не більше однієї дороги. Бродячий торговець хоче обійти всі міста рівно по одному разу і повернутися у вихідний пункт (починати рух можна в довільному місті). Необхідно знайти мінімальну відстань, яку йому доведеться пройти, або з'ясувати, що шуканого маршруту не існує.

3.2 Опис програмного продукту

В 2 розділі було наведено декілька методів розфарбування графів. Так як метод перебору є не енергозатратним, саме цей метод будемо досліджувати та перевіряти. Використовуючи мову програмування Pascal була написана програма, що дозволяє знаходити оптимальне розфарбування вершин графа, котрий у свою чергу введений користувачем з клавіатури або ж використовувати граф що знаходиться у файлі.

Розглянемо алгоритм реалізації розфарбування графів

Procedure GetColor;

Begin

For i: =1 to n do

Color [i]: =1; {Усім кольорам присвоюємо 1}

For i: =2 to n do {основний цикл розфарбування графу, де `і' - це номер вершини, яку ми розфарбовуємо}

begin

j: =1; {розпочинаємо з першої вершини}

While (j<=Graph [i]. Count) and (Graph [i]. List [j] <i) do {ідемо повним перебором по вершинах всіх}

Begin

If Color [i] =Color [Graph [i]. List [j]] Then{якщо кольори вершин, що перевіряються співпадають}

Begin

Color [i]: =Color [i] +1; {міняємо колір}

j: =1; {знову перевіряємо з першої вершини}

end

Else{якщо кольори різні, то ми ідемо далі}

j: =j+1;

end;

end;

end;

3.3 Машинна реалізація продукту

Для демонстрації роботи програмного продукту розглянемо приклад.

Знайти хроматичне число графа, що зображений на Мал. 3.3.

Мал. 3.3.

Якщо ввести в програму заданий планарний граф (див. мал. 3) и виконати послідовність дій, передбачених програмою (див. Додатки А, В, С), на моніторі програма виведе нам наступний результат:

Мал. 3.4

Висновки

У даній курсовій роботі я займався дослідженням теми розфарбування графів як математичної моделі прикладних задач. Мною було опрацьовано та проаналізовано список джерел, які допомогли краще освоїти та зрозуміти тему.

Під час виконання роботи було виконано такі завдання:

· Проаналізовано та систематизовано теоретичні та практичні досягнення в дослідженні задачі розфарбування графів;

· Досліджено типи прикладних задач, що зводяться до задачі розфарбування графів, та існуючі методи їх розв'язування;

· Проаналізовано можливості автоматизації дослідження такого роду задач.

Список використаних джерел

1. Андрійчук В.І. Вступ до дискретної математики / В.І. Андрійчук, М.Я. Команницький, Ю.Б. Іщук. - Львів: Видавничий центр ЛНУ імені Івана Франка, 2003. - 254 с.

2. Бондаренко М.Ф. Комп'юретна дискретна математика / М.Ф. Бондаренко, Н.В. Білоус, А.Г. Руткас. - Харків: "Компанія СМІТ", 2004. - 480 с.

3. Капітонова М.Ф. Комп'ютерна дискретна математика. / Ю.В. Капітонова та ін. - Київ: Наукова думка, 2002. - 578 с.

4. Кук Д. Компьютерная математика. / Д. Кук, Г. Бейз. - М.: Наука, 1990. - 384 с.

5. Новиков Ф.А. Дискретная Математика для программистов / Ф.А. Новиков. - Питер: СПб, 2000. - 304 с.

6. Карнаух Т.О. Теорія графів у задачах / Т.О. Карнаух, А.Б. Ставровський: Навчальний посібник. - К.: ВПЦ "Київський університет", 2004. - 76 с.

7. Карнаух Т.О., Ставровський А.Б. Теорія графів у задачах 63 с.

8. Дискретна Математика:: Планарні графи. Розфарбування графів

[Електронний ресурс]: стаття - режим доступу: http://oim. asu. kpi.ua/files/DM/33_Planar_graphs. pdf

9. К. т. н., доцент Зорін Ю.М., студент Кучук О.М. Алгоритм мурашиної колонії для розв'язання задачі стійкого розфарбування графу.

[Електронний ресурс]: http://pmk. fpm. kpi.ua/arhive_2012/56_Kychyk. pdf

10. В.Ф. Прокопенков, Ю.Н. Кожин, О.Н. Малых, новый эвристический алгоритм раскраски графа [Електронний ресурс]: стаття - режим доступу:

http://www.kpi. kharkov.ua/archive/Науккова_періодика/vestnik/ - Загол. з титул. екрану. Мова: рос.

11. Задача коммивояжёра (поиск минимального гамильтонова цикла) [Електронний ресурс]: стаття - режим доступу: http://cybern.ru/zadacha-kommivoyazhyora.html. - Загол. з титул. екрану. Мова: рос. Останнє поновлення: 18.01.2012

12. Быстрый алгоритм для решения задачи о раскраске графа с использованием битовых операций http://itas2014. iitp.ru/pdf/1569941697. pdf - Загол. з титул. екрану. Мова: рос.

13. C.Д. Штовба, к. т. н., доц., О.М. Рудий Мурашині алгоритми оптимізіції [Електронний ресурс] www.serhiy-shtovba. narod.ru/doc/Visnyk_ANT. pdf

14. Задача комівояжера [Електронний ресурс]: стаття - режим доступу: http://uk. wikipedia.org/wiki/Задача_комівояжера. - Загол. з титул. екрану. Мова: укр. Останнє поновлення: 18.01.2015.

15. Клас складності NP [Електронний ресурс]: стаття - режим доступу:

http://uk. wikipedia.org/wiki/Клас_складності_NP. - Загол. з титул. екрану. Мова: укр. Останнє поновлення: 02.08.2013.

NP-повна задача [Електронний ресурс]: стаття - режим доступу: http://uk. wikipedia.org/wiki/NP-повна_задача. - Загол. з титул. екрану. Мова: укр. Останнє поновлення: 02.11.2014.

16. П.О. Кравець Ігрова модель хроматичного розфарбовування графів/ Крапець П.О. - Львів Національний університет "Львівська політехніка”, 2008.

Додатки

Додаток А

Задання графу матрицею суміжності:

Uses crt;

Type MS=array [1.10,1.10] of Integer;

Var

a: MS; n, i,j: Integer;

Begin

ClrScr;

Write ('Введіть кількість вершин: ');

Readln (n);

Writeln ('Введіть матрицю суміжності: ');

For i: =1 to n do

Begin

For j: =1 to n do

Begin

GoToXY (j*2, i+3);

Write (' ');

Read (a [i,j]);

end;

Writeln;

end;

Задання графу списком суміжності:

Type GList = array [1.10] of record

Count: Integer;

List: array [1.10] of Integer; end;

CList=array [1.10] of Byte;

Var Graph: GList; Color: Clist;

ДОДАТОК В

Програмна реалізація алгоритму розфарбування графів

Procedure GetColor;

Begin

For i: =1 to n do

Color [i]: =1;

For i: =2 to n do

begin

j: =1;

While (j<=Graph [i]. Count) and (Graph [i]. List [j] <i) do

Begin

If Color [i] =Color [Graph [i]. List [j]] Then

Begin

Color [i]: =Color [i] +1;

j: =1;

end

Else

j: =j+1;

end;

end;

end;

Додаток С

Повний код програми:

Program algorytmGraf;

Uses crt;

Type GList=array [1.10] of record

Count: Integer;

List: array [1.10] of Byte;

end;

CList=array [1.10] of Byte;

Var Graph: GList; Color: CList; i,j,n: Byte; G: File of GList; s: string;

Procedure GetColor;

Begin

For i: =1 to n do

Color [i]: =1;

For i: =2 to n do

begin

j: =1;

While (j<=Graph [i]. Count) and (Graph [i]. List [j] <i) do

Begin

If Color [i] =Color [Graph [i]. List [j]] Then

Begin

Color [i]: =Color [i] +1;

j: =1;

end

Else

j: =j+1;

end;

end;

end;

Procedure Vvid_K;

Begin

Write ('Введіть кількість вершин: ');

Readln (n);

For i: =1 to n do

Begin

Write ('Введіть кількість вершин суміжних з ', i,'-ю: ');

Readln (Graph [i]. Count);

Writeln ('Введіть номери вершин суміжних з ', i,'-ю: ');

For j: =1 to Graph [i]. Count do

Begin

Write (j,'-а вершина: ');

Readln (Graph [i]. List [j]);

end;

end;

Writeln ('Зберегти введений граф у файл? [Y/N] ');

Case ReadKey of

'Y','y': Begin

Write ('Введіть назву файлу: ');

Readln (s);

Assign (G,s);

Rewrite (G);

Write (G,Graph);

Close (G);

end;

'N','n': Begin

end;

end;

end;

Procedure Vuvid;

Begin

For i: =1 to n do

begin

TextColor (Color [i]);

Write (i,': ');

For j: =1 to Graph [i]. Count do

Begin

TextColor (Color [Graph [i]. List [j]]);

Write (Graph [i]. List [j],' - ');

end;

Writeln;

end;

Readkey;

end;

BEGIN

Repeat

TextColor (15);

ClrScr;

Writeln ('1. Завантажити граф з файлу');

Writeln ('2. Ввести новий граф з клавіатури');

Writeln ('3. Знайти оптимальне розфарбування');

Writeln ('4. Вихід з програми');

Case ReadKey of

'1': Begin

Write (' Введіть назву файлу: ');

Readln (s);

Assign (G,s);

Reset (G);

Read (G,Graph);

end;

'2': Vvid_K;

'3': Begin

GetColor;

Vuvid;

end;

'4',#27: Begin

Break;

Close (G);

end;

end;

Until False;

end.

Размещено на Allbest.ru