Page 74 - 4496

вершину, потім знаходимо будь-яку вершину, не суміжну з
нею, потім знаходимо вершину, не суміжну з відібраними
вершинами й т.д. Природно, що МНС у даному графі може
бути багато й вони можуть містити різне число вершин.
Перейдемо до опису алгоритму знаходження
найкращого розфарбування вершин графа. Нехай маємо граф
G, знайдемо в ньому будь-яку МНС, яку позначимо S1, і всі
вершини, що входять у цю МНС, пофарбуємо в кольори № 1.
Далі, видалимо з даного графа всі вершини, що входять у цю
МНС (разом з ребрами), і для нового графа знову знайдемо
МНС, що позначимо S2. Ці нові вершини пофарбуємо в
кольори № 2, потім видалимо ці вершини із графа разом з
відповідними ребрами й знову знаходимо МНС, що
пофарбуємо в кольори № 3, і т.д. Можна довести, що при
будь-якому способі здійснення цієї процедури прийдемо до
найкращого розфарбування й знайдемо деяку функцію Гранди
й хроматичне число даного графа.
Приклад. У графа (рис. 3.9,а) є 3 максимально
незалежних систем вершин: {5}, {1,3} й {2,4}. Ясно, що при
будь-якій процедурі знаходження хроматичного числа в
цьому графі, одержимо число 3.
Теорема. Якщо максимальний ступінь вершин у графі
дорівнює , те хроматичне число цього графа не перевершує 
+ 1. При цьому хроматичне число графа дорівнює + 1 тільки
у двох випадках: по-перше, якщо граф є повним й, по-друге,
якщо  = 2 і при цьому даний граф містить контур непарної
довжини (такий граф зображений на рис. 3.9,б, максимальний
ступінь його вершин – 2, а хроматичне число – 3). У всіх
інших випадках хроматичне число графа не перевершує
максимального ступеня вершин.

71