6.7. Хроматика графів

6.7.1. Хроматичне число

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

Це число називається хроматичним числом графа , його позначатимемо h ( G ). Якщо h (G) = k, то граф називається k-

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

хроматика

Існує кілька алгоритмів знаходження точного зна-

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

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

Отже, нехай побудовані всі максимальні незалежні множини графа G (нехай таких множин t) і нехай задана (n × t) матриця M = < m ij >, у якої m ij =1, якщовершина x i належить максимальному незалежному множині, і m ij = 0 інакше. Якщо тепер кожній максимальній незалежній множині зіставити одиничну вартість, то завдання розмальовки зведеться просто до завдання знаходження найменшого числа стовпців у матриці М, що покривають всі її рядки х. Кожен стовпець із рішення