Теория графов. Решена еще одна задача
Двое датских программистов написали алгоритм для решения математической задачи, работа над которой тянулась десятилетиями. Разработанный учёными алгоритм может быть применён для подобных задач в самых разных прикладных сферах.
Рассматриваемая задача относится к области математики, называемой теорией графов, и в ней идёт речь о поиске алгоритма для достижения планарности динамического графа.
Плана́рный граф – это такой граф, который можно изобразить на плоскости без пересечений рёбер.
Динамический граф – это такой граф, в котором во времени возможны добавления и удаления вершин и узлов.
Чтобы лучше понять, о чём идёт речь, давайте посмотрим на головоломку под названием «Домики и колодцы», которая была впервые опубликована в 1913 году, хотя математические концепции, стоящие в её основе, сформулированы ещё раньше.
Представьте себе три дома, выстроенных в ряд – например, нарисуйте их на листочке. Под ними также можно нарисовать три отдельных «колодца»: с водой, газом и электричеством.
Задача состоит в том, чтобы нарисовать на этом рисунке линии, соединяющие три колодца с каждым домом. Но есть условие: ни одна из линий (всего девять) не должна пересекаться с другими. На листе бумаги, то есть, в двумерном пространстве, решение этой задачи являлось бы планарным графом. Но такой граф построить не получится – к сожалению, либо будут пересечения, либо какие-то дома останутся обделёнными.
Но «домики и колодцы» – это не столько головоломка, сколько пример того, как некоторые виды графов не могут быть представлены в планарном виде – у них всё равно будут пересекаться одно или больше рёбер.
Когда математики имеют дело с более сложными графами с большим количеством вершин, они с помощью теоремы Понтрягина-Куратовского могут определить, является граф планарным или нет. С 1970-х годов исследователи разрабатывают алгоритмы, позволяющие определять планарность быстрее.
Последняя подвижка в этом направлении была в 1996-м, и с тех пор не было достигнуто существенного прогресса. Основная задача, решение которой определило бы значительные подвижки в этой области, – это поиск алгоритмов, способных определять планарность в динамических графах.
В прошлом году математики и программисты Якоб Хольм (Jacob Holm) из Университета Копенгагена (Københavns Universitet) и Ева Ротенберг (Eva Rotenberg) из Технического университета Дании (Danmarks Tekniske Universitet) занялись решением этой проблемы.
«Под конец мы практически потеряли надежду решить эту головоломку. Мы предполагали, что пройдёт ещё в лучшем случае пять лет работы, прежде чем мы сможем её разгадать», — говорит Хольм.
Именно в этот момент они почти случайно поняли, что в другом исследовании, тоже посвящённом планарности графов, препринт которого был опубликован онлайн в 2019 году, они уже дали большую часть ответа на интересующий их вопрос.
Поскольку решение, по сути, уже было опубликовано, в течение последующих нескольких недель математики собрались с силами и записали формальное доказательство своего вклада в задачу.
В статье описан алгоритм, который за минимальное время может установить, является ли динамический граф планарным (проще говоря, может ли он быть нарисован на листе бумаги без пересечения линий).
Это большой шаг вперед, так как с этой, казалось бы, сугубо теоретической, проблемой сталкиваются разработчики в таких прикладных областях, как проектирование микросхем или дорожное планирование, где вершин и рёбер бывает значительно больше, чем в задаче про домики и колодцы.
Источники: