Как узнать по слову, поместится ли граф на торе: алгоритм за O(n)

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

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

На Gist.Science опубликовано доступное изложение моей работы «Embeddability of hieroglyphs in the torus and the intersection form». Здесь подробнее разберём один из её результатов: как по циклическому слову вычислить минимальный род поверхности и проверить вложимость в тор. Пройдём от геометрической конструкции до реализации на Python.

Граф с одной вершиной и петлями, у которого задан циклический порядок всех концов петель, будем называть иероглифом. У каждой петли два конца, хотя оба находятся в одной вершине. При обходе маленькой окружности вокруг вершины мы встречаем каждый конец один раз.

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

Хорды соединяют два конца одной петли. Их пересечения показывают чередование концов, а не дополнительные вершины исходного графа.

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

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

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

Получится связная ориентируемая поверхность с краем — утолщение исходного графа. Её можно непрерывно стянуть на вложенную копию этого графа. Однако пока нас интересует не стягивание, а край поверхности.

Край может состоять из нескольких окружностей. Обозначим их число через F. Заклеим каждую окружность диском. Получим замкнутую поверхность; её род g — число ручек. У сферы g = 0, у тора g = 1.

Ручка и дырка с краевой окружностью — разные вещи. Если из внутренности замкнутого диска вырезать два непересекающихся открытых диска, замыкания которых лежат внутри исходного диска и не пересекаются, получится поверхность с тремя компонентами края и без ручек.

Эйлерова характеристика — число вершин минус число рёбер плюс число граней в конечном клеточном разбиении поверхности. Клеточность означает, что внутренность каждой грани устроена как открытый диск. Исходный диск имеет эйлерову характеристику 1. Приклеивание каждой ленточки уменьшает её на единицу. Заклеивание каждой компоненты края диском увеличивает на единицу. Для n петель получаем:

χ = 1 − n + F.

У замкнутой связной ориентируемой поверхности рода g характеристика равна 2 − 2g. Поэтому

g = (n + 1 − F) / 2.

Это минимальный род, допускающий вложение заданного иероглифа. Почему минимальный? В любом таком вложении небольшая замкнутая окрестность графа устроена как построенный диск с ленточками. Пусть остальная часть поверхности состоит из k связных поверхностей с родами h₁, …, hₖ. Их суммарное число краевых окружностей равно F. По формуле Эйлера род всей поверхности равен g + h₁ + … + hₖ + F − k. Каждая из этих частей имеет хотя бы одну краевую окружность, поэтому F ≥ k, и род всей поверхности не меньше g. Заклеивание всех окружностей дисками достигает этой нижней границы.

Получить вложение в поверхность большего рода тоже можно: достаточно добавить ручки в области, не занятой графом. Поэтому вложимость в тор означает g ≤ 1. Рисунки, которым достаточно сферы, также можно разместить на торе.

Пусть сначала n > 0. Пронумеруем позиции слова от 0 до 2n − 1. Введём две перестановки — взаимно однозначных соответствия позиций самим себе:

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

φ(i) = σ(τ(i)) = (τ(i) + 1) mod 2n.

Цикл перестановки — последовательность позиций, которую получаем, повторяя её действие до возвращения в начальную позицию. Каждой краевой окружности соответствует один цикл φ. Значит, F — число циклов этой перестановки. Нам не требуется изображать поверхность или решать задачу поиска пути в пространстве: достаточно обходить массив.

Например, для abab пары позиций — (0, 2) и (1, 3). Перестановка φ имеет один цикл:

0 → 3 → 2 → 1 → 0

Поэтому F = 1 и g = (2 + 1 − 1)/2 = 1.

Для abcabc получаются два цикла:

0 → 4 → 2 → 0

1 → 5 → 3 → 1

Здесь n = 3, F = 2, и род снова равен единице. Третья петля не потребовала второй ручки.

Входом служит массив длины 2n: каждое целое число от 0 до n − 1, обозначающее петлю, должно встречаться ровно дважды. Такое представление позволяет использовать прямую адресацию без хеш-таблицы.

Проверим несколько примеров:

Пустой вход обрабатывается отдельно: у диска одна краевая окружность, хотя перестановка на пустом множестве не имеет циклов.

При построении массива пар каждый конец обрабатывается один раз. При обходе перестановки каждый конец также отмечается один раз. Получаем O(n) операций и O(n) памяти в модели, где доступ к массиву и операции над индексами имеют постоянную стоимость. Это оценка числа операций, а не обещание конкретного времени на любом компьютере. Код не строит геометрическое вложение: он вычисляет минимальный род и тем самым отвечает на вопрос о его существовании.

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

Есть и другой способ вычисления того же рода — по рангу матрицы, записывающей чередование букв. Её явное представление требует n² элементов, но она объясняет, почему число ручек связано с линейной алгеброй. Это тема следующей статьи.

Первоисточник: Embeddability of hieroglyphs in the torus and the intersection form, v6, леммы 1 и 6, теорема 2. Статья представляет авторское популярное изложение результатов этой работы.

Вопросы по статье и самостоятельному изучению математики можно обсудить в группе НМК ВКонтакте.