Материал: discrete_mathematics

Розфарбування f графа G називають правильним, якщо для будь-яких його суміжних вершин v і w виконується f (v) ≠ f (w).

Мінімальне число k, для якого існує правильне розфарбування графа G, називають хроматичним числом графа G і позначають χ(G).

Мінімальним правильним розфарбуванням графа G нази-

вають правильне розфарбування для k = χ(G).

Для певних типів графів визначити хроматичні числа нескладно. Наприклад, 1-хроматичними є порожні графи G = (V, ) і тільки вони. Хроматичне число повного графа Kn дорівнює n, а хроматичне число довільного двочасткового графа − 2. 2-хрома- тичні графи часто називають біхроматичними.

Неважко обґрунтувати такі твердження.

Якщо кожна зв'язна компонента графа G потребує для свого правильного розфарбування не більше k фарб, то χ(G) ≤ k.

Граф є біхроматичним тоді й тільки тоді, коли він двочастковий. Зокрема, усі дерева та прості цикли парної довжини C2k біхроматичні. Водночас χ(C2k + 1) = 3.

Приклад 4.17. Доведемо, що для довільного графа G виконується нерівність χ(G) ≤ (G) + 1, де (G) – найбільший зі степенів вершин графа G.

Доведення проведемо індукцією за кількістю n вершин графа G. Для тривіального графа (n = 1) і графів із двома вершинами нерівність виконується.

Нехай твердження теореми виконується для всіх графів із кількістю вершин t (t ≥ 2). Розглянемо довільний граф G із t + 1 вершиною. Вилучимо з нього деяку вершину v. Дістанемо граф G′, степені всіх вершин якого не перевищують (G). Отже, за припущенням індукції для правильного розфарбування G′ потрібно не більше ніж (G) + 1 фарб. Правильне розфарбування для G дістанемо з правильного розфарбування графа G′, якщо пофарбуємо вершину v у колір, відмінний від кольорів усіх суміжних із v вершин. Оскільки таких вершин не більше ніж (G), то для правильного розфарбування графа G достатньо (G) + 1 фарб. ◄

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

в'язано зі відомою проблемою (гіпотезою) чотирьох фарб.

187

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

Гіпотеза чотирьох фарб виникла у зв'язку з розфарбуванням друкованих географічних карт (звідси й термін плоска карта) і

була сформульована так: грані довільної плоскої карти можна

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

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

Ця гіпотеза виникла в середині ХIХ ст. Більше ста років дослідники намагалися її довести чи спростувати. У результаті багаторічних досліджень виявилось, що для розв'язання проблеми чотирьох фарб потрібно перевірити її справедливість для скінченної кількості графів певного вигляду. Кількість варіантів, які потрібно було перебрати, була настільки великою, що тільки за допомогою потужної ЕОМ, яка неперервно працювала протягом більше двох місяців, у 1976 р. справедливість гіпотези чотирьох фарб було підтверджено. Однак такий фізичний, експериментальний спосіб доведення не зовсім влаштовує багатьох професіональних математиків, тому вони продовжують пошуки аналітичного доведення гіпотези.

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

довільного планарного графа потрібно не більше шести фарб. Доведення виконаємо індукцією за кількістю n вершин гра-

фа. Для n ≤ 6 твердження очевидне.

Припустимо, що хроматичне число всіх планарних графів із t вершинами не перевищує 6 (t ≥ 6). Розглянемо довільний планарний граф G із t + 1 вершиною. Згідно із прикладом 4.15(5) у графі G існує вершина v, степінь якої не більше 5. Вилучимо вершину v із графа G. Отримаємо граф G′, вершини якого за припущенням індукції можна правильно розфарбувати не більше ніж у шість кольорів. Тоді правильне розфарбування для G отримаємо з одержаного правильного розфарбування графа G′, надаючи вершині v колір, відмінний від кольорів усіх суміжних із нею вершин. Оскільки таких вершин не більше п'яти, то для виконання цієї процедури достатньо шести фарб. Отже,

χ(G) ≤ 6. ◄

188

Пропонуємо самостійно переконатись у справедливості такого твердження: для довільного планарного графа G виконується

χ(G) ≤ 5.

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

Критичний граф G, для якого k = χ(G), називають k-кри тичним.

Приклад 4.19.

1. Доведемо, що будь-який повний граф є критичним.

χ(Kn) = n, а після вилучення довільної вершини з Kn (див. п. 4.2) отримаємо повний граф Kn – 1, хроматичне число якого дорівнює n – 1.

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

кілька компонент зв'язності. Вилучимо довільну вершину з тієї компоненти зв'язності графа G, хроматичне число якої не перевищує хроматичні числа решти компонент зв'язності. Отримаємо суперечність, оскільки після такого вилучення хроматичне число графа G не зміниться. ◄

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

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

Завдання для самостійної роботи

1. Визначити хроматичне число: (а) повного графа Kn;

(б) повного двочасткового графа Kn,m; (в) довільного двочасткового графа; (г) простого циклу довжиною 2k;

(д) простого циклу довжиною 2k + 1, k N; (е) дерева.

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

189

3.Чому дорівнює хроматичне число повного графа Kn, з якого вилучено одне ребро?

4.Довести, що граф G біхроматичний тоді й тільки тоді, коли він не містить циклів непарної довжини.

5.Довести, що для довільного планарного графа G викону-

ється нерівність χ(G) ≤ 5.

6.Знайти графи, які мають різні хроматичні числа й у яких: (а) кількість вершин степеня k однакова для всіх k ≥ 0;

(б) кількість простих циклів довжиною l однакова для всіх l; (в) виконуються обидві умови з п. (а) та (б).

7.Знайти всі 2-критичні й 3-критичні графи.

4.10. Обходи графів

Появу теорії графів як розділу математики пов'язують із задачею про кенігсберзькі мости. Сім мостів міста Кенігсберга було розташовано на р. Прегель так, як зображено на рис. 4.11, а (B і C – береги, А та D – острови).

СС

аб

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

Оскільки істотними є тільки переходи через мости, то план міста можна зобразити у вигляді графа G (із кратними ребрами), вершинами якого є береги й острови (точки А, В, С і D), а ребрами − мости (рис. 4.11, б). Тоді задачу про кенігсберзькі мости мовою теорії графів можна сформулювати так: чи існує в графі G цикл, який містить усі ребра графа? Інше відоме формулювання проблеми: чи можна накреслити фігуру, що зображає граф G, не відриваючи олівця від паперу й не повторюючи ліній

190

двічі, почавши й закінчивши процедуру в одній із вершин фігури? Уперше відповідь на це запитання дав Л. Ейлер у 1736 р. Його роботу, у якій викладено розв'язок задачі, вважають початком теорії графів.

Цикл, що містить усі ребра графа, називають ейлеровим. Зв'язний граф, що має ейлерів цикл, називають ейлеровим.

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

Оскільки для графа G на рис. 4.11, б умови теореми Ейлера не виконуються, то в задачі про кенігсберзькі мости відповідь негативна.

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

Подвоїмо кожне ребро графа G, перетворивши його на мультиграф G′ (див. п. 4.11). Степені всіх вершин G′ парні, тому за теоремою Ейлера в G′ існує цикл, що містить усі його ребра. Циклу відповідає шуканий циклічний маршрут у графі G. ◄

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

Для знаходження якогось ейлерового циклу в ейлеровому графі G можна застосувати алгоритм Фльорі. Фіксуємо довільну початкову вершину циклу. На кожному кроці процедури до шуканого циклу обираємо (доки це можливо) те ребро, після вилучення якого граф не розіб'ється на дві нетривіальні зв'язні компоненти. Кожне обране ребро вилучаємо із G. Процедуру завершуємо, коли всі ребра буде вичерпано. Сформульований алгоритм будує ейлерів цикл графа G.

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

вають гамільтоновим циклом. Граф називають гамільтоновим,

якщо він має гамільтонів цикл.

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

191