АЛГОРИТМИ РОЗФАРБУВАННЯ ГРАФА

Вачевського Олега Орестовича

Науковий керівник

кандидат технічних наук, доцент

Григорович Андрій Геннадійович

1. Допущено до захисту

„____” _________2014 р. Науковий керівник ____________ _______________

підпис прізвище, ім’я

2. Оцінка захисту _________

„____”__________ 2014 р. Члени комісії ____________ __________________

підпис прізвище, ім’я

_________ ______________

підпис прізвище, ім’я

_________ ______________

підпис прізвище, ім’я

Дрогобич 2014

Зміст

ВСТУП.. 3

РОЗДІЛ 1. 4

ГРАФ ТА ОСНОВНІ ОЗНАЧЕННЯ.. 4

РОЗДІЛ 2. 5

АЛГОРИТМИ РОЗФАРБУВАННЯ ГРАФА.. 6

2.1 Хроматичне число графа. 7

2.2 Хроматичний багаточлен. 8

2.3 Проблема чотирьох фарб. 9

2.4 Точні та евристичні методи розфарбовування графа. 11

2.5 Генетичний алгоритм розфарбування графу. 12

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

2.7 Практичне застосування розфарбування графів. 14

ВИСНОВКИ.. 15

ПЕРЕЛІК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ.. 17

Додатки.. 17

ВСТУП

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

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

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

РОЗДІЛ 1

ГРАФ ТА ОСНОВНІ ОЗНАЧЕННЯ

Граф – сукупність об’єктів з вказаними зв’язками між ними.

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

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

Граф, що містить лише ребра – називається неорієнтованим, а той, що містить лише дуги – орієнтований. Всі інші є мішаними.

Петля – дуга чи ребро, що сполучає вершину графа сама із собою.

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

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

Матриця суміжності простого графа є бінарною матрицею і містить нулі на головній діагоналі.

Матриця інцидентності – одна з форм представлення графа, в якій вказується зв’язок між інцидентними елементами графа (ребро і вершина). Стовпці матриці відповідають ребрам , рядки – вершинам. Ненульову значення у матриці вказує на зв'язок між вершиною і ребром.

Матриця суміжності – спосіб представлення графа у вигляді матриці.

Матриця суміжності графа G зі скінченою кількістю вершин (пронумерованої від 1 до n) – квадратна матриця А розмірності n, в якій значення елемента α_ij рівне числу ребер, що сполучає i-ту та j-ту вершини.[1]

РОЗДІЛ 2

АЛГОРИТМИ РОЗФАРБУВАННЯ ГРАФА

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

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

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

Нехай G=(V,E) – неорієнтований граф, з кількістю вершин що дорівнює n. Розфарбовуванням графу називатимемо відображення φ множини V на множину С таку, що С={с₁ .. с_m}. Елементи множини С називатимемо фарбами.

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