Методи розфарбування графів

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

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

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

1. Теоретична частина

1.1 Основні поняття

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

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

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

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

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

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

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

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

Якщо пара вершин сполучена кількома ребрами чи дугами одного напрямку то такі ребра чи дуги називають кратними (||)

Таблиця

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

Мал.1

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

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

Кожна комірка матриці може набувати трьох значень:

1: якщо ребро виходить з і входить у ;

— 1: якщо ребро входить у і виходить з ;

0: якщо між і немає ребра.

Список суміжності — це послідовність (масив, список) розміром N, кожен елемент якої є списком вершин суміжних з даною.

Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з x.

1.2 Постановка задач про розфарбування графів

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

Задача про розфарбування карти

Знайти хроматичне число.

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

Мал. 2

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

Гіпотеза про чотири кольори

Хроматичне число любого планарного графа не перевищує 4.

Теорема Хівуда

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

Для доведення нам знадобиться

Лема про вершину степеня <5

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

Доведення. Достатньо показати, що потрібна вершина знайдеться в одній з компонент звязності заданого графа G. Отже, можнa вважати, що граф G звязний. Припустимо і. По відповідності про кількість ребер з теореми Ейлера про плоскі графи

Оскільки сума n доданків менше 6n, хоча б одне з додаваних менше 6 (тобто не більше 5 так як степінь вершини — натуральне число). Отже, існує вершина v графа G така, що ()?5. Нехай G — планарний граф. Можно вважати, що граф G э звичайним (петлі і кратні ребра не впливають на хроматичне число) і плоским (оскільки хроматичне число не змінюється при ізоморфізмі). Припустимо і будемо доводити індукцією по n. База індукції очевидна: якщо звичайний граф G містить одну вершину, то .

Крок індукції. Нехай n>1. Виберемо в графі G вершину v степеня? 5 (така вершина існує за тільки-що деведеню лемою). Розглянемо граф G —v. В ньому n —1 вершина, а отже, по умові індукції існує правильне розфарбування f графа G —v не більше ніж 5 кольорами.

Якщо для розфарбування вершин, суміжних з v, використано менше 5 кольорів, то розфарбування f можна доповнити до правильного розфарбування графа G не більш як 5 кольорами, розфарбувавши вершину v «не зайнятим» кольором. Тому далі можна вважати, що для розфарбування вершин, суміжних з v, використані всі 5 кольорів. В даному випадку з v суміжні рівно 5 вершин, позначимо їх, ,, ,. У порядку слідування за годинниковою стрілкою відносно v (див. мал.3).

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

Мал.3

Будемо вважати, що ,…,. Позначимо через підграф графа G, породжений усіма вершинами u, що . В нашому випадку, граф містить вершини і. Розглянемо 2 випадки.

Випадок 1: вершини і лежать в різних компонентах звязності графа. Нехай К — компоента звязності в, що містить вершину .

Перепозначимо f на K, перефарбувавши вершини кольору 1 в 3-й, і навпаки. Нова функція f теж буде правильним розфарбуванням графа G — v. Дійсно, «нові» вершини кольору 1 не суміжні ні між собою (оскільки і раніше мали один колір) ні зі старими вершинами кольору 1 (знаходяться в різних компонентах графа). Теж саме справедливо і для вершин кольору 3, а для вершин інших кольорів нічого не змінилось.

Отже, ми побудували правильне 5-розфарбування графа G — v, при якому ні одна з вершин, суміжних з v в графі G, не має кольору 1 (в результаті перефарбування вершина поміняла колір на 3, а вершини, ,, зберегли колір). Отже, можна зафарбувати вершину v в колір 1, отримуючи правильне 5-розфарбування графа G, що і вимагалось.

Мал. 4

Випадок 2: Вершини і лежать в одній і тій самій компоненті звязності графа. Отже, у графі G існує простий (,) ланцюг, усі вершини якої мають кольори 1 і 3. Додавши до цього ланцюга ребра (,) і (,), отримаємо простий цикл C (виділений на мал.4 червоним), обмежуючий частину площини, яка містить рівно одну з вершин і. Розглянемо підграф графа G, породжений усіма вершинами кольорів 2 та 4. В даному випадку, містить вершини і .

Припустимо, що вершини і лежать в одній компоненті звязності графа. Тоді їх можна поеднати ланцюгом, що проходить тільки через вершини графа. З геометричної точки зору, цей ланцюг — лінія, що поєднує точки і, і вона повинна перетнути цикл C як замкнуту лінію, оскільки одна з точок, знаходиться всередині, а інша — поза областю, обмеженої циклом С. Оскільки граф G плоский, спільна точка ланцюга і цикла може бути лише вершина графа. Але в циклі С немає жодної вершини кольору 2 або 4, ми дійшли протиріччя.

Звідси слідує і лежать в різних компонентах звязності графа. Аналогічно випадку 1, перефарбуємо компоненту звязності цього графа, що містить вершину, помінявши кольори 2 і 4 місцями.

Отримане при цьому розфарбування буде правильним 5-розфарбуванням графа G — v, при цьому серед суміжних з v вершин не буде вершини кольору 2. Розфарбувавши v в колір 2, отримаємо правильне 5-розфарбування графа G.

Теорема доведена. ?

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

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

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

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

Доведення цієї теореми стало першим випадком «комп`ютерного» вирішення важкої і давно стоявшої суто математичної проблеми. Повторити доведення К. Аппеля і В. Хейкена в рамках данного курсу неможливо, тому приводимо її без доведення.

1.3 Алгоритми розв`язання задач розфарбування графів

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

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

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

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

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

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

1.4 Деякі задачі, що зводяться до задачі розфарбування графів

Задача скаладання розкладу

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

Розглянемо приклад завдання на складання розкладу. У студентських групах КН-101 і КН-102 треба провести заняття з алгебри, дискретної математики, математичного аналізу та історії України (по одному заняттю по кожному предмету). Заняття по кожному предмету проводяться з кожною групою окремо. Заняття з алгебри та з дискретної математики веде викладач X, з математичного аналізу — викладач Y, з історії Росії - викладач Z. Знайти мінімальне число пар, в які можна «укласти» всі заняття, і скласти відповідний розклад.

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

Мал. 5

Задача розподілу обладнання

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

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

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

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

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

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

Мал. 6

2. Практична частина

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

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;

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

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]

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;

2.2 Контрольні приклади

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

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]

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.

Якщо ввести в програму планарний граф з мал.7

Мал.7

Програма виведе нам наступний результат:

Висновок граф програмний розфарбування В ході виконання даної курсової роботи було розглянуто та роз’яснено багато прикладів застосування деяких аспектів теорії графів, а саме — розфарбування графів. Був написаний код програми на мові Turbo Pascal що для введеного з клавіатури або завантаженого з файлу графа знаходить оптимальне розфарбування вершин.

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

Список використаної літератури

1. Верников Б. М., Шур А. М. «Алгебра і дискретна математика» 2004 р.(324с)

2. Спекторський І. Я. «Дискретна математика» 2004 р.(220c)

3. Березина Л. Ю. «Графы и их применение: Пособие для учителей» 1979р.