7 278 601 292 779 396 715. Ровно столько разных хордальных графов (графов без индуцированных циклов длины четыре и больше) можно построить на двадцати вершинах, если считать структуры без имён. Это число — не головоломка для суперкомпьютера, а точный результат нового алгоритма, который смотрит на симметрию как на инструмент, а не помеху.

Представьте калейдоскоп: несколько цветных стёклышек порождают бесконечный узор, множась в зеркалах. В задаче перечисления непомеченных графов (где вершины неразличимы) симметрии — те же зеркала: перестановки вершин, оставляющие граф неизменным. Чтобы подсчитать все непомеченные графы, необходимо учесть каждое возможное отражение. И здесь вступает лемма Бёрнсайда: среднее по всем перестановкам число графов, неподвижных при данной перестановке, равно искомому числу. Беда в том, что перестановок — факториал от числа вершин, и для n=20 это 2,43×$10^{18}$ вариантов. Но алгоритм обходит эту лавину, опираясь на «испарение».

Испарение — это изящный процесс: из хордального графа раз за разом удаляются симплициальные вершины (такие, чьи соседи образуют клику), пока не останется пустой граф. В 2021 году фон Неймановский по духу подход — динамическое программирование — позволил быстро считать помеченные хордальные графы. Но как перенести его в мир симметрий? Ответ: заставить испаряться сразу целые орбиты — группы вершин, переходящих друг в друга при перестановке. Так возникает орбитное испарение.

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

Так, шаг за шагом, удалось дойти до n=20. Алгоритм не только совпал с ранее известными значениями до n=15, но и выдержал проверку через эйлерово преобразование, связывающее общие и связные графы, и прямое подтверждение для малых типов циклов. Его сложность — n в степени корень из n, намного ниже экспоненты, что оставляет задел для следующих рекордов.

Калейдоскоп симметрий не просто обновил энциклопедию OEIS. Он показал, как «испарительные» алгоритмы дружат с теорией групп, и предложил универсальную схему для других классов графов — интервальных, хордальных двудольных, графов сравнимости. В перспективе — распределённые вычисления и рывок к n=22. А метафора делительных пучков, возможно, пригодится в тестировании генеративных моделей сетей или в задачах хемоинформатики, где приходится перебирать неизоморфные молекулярные структуры.

Вернёмся к числу 7 278 601 292 779 396 715. За ним — не хаос, а строгая архитектура отражений. Каждое сочетание рёбер помнит свою орбиту в зеркальном лабиринте симметрий, и теперь этот лабиринт можно пройти без потерь.