Раскраска графа

Ниже — 2681 квартал центра Алматы: куски города между улицами. Раскрасим карту так, чтобы кварталы с общей улицей получили разные цвета. Это раскраска графа: кварталы — вершины, общая улица — ребро. Простейший способ — брать кварталы по одному и давать каждому первый цвет, которого нет у уже раскрашенных соседей. С запада на восток он тратит шесть цветов. Переключайте способы: порядок обхода меняет число цветов, а точный перебор находит четыре.

Четыре — это и нижняя граница: включите «Четыре соседа попарно», и сцена обведёт места, где четыре квартала соседствуют каждый с каждым. Таких мест 159, и трём цветам там не уложиться. Для карт четырёх цветов всегда хватает — это знаменитая теорема, — но доказана она с помощью компьютера, и алгоритм, который из доказательства следует, далёк от простого. Зато есть простые способы раскрасить в пять и шесть, и с доказательством, почему они работают.

Идея

Раскраска графа — назначение вершинам цветов так, чтобы концы любого ребра различались. Наименьшее число цветов, которым это можно сделать, — хроматическое число χ. Жадный способ проходит вершины в каком-то порядке и даёт каждой наименьший цвет, свободный от уже раскрашенных соседей. Он никогда не ошибается в правильности — соседи всегда разные, — но число цветов у него зависит от порядка, иногда сильно. Вся хитрость — в порядке.

Раскраска — общий язык для задач «соседи должны различаться». Экзамены с общими студентами — в разные дни. Переменные, которые живут одновременно, — в разные регистры процессора. Соседние вышки — на разные частоты. Персонажи, которые встречаются в одной главе, — разным актёрам. Цвет — день, регистр, частота, актёр, а хроматическое число — сколько их нужно как минимум.

Жадная раскраска и порядок

Для карты Алматы это слабая оценка: у одного квартала 38 соседей — это огромный квартал, окружённый мелкими, — и оценка обещает 39 цветов. Жадный способ тратит шесть или семь в зависимости от порядка. Сто случайных порядков из листинга дают 6 цветов 62 раза и 7 цветов — 38. Но хороший порядок существует всегда.

Правда, чтобы выписать такой порядок, нужна оптимальная раскраска — а её мы и ищем. Поэтому на деле берут порядки, которые легко посчитать. Самый старый — сначала вершины с наибольшим числом соседей: трудные вершины получают цвет, пока выбор ещё широк. Так в 1967 году предложили Доминик Уэлш и Мартин Пауэлл, и на кварталах Алматы это пять цветов вместо шести.

Наименьший последним

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

Пусть d — наибольшее из чисел «сколько соседей оставалось у вершины, когда её убирали». Его называют вырожденностью графа.

У кварталов Алматы d = 4: при удалении у квартала никогда не оставалось больше четырёх соседей, и порядок гарантирует пять цветов — столько он и тратит. Причина такой малой вырожденности — в том, что карта плоская.

DSatur: самый стеснённый — следующим

Порядок не обязан быть заданным заранее. В 1979 году Даниэль Брелаз предложил выбирать следующую вершину на ходу: ту, у соседей которой уже больше всего разных цветов. Это самая стеснённая вершина — если откладывать её, свободных цветов у неё станет только меньше. При равенстве берут вершину с большим числом соседей. Способ назвали DSatur, от «степень насыщенности».

На кварталах Алматы DSatur тратит пять цветов, как и «наименьший последним». Для двудольных графов он всегда находит раскраску в два цвета, а в целом часто бывает лучшим из простых способов. Но доказуемой оценки, как у порядка «наименьший последним», у него нет: в первой задаче статьи есть граф из десяти вершин с вырожденностью 2, где DSatur тратит четыре цвета, хотя порядок «наименьший последним» обходится тремя.

Точный ответ

Узнать хроматическое число — задача трудная: в 1972 году Ричард Карп включил её в список из 21 NP-полной задачи, и быстрого алгоритма для всех графов не знает никто. Но трудная в худшем случае — не значит безнадёжная на деле. Две оценки сужают поиск с двух сторон. Снизу — клика: если q вершин соединены попарно, им нужно q цветов. Сверху — любая раскраска, которую нашёл жадный способ.

Остальное делает перебор с возвратом: вершины в порядке DSatur, каждой пробуем допустимые цвета, а в тупике возвращаемся и меняем цвет предыдущей. Два отсечения делают его быстрым. Цветов больше k не берём, если проверяем, хватит ли k. И из ещё не использованных цветов пробуем только один: все они одинаковы, и раскраски, отличающиеся только их именами, — одна и та же раскраска. На кварталах Алматы перебор доказывает, что четырёх цветов хватает, осмотрев 2721 позицию.

Клика даёт ответ не всегда. Пять вершин по кругу не содержат треугольника, а цветов им нужно три. Бывают графы без треугольников, которым нужно сколько угодно цветов: в 1955 году Ян Мычельский показал, как их строить, и самый маленький такой граф с хроматическим числом 4 — граф Грёча из одиннадцати вершин — есть в тестах второй задачи. Для небольших графов есть и точный способ без перебора: формула включений и исключений считает, сколькими способами вершины покрываются k независимыми множествами, за 2^V шагов на каждое k. О нём — вторая задача.

Код

Карта кварталов: соседи — кварталы, которые обходят один и тот же отрезок улицы. Жадная раскраска в трёх порядках и в ста случайных, «наименьший последним», DSatur и точный перебор на четыре цвета — тот же DSatur, который в тупике возвращается назад. Четвёрки попарно соседних кварталов считаются прямо по спискам соседей.

blocks: 2681, neighbour pairs: 6292, most neighbours: 38
greedy, west to east              6 colours
greedy, 100 random orders         6 colours 62 times, 7 colours 38 times
greedy, most neighbours first     5 colours
smallest last                     5 colours (at most 4 neighbours coloured before a block)
DSatur                            5 colours
four blocks touch pairwise in 159 places, so 3 colours are not enough
exact search, 4 colours: possible (2721 positions)

Второй граф — из романа. Представим постановку «Войны и мира», где актёр может сыграть несколько ролей, если его персонажи ни разу не встречаются в одной главе. 46 самых заметных персонажей, две роли конфликтуют, если персонажи хоть раз в одной главе, — это раскраска, где цвет — актёр. Модель грубая: персонаж «есть в главе», если его назвали там хотя бы дважды, а названный в разговоре — не значит вышедший на сцену. Но граф получается плотным и честно трудным.

Двенадцать ролей встречаются попарно — князь Андрей, Пьер, Наташа, Николай Ростов, Кутузов, Наполеон и другие главные лица, — значит, меньше двенадцати актёров нельзя. Жадные способы берут 13–14 актёров. Перебор доказывает, что двенадцати не хватает, осмотрев 365 позиций, и находит раскладку на тринадцать за 47. Хроматическое число здесь на единицу больше клики.

roles: 46, clashing pairs: 419, most rivals: 40 (Prince Andrei)
greedy, by first appearance       14 actors
greedy, by mentions               14 actors
greedy, by rivals (Welsh-Powell)  13 actors
DSatur                            13 actors
12 roles clash pairwise, so fewer than 12 actors is impossible
exact search, 12 actors: impossible (365 positions)
exact search, 13 actors: possible (47 positions)

Сколько это стоит

Оценка для порядка Уэлша и Пауэлла доказывается так же, как первое утверждение: у i-й вершины раскрашено не больше i − 1 соседей и не больше d_i, её степени. На деле все простые способы работают за доли секунды на графах с миллионами вершин, а время уходит на точный ответ. Приблизить хроматическое число с гарантией тоже нельзя: известно, что даже ответ, верный с точностью до множителя V^1−ε, искать так же трудно, как точный.

Где работает

• Компиляторы. Переменные, которые нужны одновременно, не могут жить в одном регистре. Граф «живут одновременно» раскрашивают в столько цветов, сколько у процессора регистров; не хватило — какая-то переменная уходит в память. Так предложил делать Грегори Чайтин в 1981 году, и на этом построены распределители регистров во многих компиляторах. Подробнее — в главе базового курса о компиляторе.
• Расписания. Экзамены с общими студентами, лекции одного преподавателя, матчи одной команды — вершины, соединённые конфликтом, а цвет — день или слот. Уэлш и Пауэлл писали свою статью именно о расписаниях.
• Частоты и каналы. Соседние передатчики, точки доступа Wi-Fi, базовые станции — на разные частоты, иначе помехи. Это первая задача статьи.
• Параллельные вычисления. Если вершины одного цвета не соседствуют, их можно обновлять одновременно: никто не читает то, что пишет сосед. Так распараллеливают итерационные методы на сетках — красно-чёрная раскраска клеток шахматной доски.
• Головоломки. Судоку — раскраска графа из 81 клетки в девять цветов, где часть цветов уже дана, а соседи — клетки одной строки, столбца или квадрата.

История

В 1852 году Фрэнсис Гутри, раскрашивая карту, заметил, что ему хватает четырёх красок, и спросил, всегда ли так. В 1879 году Альфред Кемпе опубликовал доказательство, и одиннадцать лет его считали верным, пока Перси Хивуд не нашёл в нём ошибку. Из идей Кемпе Хивуд извлёк доказательство для пяти красок. Четыре краски доказали только в 1976 году Кеннет Аппель и Вольфганг Хакен: компьютер проверил почти две тысячи конфигураций, и это было первое крупное доказательство, которое человек не мог проверить вручную. В 1997 году Нил Робертсон, Дэниел Сандерс, Пол Сеймур и Робин Томас его упростили, а в 2005 году Жорж Гонтье проверил доказательство целиком в системе формальных доказательств Coq. Подробнее эта история рассказана в «Царице наук», в главе о графах.

Алгоритмическая сторона началась позже. В 1967 году Уэлш и Пауэлл предложили порядок «больше соседей — раньше» для расписаний, в 1979 году Брелаз — DSatur, а в 1983 году Дэвид Матула и Лиланд Бек описали порядок «наименьший последним» и то, как найти его за линейное время. В 1972 году Карп доказал, что хроматическое число — NP-трудная задача, и с тех пор раскраска — один из главных полигонов для эвристик и точных переборов.

Задачи

В первой задаче частоты для вышек нужно раздать с гарантией «не больше d + 1», и ни один жадный порядок, кроме «наименьшего последним», её не даёт. Во второй — точное число дней для сессии из двадцати экзаменов: клика и DSatur ошибаются, а формула включений и исключений — нет.