Три коттеджа, три колодца и 12 миллионов графов

27 минут назад Прокомментировать Просмотры: 0

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

Жилища и источники выступают в роли вершин, а тропинки образуют рёбра. Каждое жилище связано с каждым источником, что в сумме дает девять рёбер; подобная структура именуется графом $K_{3,3}$ — полным двудольным графом три на три. Граф, который допускает изображение на плоскости без единого пересечения рёбер (за исключением их концевых точек), называется планарным. Суть поставленной задачки сводится к одному: является ли граф $K_{3,3}$ планарным?

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

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

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

Предположим, построить граф $K_{3,3}$ всё же удалось. В нём $V = 6$ и $E = 9$, следовательно, по формуле Эйлера количество граней должно равняться $F = 2 — 6 + 9 = 5$. Давайте выясним, хватит ли для них рёбер. Любой замкнутый контур в таком графе чередует жилища и источники, поэтому минимальный цикл состоит из четырёх рёбер: жилище, источник, жилище, источник. Это значит, что обход периметра любой грани требует как минимум четырёх шагов. У каждого ребра ровно две стороны, каждая из которых принадлежит какой-либо грани; следовательно, при обходе границ всех граней каждое ребро будет задействовано ровно дважды, что в сумме дает 18 шагов. Поскольку на каждую грань уходит по меньшей мере четыре шага, их общее количество не может превышать $18 / 4$, то есть четырёх. Однако по формуле Эйлера их должно быть пять. Искомого рисунка объективно не существует, как бы упорно вы ни переставляли колодцы.

С полным графом $K_5}$ ситуация аналогична. Он содержит пять вершин, каждая из которых соединена со всеми остальными, формируя десять рёбер. Согласно Эйлеру, граней должно быть $2 — 5 + 10 = 7$. Самый короткий цикл здесь представляет собой треугольник, поэтому граней получается не более $20 / 3$, то есть шести.

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

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

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

Для программиста отсюда вытекает приятное следствие: у любого ответа имеется официальный сертификат. Если исследуемый граф непланарен, программное обеспечение может не ограничиваться сухим отказом, а продемонстрировать тот самый видоизмененный $K_{3,3}$ или $K_5$, подлинность которого легко проверить независимо от алгоритма. Если же граф планарен, сертификатом выступает конкретная укладка — то есть порядок расхождения рёбер вокруг каждой вершины. Убедиться в её корректности помогает всё та же формула Эйлера: нужно проверить, что укладка содержит ровно те же рёбра, что и оригинал, обойти по ней все грани, подсчитать их количество и сопоставить с формулой (для несвязных графов вводится поправка на число компонентов). В тестовых прогонах рассматриваемой библиотеки каждая укладка проходит верификацию именно по этому принципу.

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

Перебирать все возможные варианты чертежа бессмысленно: количество одних лишь комбинаций порядков рёбер вокруг вершин астрономически велико, а наивный поиск скрытых структур $K_{3,3}$ и $K_5$ требует непомерных вычислительных затрат. Первый алгоритм, работающий за линейное время относительно числа вершин, был представлен Хопкрофтом и Тарьяном в 1974 году. Линейная сложность достигается во многом благодаря Эйлеру: у стандартного планарного графа рёбер меньше $3V$, а если их больше, вердикт известен заранее и дальнейший анализ рёбер не требуется. Речь идёт о графе, который уже загружен в оперативную память в виде списков смежности; процедура чтения из файла может потребовать дополнительных издержек, к которым мы ещё вернемся.

Данный алгоритм делит граф на двусвязные компоненты и формирует каждую из них путями: выбирает базовый цикл и последовательно наращивает его новыми путями, определяя, с какой стороны от уже построенного чертежа их расположить. Метод изящен, однако крайне сложен в реализации: чтобы подробно описать механизм построения самой укладки, а не просто выдачу булевого ответа, в 1996 году потребовалась отдельная научная публикация.

Спустя тридцать лет после работ Хопкрофта и Тарьяна, в 2004 году, Бойер и Мирволд предложили упрощенный алгоритм с линейной сложностью, где единицей работы выступает отдельное ребро. Поиск в глубину формирует дерево, рёбра которого укладываются незамедлительно. Затем вершины обрабатываются в обратном порядке обхода (потомки опережают предков), и для каждой из них поочередно добавляются оставшиеся рёбра, идущие из её поддерева. Чтобы очередное ребро заняло своё место, алгоритм способен разворачивать уже сформированные фрагменты или объединять их части, действуя так, чтобы не нарушить будущие вставки. Если даже при таких манипуляциях ребро не помещается, граф признается непланарным, после чего система извлекает деформированный $K_{3,3}$ или $K_5$ из уже уложенной части и оставшихся рёбер. Данный алгоритм реализован, в частности, в библиотеке Boost, а среда SageMath использует его эталонную инсталляцию, о которой пойдет речь далее.

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

Эталонный код размещен в открытом репозитории Edge Addition Planarity Suite, написан на языке Си и поддерживается непосредственным автором алгоритма. Проверка его работоспособности осуществляется самым радикальным методом: перебираются все возможные неизоморфные графы на $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. Строгим математическим доказательством корректности это, конечно, не является: если обе программы допускают ошибку на одном и том же уникальном графе, подобная сверка её не выявит, а иные нумерации и более крупные графы данный тест не охватывает. Тем не менее, баг хотя бы в одной из программ на любом из этих двенадцати миллионов вариантов был бы мгновенно пойман.

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

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

Стандартизированный формат для подобных массивов носит название `graph6` и также заимствован из пакета `nauty`. Каждый граф кодируется единственной строкой текстовых символов: сначала фиксируется число вершин, затем идет верхний треугольник матрицы смежности (по одному биту на каждую пару вершин с обходом по столбцам: $(0,1), (0,2), (1,2), (0,3)$ и т.д.). Полученная битовая последовательность разбивается на блоки по шесть бит, при необходимости дополняется нулями справа, после чего к каждому значению прибавляется 63, образуя печатный ASCII-символ. Так, граф $K_5$ в нотации `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`), программа считывала первые байты, после чего переоткрывала файл заново для обработки с самого начала. С обычными файлами этот трюк проходил успешно. Однако если графы поступали через стандартный поток ввода (`stdin`), перемотка назад невозможна, и подсмотренные байты безвозвратно терялись: при тестировании на файле с тридцатью четырьмя графами на пяти вершинах утилита насчитывала лишь 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` ради экономии диска, а не ради мизерного прироста скорости. В случае же с гигантскими графами узким местом может стать само чтение, как продемонстрировал мой пример с десятимиллионным графом. От идеи использовать инкрементальный формат для мелких структур я бы отказался лишь в том случае, если бы операция чтения составляла львиную долю времени — например, при использовании алгоритмов, работающих значительно быстрее укладки.

Если же вы всё-таки стремитесь разрешить исходную головоломку на практике, изобразите жилища и колодцы на обычной кружке с ручкой. Топологически кружка представляет собой тор, а на торе граф $K_{3,3}$ успешно чертится без единого пересечения: девятая тропинка просто проходит сквозь ручку.

Источник