×

Zagadka matematyczna sprzed dziesięcioleci w końcu rozwiązana

Para duńskich informatyków rozwiązała starą matematyczną zagadkę, która pozostawała zapomniana od lat 90-tych, kiedy to nie udało się osiągnąć znaczących postępów w tej kwestii.


Teoria grafów

Abstrakcyjny problem jest częścią teorii grafów, a konkretnie dotyczy znalezienia algorytmu do rozwiązania płaskości wykresu dynamicznego. By zwizualizować problem, w 1913 roku stworzono zagadkę zwaną problemem trzech mediów.

Wyobraź sobie trzy domy ustawione w rzędzie, a pod mini trzy oddzielne media – wodę, gaz i energię elektryczną. Zadaniem jest narysowanie linii na tym prostym wykresie, które połączą trzy media z każdym domem.

Problem trzech mediów

Wydaje się banalnie proste, ale istnieje jedna zasada – żadna z linii (w sumie dziewięciu) nie może się przecinać. Czy jesteś w stanie wymyślić sposób, by połączyć wszystkie domy z mediami tak, by połączenia się nie przecinały?

Na zwykłej dwuwymiarowej kartce papieru rozwiązanie problemu trzech mediów jest niemożliwe. Zagadka nie jest jednak nierozwiązywalna, bo jest to przykład tego, jak niektóre rodzaje sieci grafów mogą mieć krawędzie łączące ich różne wierzchołki bez przecinania linii.

Algorytmy

W przypadku bardziej złożonych grafów, które obejmują więcej wierzchołków, twierdzenie Kuratowskiego pozwala matematykom określić, czy wykresy są płaskie, czy nie. Od lat 70-tych opracowywane są także algorytmy, by robić to sprawniej.

Ostatni większy przełom w dziedzinie algorytmów nastąpił w latach 90-tych, ale w kwestii problemu trzech mediów nie dokonano żadnego znaczącego postępu. Zagadkę więc porzucono, aż do zeszłego roku.

Ponowna próba rozwiązania problemu

Jacob Holm z Uniwersytetu w Kopenhadze i Eva Rotenberg z Politechniki Danii zajęli się tym problemem. Przy ostatnim elemencie prawie się poddali i właśnie ten krytyczny moment sprawił, że przypadkiem doszli do rozwiązania.

Duet zdał sobie sprawę, że skutecznie rozwiązali już większość problemu w innym badaniu dotyczącym koncepcji planarnych. W końcu spisano formalny dowód udoskonalenia algorytmu graficznego, który nie widział ulepszeń od lat 90-tych.

Wielki sukces

Opublikowane wyniki zapewniają algorytm, który zajmuje najmniej czasu obliczeniowego, aby rozwiązać kwestię, czy dynamiczny wykres może obsługiwać osadzanie płaskie. To duży postęp, ponieważ te same trudności, które pojawiają się w czymś tak prostym koncepcyjnie, jak problem trzech mediów, stają się znacznie bardziej problematyczne w innych dziedzinach.

Okazuje się, że w przypadku problemów z dynamicznymi wykresami można zbudować pewną strukturę danych, która może być wykorzystana do ponownego obliczenia odpowiedzi po każdej zmianie wykresu znacznie szybciej niż ponowne obliczenie odpowiedzi od zera. Ten wynik jest dla nas oczywiście wielkim osobistym zwycięstwem. – podsumował Holm


Mika Nojewska

Miłośniczka wszystkiego, co dziwne i ciekawe. Głównie tworzy teksty dla nauka.rocks i przed komputerem spędza więcej czasu, niż chciałaby się przyznać. W wolnym czasie odkrywa nieodkryte i próbuje opanować świat. Kocia mama i mag na 55 levelu

Może Cię zainteresować