Раскраска графа: почему три цвета сложнее двух

Коротко

Правильная раскраска - назначение вершинам цветов так, чтобы соседи не совпадали; хроматическое число χ(G) - наименьшее число цветов, которого хватает. Два цвета проверяются за O(V + E) (это двудольность из прошлого урока), а уже для трёх задача NP-полна: быстрого алгоритма не известно, и найти его значило бы решить главную открытую проблему информатики. Поэтому на практике красят ЖАДНО: перебирают вершины в каком-то порядке и дают каждой наименьший цвет, не занятый её соседями. Жадность никогда не тратит больше Δ + 1 цветов, где Δ - максимальная степень, но ОПТИМУМА НЕ ГАРАНТИРУЕТ: результат зависит от порядка, и на специально построенном графе она промахивается сколь угодно сильно (иногда, впрочем, попадает в оптимум - как в разборе ниже).

Если ты знаешь про хроматическое число, помнишь оценку жадной раскраски Δ + 1 и понимаешь, почему три цвета - трудная задача, а два - лёгкая, листай до «Теперь сам».

Как думаешь, где проходит граница трудности

Проверить, хватает ли ДВУХ цветов, мы научились за один обход. Прежде чем читать дальше, прикинь: как проверить, хватает ли ТРЁХ? Есть ли столь же простой критерий вроде «нет циклов такой-то длины»? Подсказка: если бы он был, о нём бы знали - и задача не входила бы в список классических трудных.

На что это похоже

Расписание экзаменов. Экзамены, на которые записан один и тот же студент, нельзя ставить в одно время - это ребро в графе. Цвет - время проведения. Минимальное число цветов - минимальное число слотов, за которое можно провести сессию. Легко проверить, хватит ли двух дней. А вот вопрос «хватит ли трёх» внезапно становится переборным: никакого простого признака у него нет.

Механизм: жадная раскраска и её граница

def greedy_coloring(order):
    color = [-1] * V
    for v in order:                       # порядок - параметр!
        used = {color[u] for u in adj[v] if color[u] != -1}
        c = 0
        while c in used:                  # наименьший свободный цвет
            c += 1
        color[v] = c
    return color

Почему цветов не больше Δ + 1: у вершины не больше Δ соседей, значит они занимают не больше Δ цветов, и среди цветов 0..Δ хотя бы один свободен. Цена - O(V + E).

Что известно про сами числа:

χ(G) = 1   ⇔ рёбер нет вовсе
χ(G) <= 2  ⇔ граф двудолен (проверяется за O(V + E))
χ(G) <= 3  - NP-полная задача уже для планарных графов
χ(G) <= Δ + 1 всегда (жадная раскраска)
χ(G) <= Δ   для связного графа, кроме полного графа и нечётного цикла (теорема Брукса)
χ(G) >= размер наибольшей клики (полного подграфа)

Порядок перебора решает многое. Популярные эвристики: по убыванию степени (Welsh-Powell); smallest-last - многократно снимать вершину НАИМЕНЬШЕЙ степени, складывая снятые в стек, а потом красить в обратном порядке; DSATUR - на каждом шаге брать вершину с наибольшим числом РАЗНЫХ цветов среди соседей. На практике они дают близкие к оптимуму ответы, но гарантии оптимальности не дают ни одна.

Правило

Правильная раскраска - соседи разных цветов; χ(G) - минимальное число цветов. χ <= 2 проверяется за O(V + E) (двудольность), проверка χ <= 3 NP-полна. Жадная раскраска даёт не больше Δ + 1 цветов за O(V + E), но зависит от порядка и оптимальной не гарантирует. Нижняя граница - размер наибольшей клики; по теореме Брукса связному графу хватает Δ цветов, кроме полного графа и нечётного цикла.

Разбор: жадность зависит от порядка

Классический плохой случай - «корона»: двудольный граф с долями {a₁...a_k} и {b₁...b_k}, где a_i соединена со всеми b_j, КРОМЕ b_i. Он двудольный, значит двух цветов хватает заведомо. Возьмём k = 3 и проследим два порядка.

Порядок по долям (a₁, a₂, a₃, b₁, b₂, b₃): все a попарно не соседи → все получают цвет 0. Каждая b видит только вершины a (цвет 0) → все получают цвет 1. Итого два цвета, оптимум.

Порядок вперемешку (a₁, b₁, a₂, b₂, a₃, b₃). Выпишем соседей: a₁ дружит с b₂ и b₃, a₂ - с b₁ и b₃, a₃ - с b₁ и b₂.

a₁ → покрашенных соседей нет                     → цвет 0
b₁ → соседи a₂, a₃ ещё белые                       → цвет 0   (b₁ и a₁ НЕ соседи)
a₂ → сосед b₁ цвета 0                            → цвет 1
b₂ → сосед a₁ цвета 0 (a₃ ещё не покрашена)      → цвет 1
a₃ → соседи b₁ (0) и b₂ (1)                      → цвет 2
b₃ → соседи a₁ (0) и a₂ (1)                      → цвет 2

Итого три цвета вместо двух - и всё из-за порядка.

На больших k эта конструкция даёт k цветов вместо двух: разрыв между жадностью и оптимумом неограничен. Это не мелкий недостаток, а причина, по которой раскраску не считают решённой задачей.

Разбор: почему два легко, а три трудно

Полезно понять, ГДЕ ломается рассуждение при переходе от двух цветов к трём.

С двумя цветами выбора нет: как только покрашена одна вершина, цвета всех остальных в её компоненте определены однозначно - каждый сосед обязан быть противоположным. Алгоритм просто распространяет единственно возможное решение и либо доходит до конца, либо натыкается на противоречие. Никакого перебора.

С тремя цветами выбор появляется: покрасив вершину в цвет 0, её соседу можно дать 1 ИЛИ 2. Каждое такое решение влияет на дальнейшее, и отката может потребоваться сколь угодно много. Именно эта свобода и делает задачу переборной: известно, что 3-раскраска NP-полна, причём даже для планарных графов (для которых, к слову, четырёх цветов хватает всегда - об этом следующий урок).

Практический вывод: если задача сводится к раскраске, не ищи точный алгоритм - либо соглашайся на жадную эвристику с хорошим порядком, либо ограничивай размер входа и перебирай, либо ищи дополнительную структуру, которая делает частный случай лёгким (двудольность - два цвета за линию; планарность - четырёх цветов хватает всегда).

Что ломается без этого

Первое: считать, что жадная раскраска даёт хроматическое число - она даёт лишь верхнюю оценку, и на специально построенных графах промахивается в разы. Второе: ждать, что «хороший» порядок решит проблему - эвристики помогают в среднем, но и у DSATUR есть плохие входы. Третье: путать Δ + 1 с точным ответом: у длинного пути Δ = 2, а хватает двух цветов, а не трёх. Четвёртое: забывать про нижнюю границу - если в графе есть клика на k вершинах, меньше k цветов не бывает никогда, и это первый способ доказать, что решение оптимально. Пятое: пытаться свести задачу к раскраске и удивляться, что «алгоритм долго работает»: точная раскраска - экспоненциальный перебор, и надо сразу выбирать между точностью и временем.

Зачем это в работе

Самое известное применение - распределение регистров в компиляторах: вершина это переменная, ребро означает «эти две живут одновременно, значит не могут занимать один регистр», цвет - регистр. Если цветов не хватает, часть переменных «выплёскивают» в память; современные компиляторы используют именно эвристики раскраски. Дальше: назначение частот передатчикам (соседние вышки не должны работать на одной частоте), составление расписаний (экзамены, смены, переговорки), планирование задач с конфликтами за ресурс, разбиение тестов на группы, которые можно гонять параллельно. Общее во всех: «конфликтующие сущности - в разные слоты», и сразу же общий вывод - точного решения ждать не стоит, а хорошая эвристика с внятной верхней границей чаще всего и есть ответ.

Теперь сам

Граф - «колесо»: цикл 1-2-3-4-5-1 и центр 6, соединённый со всеми пятью. Сколько цветов нужно? Сколько даст жадная раскраска в порядке 6, 1, 2, 3, 4, 5?

Ответ. Сначала оптимум. Центр соединён со всеми, значит его цвет не может совпасть ни с одним другим - один цвет уходит на него. Остальные пять образуют цикл нечётной длины, а такому циклу двух цветов не хватает (это критерий из прошлого урока), нужно три. Центру нужен цвет, отличный от всех цветов цикла, значит всего 3 + 1 = 4. Меньше нельзя: три цвета цикл израсходует полностью, и центру, который видит все пять его вершин, не останется ничего. Значит χ = 4. Теперь жадность в порядке 6, 1, 2, 3, 4, 5: 6 → цвет 0. 1 → сосед 6 цвета 0 → цвет 1. 2 → соседи 6 (0) и 1 (1) → цвет 2. 3 → соседи 6 (0) и 2 (2) → цвет 1. 4 → соседи 6 (0) и 3 (1) → цвет 2. 5 → соседи 6 (0), 4 (2) и 1 (1) → цвет 3. Жадность потратила четыре цвета - здесь она попала в оптимум. Проверь себя: максимальная степень Δ = 5 (у центра), значит граница Δ + 1 = 6, и реальный результат оказался заметно лучше границы - так обычно и бывает, но гарантии нет.

Главное

Правильная раскраска - соседи разных цветов; χ(G) - минимальное число цветов. Граница простоты проходит между двумя и тремя: χ <= 2 равносильно двудольности и проверяется обходом за O(V + E), а проверка χ <= 3 NP-полна - и причина видна прямо в алгоритме: с двумя цветами выбора нет (цвет соседа определён однозначно), с тремя появляется развилка, и решение становится переборным. На практике красят жадно: перебирают вершины и дают каждой наименьший цвет, свободный у соседей; это O(V + E) и не больше Δ + 1 цветов, потому что Δ соседей не могут занять Δ+1 цвет. Но результат зависит от ПОРЯДКА, и на специально построенном двудольном графе жадность даёт k цветов вместо двух - разрыв неограничен. Полезные ориентиры: нижняя граница - размер наибольшей клики; теорема Брукса даёт Δ цветов для связного графа, кроме полного графа и нечётного цикла; эвристики порядка (по убыванию степени, DSATUR) улучшают результат, но гарантий не дают. Раскраска - это распределение регистров, частот, слотов расписания: там, где конфликтующие сущности нельзя ставить вместе.