Стара математическа загадка е окончателно решена

Ваня Милева Последна промяна на 20 август 2020 в 00:01 17257 0

Представяне на проблема с трите комунални услуги с кръстосани линии. (Koko90 / Wikimedia Commons / CC BY-SA 3.0)

Изследователи успяват да решат математически проблем от 80-те години от миналия век и показват голяма част от решението в научна статия.

Решението може да се използва за подобряване на бъдещите телефони и компютри.

Двама компютърни учени, доц. Джейкъб Холм (Jacob Holm) от Копенхагенския университет UCPH и доцент Ева Ротенберг (Eva Rotenberg) от Датския Технически университет DTU, решават дългогодишна математическа главоблъсканица, след като десетилетия изследователите не успяха да постигнат значителен напредък по въпроса от 90-те години.

Въпросният абстрактен проблем е част от т.нар. теория на графите и се отнася конкретно до предизвикателството да се намери алгоритъм за решаване на пларността на динамичен граф. Това може да звучи малко отвлечено, но има много по-забавен и достъпен начин за осмисляне на същите идеи.

От 1913 г. - въпреки че математическите понятия вероятно могат да бъдат проследени много по-далеч - бе публикувана главоблъсканица, наречена проблемът с трите комунални услуги.

Проблемът с трите комунални услуги

През 1913 г. предшественикът на сега решаваната математическа главоблъсканица е публикуван в списание „Strand“ като „Проблемът с трите комунални услуги“. Той затрудни читателите на списанието. При проблема всяка от три къщи трябва да има вода, газ и електричество, докато "проводите" между къщите и водата, електричеството и газта трябва да не се пресичат една друга - което не е възможно.

Но когато математик установи, че нещо е невъзможно, той мисли: Мога ли да докажа, че наистина е невъзможно? И мога ли да променя условията, за да направя това възможно? 

Решение на задачата за трите комунални услуги с едно пресичане. Кредит: CMG Lee / Wikimedia Commons / CC BY-SA 4.0 

На обикновен, двуизмерен лист хартия, като пример за планарен граф, не е възможно да се реши проблема с трите комунални услуги. 

Но проблемът с трите комунални услуги не е главоблъсканица, който трябва да бъде решена, а по-скоро пример за това, че някои видове графови мрежи може да не са планарни - т.е. могат да имат ребра (линии), свързващи различните си върхове (къщи и комунални услуги) без линиите да се пресичат. 

Върху тор (поничка) задачата за трите комунални услуги се решава без пресичане. Кредит: http://mathforum.org/dr.math/faq/faq.3utilities.html

За теорията на графите

Графът е много проста конструкция, използвана за моделиране на неща, които могат да бъдат описани като обекти и връзките между тях. Теорията на графите е едновременно област на математиката и важен инструмент в компютърните науки.

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

Според формулата на Ойлер за всяка планарна графика, площи - ребра + върхове винаги е равен 2. Нека видим на следната фигура.

За да се удовлетвори формулата на Ойлер, решението трябва да има най-малко 5 лица с поне 4 страни, което означава, че има поне 10 ребра. И в същото време трябва да има 9 ребра, както се изисква от изложението на проблема. По този начин такова решение не съществува.

Решение между линиите

Най-просто казано, задачата е за това как да се свържат поредицата точки в графа, без свързващи ги линии да се пресичат. И как с математически инструмент - алгоритъм - може да се правят промени в обширна "мрежа от графи", за да се гарантира, че никоя линия няма да се пресача, без да се налага да се започва отначало. Това са свойства, които могат да се използват, наред с други неща, за изграждане на огромни пътни мрежи или на във вътрешността на компютрите, където електрическите вериги на платките не може да се пресичат.

За решението

При по-сложни графи, които включват повече върхове, теоремата на Куратовски помага на математиците да определят дали графите са планарни или не и от 70-те години на миналия век изследователите също създават алгоритми, които да направят същото по-бързо.

Независимо от това, след един последен алгоритмичен пробив през 90-те години на миналия век, в тази област не е постигнат съществен напредък, поне не по отношение на алгоритмите, които могат да решат за динамични (променящи се) графи.

Но миналата година компютърните учени Джейкъб Холм от Университета в Копенхаген и Ева Ротенберг от Техническия университет в Дания се захващат отново с проблема.

„Почти се бяхме отказали да вземем последното парче и да сглобим пъзела“, разказва Холм. "Предполагахме, че ще има още пет години работа, в най-добрия случай, преди да успеем да разрешим загадката."

Има два вида актуализации в динамичните графи - да се изтрие линия и да се постави нова линия. Тези две операции трябва да бъдат направени от потребителя, докато алгоритъмът следи чертежа на мрежата непрекъснато. Това е алгоритъмът, за който изследователите са открили рецептата.

Те почти случайно разбират, че вече ефективно са решили по-голямата част от проблема в друго изследване - статия - препринт на свързани планарни концепции, която двамата пускат онлайн през 2019 г. След това, през следващите седмици те пишат официално доказателство за подобрението на графичния алгоритъм, който не е пипан от 90-те години.

„Работихме над статията без прекъсване в продължение на пет до шест седмици. И в крайна сметка запълнихме повече от 80 страници“, разказва Ротенберг.

Резултатите, публикувани сега, предоставят алгоритъм, за който е нужно най-малко изчислително време, за да се реши въпросът дали динамичният граф - обект на вмъкване и изтриване на ребрата, свързващи неговите върхове - може да поддържа планарно вграждане. (Най-просто казано, дали може да се нарисува върху лист хартия, без да се пресичат линии.)

Това са свойства, които могат да се използват, наред с други неща, за изграждане на огромни пътни мрежи или на във вътрешността на компютрите, където електрическите вериги на платките не може да се пресичат. Кредит: pikist.com

Това е голям напредък, тъй като същите трудности, представени в нещо толкова концептуално просто като проблема с трите комунални услуги, се срещат и стават много по-непреодолими в области като проектиране на микрочипове или планиране на пътища, където са включени много повече върхове, отколкото просто три къщи и три комунални услуги.

"Оказва се, че при проблеми с динамичните графи често е възможно да се изгради някаква структура от данни, която може да се използва за преизчисляване на отговора след всяка промяна в графа много по-бързо, отколкото преизчисляване на отговора от нулата", обяснява Холмс .

"Този резултат разбира се е огромна лична победа за нас."

Справка: 

Fully-dynamic planarity testing in polylogarithmic time
Jacob Holm, Eva Rotenberg

Publication:STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingJune 2020 Pages 167–180 https://doi.org/10.1145/3357713.3384249

Източник: 

Math Riddle From Decades Ago Finally Solved After Being Lost And Found by Researchers, sciencealert

Graph theory: Solution to '3 utilities problem' could lead to better computers,  University of Copenhagen

Най-важното
Всички новини
За писането на коментар е необходима регистрация.
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!

Няма коментари към тази новина !