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

Домики и колодцы это вершины, тропинки это рёбра. Каждый домик соединён с каждым колодцем, всего девять рёбер, и такой граф называется K3,3: полный двудольный, три на три. Граф, который можно нарисовать на плоскости так, чтобы рёбра встречались только в общих вершинах, называют планарным. Головоломка спрашивает одно: планарен ли K3,3.

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

Почему девятая тропинка не ложится

Если граф нарисован без пересечений, рёбра режут плоскость на области, их называют гранями. Внешняя, бесконечная область тоже считается гранью. Для связного рисунка всегда верна формула Эйлера: V − E + F = 2, где V это число вершин, E рёбер, F граней. Проверим на квадрате: четыре вершины, четыре ребра, две грани (внутри и снаружи), 4 − 4 + 2 = 2.

Допустим, K3,3 нарисовать удалось. У него V = 6 и E = 9, значит граней по Эйлеру F = 2 − 6 + 9 = 5. Посмотрим, хватит ли на них рёбер. Любой цикл в этом графе чередует домики и колодцы, поэтому самый короткий цикл состоит из четырёх рёбер: домик, колодец, домик, колодец. Значит, обход любой грани по границе занимает минимум четыре ребра. У каждого ребра две стороны, и каждая смотрит в какую-то грань, так что если обойти по границе все грани, каждое ребро будет пройдено ровно дважды: всего 18 шагов. На грань нужно хотя бы четыре шага, значит граней не больше 18 / 4, то есть четырёх. А по Эйлеру их пять. Рисунка не существует, сколько ни переставляй колодцы.

С K5 всё так же. Это пять вершин, каждая соединена с каждой, всего десять рёбер. Граней по Эйлеру должно быть 2 − 5 + 10 = 7. Самый короткий цикл здесь треугольник, поэтому граней не больше 20 / 3, то есть шести.

Из того же подсчёта получается общая оценка: у планарного графа без петель и кратных рёбер с тремя и более вершинами рёбер не больше 3V − 6, а если в нём нет треугольников, то не больше 2V − 4. Следствие первое: планарный граф всегда разреженный, средняя степень вершины у него меньше шести. Следствие второе, дешёвая отбраковка: если рёбер больше 3V − 6, граф непланарен, рисовать ничего не надо. В обратную сторону оценка не работает. K3,3 с девятью рёбрами в 3V − 6 = 12 укладывается с запасом и всё равно не рисуется. Среди графов на десяти вершинах подсчёт рёбер сразу отсекает 28%, хотя непланарных там больше 90%.

Виновников всего два

Удивительно, что других причин непланарности, кроме K3,3 и K5, нет. Это теорема, которую у нас называют теоремой Понтрягина-Куратовского: Куратовский опубликовал её в 1930 году, а Понтрягин, как считается, доказал раньше, но не публиковал. Граф планарен тогда и только тогда, когда в нём не спрятан K3,3 или K5. «Спрятан» значит, что рёбра могут быть подразделены: если поставить на тропинку ещё один домик, суть не изменится. Любой непланарный граф, хоть на миллион вершин, где-то внутри содержит три домика и три колодца или пять попарно связанных точек, просто растянутые по графу.

Для программиста отсюда следует приятная вещь: у ответа есть сертификат. Если граф непланарен, программа может не просто сказать «нет», а предъявить тот самый растянутый K3,3 или K5, и его можно проверить, не доверяя алгоритму. Если граф планарен, сертификат тоже есть: укладка, то есть для каждой вершины порядок, в котором вокруг неё расходятся рёбра. Проверить её помогает та же формула Эйлера: убедиться, что в укладке ровно те же рёбра, что в исходном графе, обойти по ней все грани, посчитать их и сверить с формулой (для несвязного графа в ней появляется поправка на число компонент). В тестовом прогоне библиотеки, о которой речь пойдёт дальше, каждая укладка проверяется именно так.

Как проверить быстро

Перебирать варианты рисунка бесполезно: даже одних порядков рёбер вокруг вершин астрономически много, а искать спрятанные K3,3 и K5 наивным перебором кандидатов слишком дорого. Первый алгоритм, который отвечает за время, линейное по числу вершин, опубликовали Хопкрофт и Тарьян в 1974 году. Линейное именно по вершинам тоже благодаря Эйлеру: рёбер у простого планарного графа меньше 3V, а если их больше, ответ известен, и дальше рёбра можно не считать. Речь о графе, который уже лежит в памяти списками смежности: прочитать его из файла может стоить отдельно, и к этому я ещё вернусь.

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

Через тридцать лет после Хопкрофта и Тарьяна, в 2004-м, Бойер и Мирволд опубликовали упрощённый линейный алгоритм, где единица работы одно ребро. Обход в глубину строит дерево, и его рёбра укладываются сразу. Потом вершины разбираются в обратном порядке обхода, потомки раньше предков, и для каждой по одному добавляются остальные рёбра, которые ведут к ней из её поддерева. Чтобы ребро легло, алгоритм может перевернуть уже уложенную часть или склеить две части, и делает это так, чтобы не испортить будущие вставки. Если и так нужное ребро не ложится, граф непланарен, и алгоритм выделяет растянутый K3,3 или K5 из уложенной части и ещё не уложенных рёбер. Этот алгоритм есть, например, в Boost, а SageMath оборачивает эталонную реализацию, о которой дальше.

Как поверить коду

Эталонная реализация живёт в открытом репозитории Edge Addition Planarity Suite, на C, и ведёт её сам автор алгоритма. Проверяет она себя лобовым способом: взять все графы на N вершинах, прогнать алгоритм на каждом, проверить каждый ответ и сверить итоговые счётчики с эталоном.

«Все» значит все неизоморфные простые графы, связные и несвязные: два графа, которые отличаются только нумерацией вершин, считаются одним. Генерирует их программа geng из пакета nauty, и количество растёт так: на 9 вершинах 274 668 графов, на 10 уже 12 005 168, на 11 больше миллиарда, на 12 около 165 миллиардов. Из 12 005 168 графов на десяти вершинах планарны 1 140 916, меньше одного из десяти.

Эти числа известны заранее: они лежат в OEIS, энциклопедии целочисленных последовательностей. Я пересчитал их у себя двумя программами: этой библиотекой и проверкой планарности из самого nauty. У nauty свой код, написанный по тому же методу добавления рёбер для системы компьютерной алгебры Magma. Я сравнил ответы двух программ на каждом из 12 005 168 графов по отдельности: расхождений ноль, планарных в обоих случаях 1 140 916, как в OEIS. Доказательством корректности это не является. Если обе программы ошибаются на одном и том же графе, сверка этого не увидит, а другие нумерации вершин и графы побольше этот прогон не покрывает. Но ошибку только в одной из двух программ на любом из этих 12 005 168 графов она бы поймала.

Как я пересчитывал эталонные таблицы этой библиотеки целиком, до 11 вершин и шести миллиардов прогонов, я рассказывал в статье про ревью научного софта, повторять не буду.

Как хранить двенадцать миллионов графов

Стандартный формат для таких наборов называется graph6, он из того же nauty. Каждый граф записан одной строкой печатных символов: сначала число вершин, потом верхний треугольник матрицы смежности, по биту на каждую пару вершин, пары идут по столбцам: (0,1), (0,2), (1,2), (0,3) и так далее. Биты режутся на куски по шесть, последний кусок добивается нулями, к каждому куску прибавляется 63, и получается печатный символ ASCII. K5 в graph6 выглядит так: D~{. Вся головоломка про домики и колодцы: EFz_. На десяти вершинах пар 45, это восемь символов, плюс символ на число вершин и перевод строки, 10 байт на граф. Все графы на десяти вершинах занимают 120 051 680 байт, около 120 МБ. На 11 вершинах такой файл весит уже около 12 ГБ, на 12 был бы больше двух терабайт.

graph6 тратит бит на каждую пару вершин, даже если ребра между ними нет. Мы уже выяснили, что планарные графы разреженные, а для разреженных у nauty есть sparse6: вместо матрицы список рёбер. Казалось бы, наш случай. Но набор «все графы на десяти вершинах» разреженным не назовёшь: дополнение любого графа тоже лежит в наборе, поэтому в среднем у графа 22,5 ребра из 45 возможных. И sparse6 на этом наборе проигрывает: 276 МБ против 120.

Выигрывает третий вариант, инкрементальный sparse6. Строка, начинающаяся с ;, хранит не граф, а разницу с предыдущим: список рёбер, которые надо переключить. Ребро было, значит пропадёт, не было, значит появится. Работает это потому, что geng выдаёт графы не вразнобой: соседние в его выдаче отличаются в среднем на 2,5 ребра, а в трёх случаях из четырёх не больше чем на два. В файле на десять вершин целиком записан только первый граф, пустой, а дальше идут 12 005 167 строк-разниц. Итого 65 340 449 байт, почти вдвое меньше, чем у graph6.

Чтение и запись sparse6 для простых графов, включая инкрементальный вариант, в библиотеку дописал я: теперь её прогон по всем графам читает такие файлы напрямую.

Первая моя версия чтения споткнулась на мелочи. Чтобы понять, graph6 перед ней или sparse6, программа заглядывала в первые байты файла, а потом открывала его заново и читала с начала. С обычным файлом это работает. А если графы приходят через стандартный ввод, поток назад не отматывается, и подсмотренное пропадает: на файле со всеми 34 графами на пяти вершинах прогон насчитал 33. Пришлось открывать вход один раз, а прочитанное начало возвращать обратно в поток.

У строк-разниц есть подвох. Переключение работает, пока ребро между двумя вершинами либо есть, либо нет. Но sparse6 умеет хранить мультиграфы, где между одной парой вершин бывает несколько рёбер, и для них «переключить» не определено: убрать одно ребро или все? Поэтому описание формата прямо говорит, что инкрементальные строки кратных рёбер не поддерживают, а проверять это приходится читающей стороне. Возьмём те же домики и колодцы, но от домика 0 к колодцу 3 и от домика 1 к колодцу 4 проложим по две тропинки, а следующей строкой с ; добавим одно ребро между домиками 0 и 1. copyg из nauty прочтёт второй граф без единой тропинки 0-3 и 1-4: двойные рёбра сократились по модулю два, и никто ничего не сказал. Формат такого входа не предусматривает, так что ошибкой программы это не назовёшь, но мусор на входе молча становится другим графом. Повторить можно двумя строками sparse6: :Ek?CgCQ_Q и ;b.

Диск против процессора

Становится ли проверка быстрее, раз файл почти вдвое меньше? Я замерил на MacBook Air M3, по три прогона каждого формата вперемешку, процессорное время. Одно только чтение всех двенадцати миллионов графов библиотекой занимает 4,1-4,2 секунды из graph6 и около 2,7 из инкрементального sparse6. Полный прогон проверки планарности: 22,5-22,8 секунды против 21,7-21,9. Файл меньше на 46%, чтение быстрее на треть, а весь прогон короче примерно на 4%. Отдельно измеренное чтение меньше пятой части полного теста: в полном тесте к нему добавляются копирование графа, укладка и проверка ответа. Главный выигрыш здесь в размере файла.

С одним большим графом картина обратная. Есть максимальные планарные графы: простые графы, в которые нельзя добавить ни одного нового ребра между несмежными вершинами, не потеряв планарность. При трёх и более вершинах рёбер у них ровно 3V − 6: та самая оценка, только с равенством. Я сгенерировал такой граф на 10 миллионов вершин генератором самой библиотеки, у него 29 999 994 ребра. В graph6 он занял бы больше восьми терабайт, бит на каждую пару вершин, поэтому сравнивал я текстовый список смежности и sparse6, на том же ноутбуке, по три прогона вперемешку, процессорное время. Список смежности занимает 571 МБ, пишется около 9 секунд и читается около 30. sparse6 занимает 125 МБ, пишется за 2,5 секунды и читается за 10-11. Сама укладка этого графа после чтения занимает 5-6,5 секунды, так что чтение текстового списка смежности обходится почти вшестеро дороже самой укладки.

Формат я бы выбирал по узкому месту. Для миллионов маленьких графов перешёл бы на инкрементальный sparse6 ради диска, а не ради нескольких процентов скорости. С большим графом узким местом может оказаться само чтение, как на моём графе на 10 миллионов вершин. Насчёт маленьких графов передумаю, если увижу прогон, где чтение съедает заметную долю времени, например с алгоритмом намного быстрее укладки.

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