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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

объясняет Хольм.

Источник: 22century.ru

Комментарии: