На втором курсе университета (2011-2012 учебный год) нам объявили что пора уже задумываться о выборе научного руководителя, поскольку зима третий курс близко. Как раз в том учебном году к нам в филиал впервые приехал мой будущий научный руководитель и провел нам великолепный курс по теории графов. Меня так увлекла его манера преподавания, и тема была настолько интересна, что я не задумываясь после окончания курса (а курсы от приезжих специалистов читались нам в сжатые сроки, примерно за месяц) обратился с просьбой взять надо мной шефство. С тех самых пор научный руководитель у меня не менялся, но правда по науке графами много заниматься не пришлось. Тем не менее, теплые чувства к теории графов никуда не пропали, а потому часто возникает желание окунуться в графовые задачки и найти что-то познавательное (хотя в этой области уже все давно украдено решено за нас).
Пару недель назад в голову пришла мысль посмотреть на заезженную вдоль и поперек задачу о правильной вершинной раскраске планарного графа с алгоритмической точки зрения. А на помощь мне пришла моя бывшая ученица, на текущий момент без пяти минут абитуриент Матвеева Ася, которая любезно согласилась позаниматься в свободное время вершинными раскрасками, а так же оформить демонстрационный код для сегодняшней заметки. Ася очень талантливая и просто замечательная, уверен, что её ждут большие успехи во всем. Весь код и почти все иллюстрации в сегодняшней статье целиком и полностью являются ее заслугой!
Если вам не доводилось слышать про математические графы, то, скорее всего, словосочетание «раскраска графа» вызовет примерно такие ассоциации:
Такие раскраски, без сомнения, крайне увлекательны, но сегодня не про них. Обратимся к математике и коротко обозначим суть задачи о правильной раскраске планарных графов:
Графом называется два множества: множество вершин и множество ребер между некоторыми из этих вершин (ребро соединяет всегда пару различных вершин). Планарным графом называется граф, который можно изобразить на плоскости без пересечений ребер. Правильная вершинная раскраска графа — это такое правило назначения цветов (или просто каких-то меток) вершинам графа, что ни одно ребро не соединяет две одноцветные вершины.
Без примеров это может быть не совсем ясно, но теория графов прекрасна тем, что она почти всегда очень хорошо визуализируется. Чтобы лучше понять планарность, для начала следует посмотреть на примеры непланарных графов. Два самых известных непланарных графа это полный граф на пяти вершинах (K5) и полный двудольный граф с тремя вершинами в каждой доле (K3-3), они изображены ниже. Если внимательно присмотреться, станет понятно, что нельзя так выгнуть ребра или подвинуть вершины, чтобы не было пересечений между ребрами на плоскости:
Эти два графа, на самом деле, являются в некотором смысле ключевыми, о чем говорит нам теорема Понтрягина-Куратовского, но углубляться в это сейчас не будем.
Легко представить себе пример планарного графа, хотя бы банальный граф-треугольник. Но давайте сразу посмотрим на пример посложнее, а заодно разберемся с тем, что такое правильная вершинная раскраска. Ниже приведен пример планарного графа из семи вершин и его правильной вершинной раскраски в шесть цветов:
Планарные графы интересны нам с той точки зрения, что ими могут быть представлены, к примеру, карты регионов и стран. В самом деле, на плоской карте можно номерами вершин обозначить страны, а ребро между вершинами будет обозначать наличие границы между двумя странами. Так, например, на графе, представленном выше, можно считать, что страна с номером «2» имеет границу со странами «0», «1», «3» и «5», но не граничит со странами «6» и «4». Поскольку карту можно изобразить на плоскости, то и граф, соответствующий карте, будет планарным.
С математической точки зрения интересна задача нахождения минимально возможного количества цветов для заданного графа, чтобы правильно покрасить его вершины. Такое число называется хроматическим, а про раскраски графов (необязательно планарных) можно ещё очень много интересных вещей почитать. Применений у хроматического числа масса, одно из них это составление правильного расписания выполнения задач при определенных условиях, но об этом рекомендую почитать отдельно.
В любом хорошем курсе по теории графов обязательно освещена тема правильной вершинной раскраски и отдельное внимание уделяется раскраске планарных графов. Самая популярная тут это теорема о правильной раскраске планарного графа в четыре цвета, этот результат доказан на сегодняшний день не «на бумаге», а только при помощи компьютерного моделирования (и поэтому у многих скептиков вызывает подозрения). Но эту одиозную теорему в сегодняшней заметке мы не будем затрагивать, поговорим о вещах попроще (доказательства представленных теорем можно найти не только по ссылкам, но и почти в любом учебнике по теории графов).
Первая и самая простая теорема, на которую сегодня взглянем, это теорема о шести красках. Утверждается что планарный граф обязательно можно правильно раскрасить в шесть цветов. Идея доказательства довольно проста: из формулы Эйлера несложным образом выводится тот факт, что в планарном графе всегда существует вершина степени не больше пяти (степенью вершины называется количество её соседей). Удаляя такую вершину из графа (и запоминая что мы её удалили), мы всё ещё получим планарный граф, но с уже меньшим числом вершин. Многократно применяя это размышление, можно уменьшить размер задачи до графа с шестью вершинами, который, очевидно, можно будет правильно раскрасить в шесть цветов. Дальше дело за малым — необходимо по одной возвращать те вершины, что были удалены, и окажется что нам всегда удастся покрасить новую вершину в какой-то из шести цветов, не нарушая правильной раскраски (поскольку соседей у неё было не больше пяти). В тексте это может быть не очень ясно, динамика работы принципа изображена на иллюстрациях ниже. Этот граф мы уже видели в самом начале данной статьи:
Это простое и изящное размышление несложно завернуть в код, для полного осознания:
Итак, мы уже знаем, что хватает шести цветов. Раньше было упомянуто про четыре цвета. Что же с пятеркой? Оказывается, теорему о том, что для правильной вершинной раскраски планарного графа пяти красок будет достаточно тоже можно доказать «на бумаге». Правда, здесь потребуется некоторая дополнительная «возня». Первые шаги будут аналогичны случаю шести красок, мы постепенно будем удалять вершины из графа, пока задача не схлопнется в граф на пяти вершинах, который, очевидно, можно раскрасить в пять цветов. Далее так же начнем возвращать вершины по одной, однако здесь возникает нюанс: может так случиться, что все пять соседей уже раскрашены в разные цвета, и новую вершину не во что красить, если мы не хотим нарушать правильность раскраски. Однако ситуацию спасает тот факт, что обязательно найдутся две вершины среди соседей этой новой вершины, цвета которых можно будет отождествить (правда при этом может понадобиться перекрасить часть уже раскрашенного графа). За подробностями отправляю читать полный текст доказательства, а мы посмотрим на простой пример:
Алгоритм становится несколько сложнее, поскольку теперь необходимо иногда «пробегать» по соседям в поисках такой цепочки, которую можно перекрасить. Поскольку для каждой новой добавленной вершины длина такой цепочки может доходить в худшем случае почти до общего числа вершин в графе, алгоритм приобретает квадратичную сложность. В коде это будет выглядеть примерно так:
Дочитав до этого места, вы вполне могли задаться вопросом: «А можно ли сделать раскраску в пять цветов быстрее чем за квадратичное время?». В конце концов, если число вершин очень велико, а раскрасить граф ну очень хочется, долго ждать это так себе вариант.
Оказалось что сделать это можно, и еще в 1980 году был опубликован алгоритм, который решает задачу о раскраске планарного графа в пять цветов асимптотически за линейное время. Но, как говорится, есть нюанс...
В вышеупомянутой статье японских исследователей от 1980 года скрыты некоторые подводные камни, которые можно обнаружить только внимательно прочитав материал. Во-первых, для линейного алгоритма предполагается, что мы знаем некоторую планарную укладку заданного графа и задаем его на вход алгоритму списками смежности, причем для каждой вершины в списке смежности соседи перечислены либо по часовой стрелке, либо против часовой (относительно заданной планарной укладки). Во-вторых, списки смежности, которыми задается граф, совсем не просты — предполагается, что удаление вершины степени d из графа можно при помощи этих списков выполнять за O(d), а «схлопывать» две вершины степеней d1 и d2 можно за O(d1+d2). В варианте списка смежности, который первым приходит на ум, т.е. в массиве двусвязных списков, так сделать не получится, но, если исхитриться, и «промоделировать» списки смежности ассоциативными массивами (нам обязательно нужен будет порядок обхода соседей), можно достичь желаемой асимптотики.
Немного огорчило, что в статье об этом ничего не сказано и совсем ничего не упоминается в аннотации к статье требования о наличии планарной укладки, но допустим, что мы согласились с такими правилами игры.
Если коротко, метод, предложенный в статье, пытается достичь ситуации, схожей с подходом в теореме о шести красках, — добиться, чтобы у новой вершины всегда оказывалось не более четырех цветов по соседству. Авторы модифицируют процесс удаления таким образом, что помимо удаления вершин с не более чем пятью соседями, рассматриваются также вершины с шестью соседями, и некоторые пары или тройки вершин в процессе «схлопываются», чтобы гарантировать, что они в итоге будут покрашены в один цвет на самом нижнем ярусе рекурсивных вызовов. Так обеспечивается наличие «свободного» цвета в процессе восстановления графа. При этом количество вершин, которые мы будем в процессе «схлопывать», достаточно велико для обеспечения линейной асимптотики работы, а выбираются эти вершины таким образом, чтобы не нарушалась планарность при переходе к новому графу. Размышления довольно хитрые, в коде они выглядят примерно так:
Хочется отметить, что код демонстрационный, а потому рекурсивный, и он вполне может не отрабатывать на слишком большом количестве вершин. Но никто не мешает желающим «избавиться» в этом коде от рекурсии (достаточно симулировать стэк вызовов своим собственным).
На закуску мы сравнили производительности алгоритмов раскраски из последнего листинга и «наивного» листинга основанного на теореме. В качестве тестовых данных выбирался заведомо планарный граф, соответствующий квадратной декартовой сетке фиксированного размера. Результаты замеров производительности выглядят довольно оптимистично, изображено время исполнения 10 запусков для каждого фиксированного размера:
На этом сегодня все, такие вот любопытности в раскрасках графов!
Хочется еще раз выразить благодарность Асе Матвеевой за её неподдельный интерес к теме и большие старания, будущему её научному руководителю крупно повезёт. Огромных успехов!
А Вам спасибо за внимание, до новых статей! Пусть жизнь будет окрашена только в яркие краски, а их число будет сильно больше чем хроматическое у планарных графов.
Не забывайте подписываться и ставить лайки если понравился материал!
