Лекція № 4 розмальовки

1. Введення

Різноманітні завдання, що виникають при плануванні виробництва, складанні графіків огляду, зберігання і транспортування товарів і т.д. можуть бути представлені часто як задачі теорії графів, тісно пов'язані з так званої «завданні розмальовки». Графи, що розглядаються в цьому розділі, є неорієнтованими і не мають петель; якщо спеціально не обмовляється інше, то під словом «граф» розуміється саме такий граф.

Граф

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

Взагалі кажучи, хроматичної число графа (так само як числа незалежності і домінування, розглянуті в попередньому розділі) не можна знайти, знаючи тільки числа вершин і ребер графа. Недостатньо також знати ступінь кожної вершини, щоб обчислити хроматичної число графа. У цьому можна переконатися, розглядаючи графи, наведені на рис.1 (а) і рис.1 (б). Ці графи мають по n = 12 вершин, m = 16 ребер і однакове розподілу степенен вершин

. Однак хроматичні числа даних графів рівні 4 і 2 відповідно. При відомих величинах n (число вершин), m (число ребер) і (Ступеня вершин графа) можна отримати верхню і нижню оцінки для хроматичного числа графа. Цим оцінками присвячений наступний розділ.

Завдання знаходження хроматичного числа довільного графа з'явилася предметом багатьох досліджень в кінці XIX і в поточному столітті. Зараз з цього питання відома велика кількість цікавих результатів. В цьому розділі, однак, ми не намагаємося обговорити ці результати або хоча б дати їх короткий огляд. Ми вводимо тільки такі поняття, які потрібні для побудови алгоритмів розв'язання задачі про розфарбування графа. Тут ми розглядаємо в основному алгоритми (як точні, так і «наближені»), що дозволяють знаходити (точне або наближене) значення хроматичного числа довільного графа і відповідну цьому значенню розмальовку вершин.

Рис.1. Два графа з однаковими n, m і розподілами ступенів вершин, але з різними хроматическими числами. (А)

.(Б) .

2. Деякі теореми і оцінки, які стосуються хроматичним числах

2.1. Нижні оцінки для.

оскільки число

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

де n - число вершин графа G. а

позначає наібольшеецелое число, яке не перевищує числа x.

Ще одна нижня оцінка для

запропонована Геллер: