Решена головоломка из области алгоритмов на графах, над которой арифметики бились 10-ки лет — uzkinobiz.ru

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

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

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

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

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

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

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

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

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

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

гласит Хольм.

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

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

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

гласит Ротенберг.

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

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

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

разъясняет Хольм.

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

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