Решена головоломка из области алгоритмов на графах, над которой математики бились десятки лет

+7 926 604 54 63 address
 Решение «домиков и колодцев» с одним пересечением.
Решение «домиков и колодцев» с одним пересечением.

Двое датских информатиков написали алгоритм для решения математической задачи, работа над которой тянулась десятилетиями — и после 1990-х годов в ней не было заметно никакого прогресса. Разработанный учёными алгоритм может быть применён для подобных задач в самых разных прикладных сферах.

Рассматриваемая задача относится к области математики, называемой теорией графов, и в ней идёт речь о поиске алгоритма для достижения планарности динамического графа. Плана́рный граф — это такой граф, который можно изобразить на плоскости без пересечений рёбер. Динамический граф — это такой граф, в котором во времени возможны добавления и удаления вершин и узлов.

Чтобы лучше понять, о чём идёт речь, давайте посмотрим на головоломку под названием «Домики и колодцы», которая была впервые опубликована в 1913 году, хотя математические концепции, стоящие в её основе, сформулированы ещё раньше.

Представьте себе три дома, выстроенных в ряд — например, нарисуйте их на листочке. Под ними также можно нарисовать три отдельных «колодца»: с водой, газом и электричеством.

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

Но «домики и колодцы» — это не столько головоломка, сколько пример того, как некоторые виды графов не могут быть представлены в планарном виде — у них всё равно будут пересекаться одно или больше рёбер.

Когда математики имеют дело с более сложными графами с большим количеством вершин, они с помощью теоремы Понтрягина—Куратовского могут определить, является граф планарным или нет. С 1970-х годов исследователи разрабатывают алгоритмы, позволяющие определять планарность быстрее, с меньшим уровнем сложности в рамках нотации Ландау.

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

В прошлом году информатики Якоб Хольм (Jacob Holm) из Университета Копенгагена (Københavns Universitet) и Ева Ротенберг (Eva Rotenberg) из Технического университета Дании (Danmarks Tekniske Universitet) занялись решением этой проблемы.

«Под конец мы практически потеряли надежду решить эту головоломку. Мы предполагали, что пройдёт ещё в лучшем случае пять лет работы, прежде чем мы сможем её разгадать»,

говорит Хольм.

Именно в этот момент они почти случайно поняли, что в другом исследовании, тоже посвящённом планарности графов, препринт которого был опубликован онлайн в 2019 году, они уже дали большую часть ответа на интересующий их вопрос.

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

«Мы работали над статьёй нон-стоп в течение пяти-шести недель. И в итоге текст занял более 80 страниц»,

говорит Ротенберг.

В статье описан алгоритм, который за минимальное время может установить, является ли динамический граф планарным (проще говоря, может ли он быть нарисован на листе бумаги без пересечения линий).

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

«Для решения задачи [определения планарности динамического графа] часто можно построить некоторую структуру данных, которая может быть использована для пересчёта ответа после каждого изменения графа намного быстрее, чем пересчёт ответа по новой»,

объясняет Хольм.
Комментирует Андрей Райгородский, доктор физико-математических наук, директор Физтех-школы прикладной математики и информатики МФТИ:

— Это интересный результат из области алгоритмов на графах, так как задача очень естественная, а продвижение значимое. Речь идёт о проверке планарности графа в случае, когда сам граф может динамически изменяться путём добавления или удаления ребер. Планарность — это классическое свойство графа. Например, оно очень естественно возникает в связи со знаменитой проблемой 4-х красок (покрасить карту мира в 4 цвета так, чтобы граничащие страны имели разные цвета). Если граф не меняется, то задача проверки планарности давно решена. Что значит «решена»? Это значит, что указан многочлен (полином) P(n) и придуман алгоритм, который для любого графа на n вершинах за P(n) операций отвечает на вопрос, планарен ли этот граф. Для динамического графа «время работы» ранее существовавших алгоритмов было сильно больше полиномиального, что-то типа e^{c \sqrt{n}}, где с — константа. Товарищи придумали алгоритм, работающий за e^{(log n)^c}. Это всё ещё не полином, т.к. у них с > 1, но уже очень близко. Аналогичное по силе продвижение сравнительно недавно было и в задаче о проверке изоморфизма графов. Там отличился Ласло Бабаи (Babai László), классик алгоритмической теории графов.