Настоящая головоломка — вот как можно смело описывать эту математическую задачу в дисциплине теория графов. Два математика из Департамента компьютерных наук Копенгагенского университета и DTU решили задачу, над которой самые быстрые компьютеры и умнейшие люди в мире бились с 1980-х годов.
В 1913 году предшественник этой широко известной математической головоломки был опубликован в «The Strand Magazine» как «Проблема трех коммунальных служб». Это заставило читателей журнала почесать в затылках и задуматься. В задаче в каждом из трех коттеджей должны быть вода, газ и электричество, а «линии» между домами и узлами коммуникаций не могут пересекать друг друга, что невозможно.
Двое ученых-информатиков, доцент Джейкоб Холм из UCPH и доцент Ева Ротенберг из DTU чуть не выдали свое решение летом 2019 года, после того как отправили исследовательскую статью, которая стала предшественником новой работы, в которой они, наконец, решили математическую загадку. Предыдущая работа математиков была посвящена динамическим графам и подробно раскрывала их свойсва, в том числе и типы обновлений. В рамках материала 2019 года исследователи предположили, что при правильном выборе динамических графов может быть решена одна из сложнейших математических головоломок.
Джейкоб Холм, один из авторов решения, говорит следующее:
Мы почти отказались от того, чтобы получить последний кусок пазла и разгадать загадку. Мы думали, что получили незначительный результат, который был интересным, но никак не решали проблему. Мы предполагали, что потребуется еще пять лет работы, в лучшем случае, прежде чем мы сможем решить головоломку.
Для упрощения понимания решения нужно немного иначе взглянуть на саму задачу. Проще говоря, головоломка состоит в том, как соединить несколько точек на графике, не позволяя соединяющим их линиям пересекаться. И как с помощью математического вычисления — алгоритма — вы можете внести изменения в обширную «сеть графов», чтобы гарантировать, что никакие линии не пересекаются, без необходимости начинать все заново. Подобные алгоритмы могут быть использованы, среди прочего, для строительства огромных дорожных сетей или крошечных компонентов компьютеров, где электрические схемы на печатных платах не могут пересекаться.
Так что там с решением? Всё гениально, и просто одновременно. В динамических графах есть два типа обновлений: можно удалить ребро и можно вставить новое ребро. Эти две операции должны выполняться пользователем, в то время как алгоритм постоянно отслеживает прорисовку сети. Этот простой алгоритм и есть рецепт решения, которое подробно описали исследователи.
Фактически подобные исследования можно отнести к разряду фундаментальных, ведь они затрагивают не только математику. Дизайн микрочипов и печатных плат, используемых во всей электронике, может стать областью, где в конечном итоге будут использованы подобные алгоритмы проектирования электронных цепей.
