Розфарбування графів

Нехай G =(V,E ) довільний граф, а N_k={1,2,...,k }.

Будь-яке відображення f :V ® N_k, яке ставить у відповідність кожній вершині v ÎV деяке натуральне число f (v) ÎN_k, називається розфарбуваннямграфа G. Число f (v)називається кольором або номером фарби вершини v.

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

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

Мінімальним правильним розфарбуваннямграфа G називається правильне розфарбування для k=c(G ).

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

Очевидними є такі твердження.

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

Лема 3.7. Граф є біхроматичний тоді і тільки тоді, коли він двочастковий.

Зокрема, всі дерева і прості цикли парної довжини C_2k є біхроматичні. У той же час, c(C_2k+1)=3.

Використовуючи теорему 3.12 (Кеніга), останню лему можна переформулювати у такому вигляді.

Лема 3.8. Граф є біхроматичний тоді і тільки тоді, коли він не має циклів непарної довжини.

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

Теорема 3.16. Позначимо через D(G ) найбільший зі степенів вершин графа G, тоді c(G ) £ D(G )+1.

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

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

Наслідок 3.16.1. Для правильного розфарбування довільного кубічного графа достатньо чотири фарби.

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

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

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

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

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

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

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

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