|
Теорема Брукса У теорії графів, теорема Брукса встановлює зв'язок між максимальним степенем графа і його хроматичним числом. Згідно з теоремою, зв'язний граф, у якому кожна вершина має не більше Δ сусідів, вершини можуть бути пофарбовані не більше ніж в Δ кольорів, за винятком двох випадків — повний граф і граф-цикл непарної довжини, які вимагають Δ + 1 кольорів. Теорема названа на честь Леонарда Брукса[en], який опублікував доказ в 1941 році. Розмальовку з кількістю кольорів, описаних теоремою Брукса, іноді називають забарвленням Брукса або Δ-розмальовкою. ФормулюванняДля будь-якого зв'язного неорієнтованого графа G з максимальним степенем Δ, хроматичне число графа G не більше Δ, за винятком випадків, коли G — кліка або непарний цикл. У цих випадках хроматичне число дорівнює Δ + 1. ДоведенняЛасло Ловас (László Lovász, 1975) дає спрощений доказ теореми Брукса[1]. Якщо граф не є двозв'язним, його двозв'язні компоненти можна розфарбувати окремо, а потім об'єднати розмальовки. Якщо граф містить вершину v зі ступенем, меншим Δ, то алгоритм жадібної розмальовки, який розфарбовує вершини згідно з відстанню від v (дальні — в першу чергу, ближні — в останню) використовує максимум Δ кольорів[2]. Таким чином, найбільш складними випадками для доказу є двозв'язні Δ-регулярні графи з Δ ≥ 3. Ловас показує, що можна знайти кістякове дерево, таке що двоє несуміжних сусіди u і w кореня v лежать на дереві. Привласнимо вершинам u і w один (будь-який) колір. Жадібний алгоритм, починає в u і w і проходить решту вершин кістякового дерева (піднімаючись від кореня до листя), використовує максимум Δ кольорів. Коли всі вершини, відмінні від v, розфарбовані, вони мають незабарвленого батька, так що вже пофарбовані кольори не можуть використовувати всі вільні кольори, оскільки два сусіди v (u і w) мають один колір. У невикористаний колір розфарбуємо саму вершину v. УзагальненняБільш загальна версія теореми відноситься до списку розфарбування[en] — якщо заданий зв'язний неорієнтований граф з максимальним степенем Δ, який не є ні клікою, ні циклом непарної довжини, і список Δ кольорів для кожної вершини, можна вибрати колір кожної вершини зі списку так, що ніякі дві суміжні вершини не мають один колір. Іншими словами, запропоноване хроматичне число зв'язкового неорієнтованого графа ніколи не перевершує Δ, якщо лише G не є клікою або циклом непарної довжини. Теорема була доведена Вадимом Візінгом. Для деяких типів графів потрібно навіть менше Δ кольорів. Брюс Рід[en](1999) показав, що Δ-1 кольорів достатньо тоді і лише тоді, коли граф не містить Δ-кліки, але при цьому Δ має бути достатньо великим. Для графів без трикутників, а також для більш загального класу графів, в яких околи вершин достатньо розріджені, достатньо O(Δ/log Δ) кольорів[3]. Степінь графів з'являється також при оцінці верхньої межі іншого типу забарвлення — реберної. Те, що хроматичний індекс не перевищує Δ + 1 є теоремою Візінга. Розширення теореми Брукса на тотальну розмальовку, яке стверджує, що тотальне хроматичне число не перевищує Δ + 2, було запропоновано Бехзадом та Візінгом як гіпотеза. Теорема Хайналь — Семереді про рівномірне розфарбування стверджує, що будь-який граф має (Δ + 1) кольорову розмальовку, при якій число вершин двох різних кольорів відрізняється максимум на одиницю. АлгоритмиΔ-розмальовку, або навіть приписану Δ-розмальовку, графа зі ступенем Δ можна знайти за лінійний час[4]. Відомі ефективні алгоритми для пошуку розмальовки Брукса в паралельних і розподілених середовищах обчислень[5]. ПриміткиПосилання
|