Розфарбування графів
ТТпавильне поч(Ьапб¥вання
Граф, для якого існує правильне к-розфарбування, називається розфарбованим графом.
При визначенні розфарбування графа множину Nk можна замінити довільною к-елементною множиною.Правильне розфарбування графа можна трактувати як розфарбування кожної його вершини в один з k кольорів, таким чином, щоб суміжні вершини були розфарбовані в різні кольори. Оскільки функція f не обов’язково взаємно однозначна, то при к-розфарбуванні фактично може бути використано менш ніж k кольорів. Отже,
правильне к-розфарбування можна розглядати як розбиття множини вершин V графа G на класи
1, 2, 1. Кожний клас Vi - незалежна множина, а самі класи
називаються колірними класами.
Мінімальне число к, при якому існує правильне к-розфарбування графа G, називається хроматичним числом цього графа і позначається Xp(G). Якщо Xp(G) = к, то граф G називається к-хроматичним. Правильне к-розфарбування графа G при к = Xp(G) називається мінімальним (рис. 48).
На рис. 48 натуральними числами 1, 2, 3, 4 позначені фарби відповідних вершин
Рис.48
Практичні задачі, що призводять до розфарбування
Задача складання розкладу занять. Нехай потрібно прочитати кілька лекцій за найкоротший проміжок часу. Читання лекції займає одну годину, але деякі лекції не можуть читатися одночасно (наприклад, коли їх читає один лектор). Побудуємо граф G = (V, Е), де V - множина, яка відповідає множині лекцій, причому дві вершини суміжні тоді і лише тоді, коли відповідні лекції не можуть читатися одночасно. Очевидно, що всяке правильне розфарбування цього графа визначає допустимий розклад: лекції, які відповідають вершинам графа, що становлять один колірний клас, читаються одночасно.
Навпаки, всякий допустимий розклад визначає правильне розфарбування графа G. Оптимальний розклад відповідає мінімальним розфарбуванням, а число годин, необхідне для того, щоб прочитати всі лекції, дорівнює Xp(G).Хроматичні числа деяких графів
Для деяких простих графів неважко знайти хроматичні числа. Наприклад,
2,
Твердження про хроматичні числа графів:
• граф є 1-хроматичним тоді і лише тоді, коли він пустий, а 2- хроматичним - коли він двочастинний і непустий, 2-хроматичні графи, називають біхроматичними;
• непустий граф є біхроматичним тоді і лише тоді, коли він не має циклів непарної довжини;
Хоча наведені твердження і дають певну інформацію про хроматичні числа графів, але їх оцінки досить неточні. Наприклад, зірковий граф Kijll, розфарбовується п фарбами, насправді є біхроматичним.
2.6.5.