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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Розфарбовування графа Петерсена трьома кольорами.

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

Теорема[ред. | ред. код]

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

Доведення[ред. | ред. код]

Застосуємо індукцію за кількістю вершин графа. Нехай граф G має n вершин; вилучимо з нього довільну вершину u разом з усіма інцидентними їй ребрами. Отримаємо граф з n-1 вершиною, степінь кожної вершини не більший ніж p. За припущенням індукції цей граф можна розфарбувати в p+1 колір. Отже, у p+1 колір можна розфарбувати й граф G, якщо розфарбувати вершину u кольором, що відрізняється від тих, якими розфарбовано суміжні з нею вершини (а їх разом не більше ніж p).

Теорема (Р.Хейвуда)[ред. | ред. код]

Будь який планарний граф можна розфарбувати в п'ять кольорів , тобто χ(G)≤5 для будь-якого планарного графа G.

Доведення[ред. | ред. код]

Доведення цієї теореми ґрунтується на тому, що в будь-якому простому планарному графі є вершина, степінь якої не більший ніж п'ять. Застосуємо математичну індукцію за кількістю вершин графа. Теорема справджується для графів із не більше ніж n вершинами,де n ≥5. Розглянемо довільний плоский граф G з (n+1) вершиною. Він містить вершину u_0, степінь якої не більший ніж п'ять. Нехай W =Г(u_0)- множина вершин, суміжних із вершиною u_0 в графі G. Розглянемо наступний випадок. | W |≤4. Позначимо як G - u_0 граф,отриманий із графа G вилученням вершини u_0 та всіх інцидентних їй ребер .За індуктивним припущенням граф G - u_0 можна розфарбувати в п'ять кольорів. Зафіксуємо одне з таких розфарбувань і зафарбуємо вершину u_0 в той із п'яти кольорів,який не використано для фарбування вершин із множини W.

Теорема[ред. | ред. код]

Нехай G - простий граф , а u та w - його несуміжні вершини. Якщо граф G_1 отримано з G за допомогою з'єднання вершин u та wребром, а граф G_2 - ототожненням вершини u та w ( і кратних ребер, якщо їх буде одержано), то P_G(k)=P_G1(k)+P_G2(k).

Доведення[ред. | ред. код]

За будь-якого допустимого розфарбовування вершин графа G існує альтернатива: u та w мають різні кольори, або той самий. Кількість розфарбовувань, за яких u та w мають різні кольори , не зміниться, якщо долучити ребро {u, w}. Отже, ця кількість дорівнює P_G1(k). Аналогічно, кількість розфарбовувань ,за яких u та w мають один колір, не зміниться, якщо ототожнити u та w. Залишилось застосувати комбінаторне правило суми. Теорему доведено.

Наслідок[ред. | ред. код]

Хроматична функція простого графа - поліном. P_G(k) - хроматичний поліном .Якщо граф G має n вершин, то степінь полінома P_G(k) дорівнює n. Коефіцієнт kn дорівнює 1, а при kn-1 дорівнює -m, де m - кількість ребер графа G; знаки коефіцієнтів чергуються; вільний член хроматичного полінома дорівнює 0. Хроматичний поліном будують на основі теореми 3.19 у вигляді суми хроматичних поліномів повних графів.

Див. також[ред. | ред. код]

Література[ред. | ред. код]

  • Ю.В. Нікольський , В.В. Пасічник,Ю.М. Щербина "Дискретна математика", 2007.