Problem siedmiu mostów

Problem siedmiu mostów (ang. Seven Bridges of Königsberg problem) jest klasycznym zadaniem z dziedziny teorii grafów, które zapoczątkowało rozwój tej dyscypliny. Problem został sformułowany w XVIII wieku i rozwiązany po raz pierwszy przez szwajcarskiego matematyka Leonarda Eulera.

Historia

W 1726 roku w pruskiej mieście Königsberg (obecnie Kaliningrad) znajdowało się siedem mostów łączących cztery części wyspy i dwóch brzegu rzeki Pregel. Mieszkańcy miasta zadawali sobie pytanie, czy istnieje przejście, które pozwoli przejść każdy most dokładnie raz, wracając jednocześnie do punktu wyjścia.

Formalizacja problemu

Euler przedstawił problem w postaci abstrakcyjnej, zamieniając obszary lądowe na wierzchołki, a mosty na krawędzie. W wyniku otrzymano graf, w którym:

• każdy wierzchołek reprezentuje jedną z czterech części miasta,
• każda krawędź (most) łączy dwa wierzchołki,
• graf jest nieskierowany i może posiadać wielokrotne krawędzie.

Problem sprowadza się do znalezienia w tym grafie drogi eulerowskiej – ciągu krawędzi, w którym każda krawędź jest odwiedzona dokładnie raz.

Rozwiązanie Eulera

Euler udowodnił następujące kryterium:

1. Graf ma drogi eulerowskie wtedy i tylko wtedy, gdy jest spójny (po usunięciu wierzchołków izolowanych) i wszystkie jego wierzchołki mają parzysty stopień.
2. Graf ma ścieżkę eulerowską (rozpoczynającą się w jednym wierzchołku i kończącą w innym) wtedy i tylko wtedy, gdy jest spójny i dokładnie dwa wierzchołki mają nieparzysty stopień.

W grafie reprezentującym siedem mostów wszystkie cztery wierzchołki mają nieparzysty stopień (3, 3, 3 i 5). Z atem spełniony jest warunek, że istnieją więcej niż dwa wierzchołki o nieparzystym stopniu, co oznacza, że droga eulerowska nie istnieje. W wyniku wniosek: przejścia, które przechodziłoby każdy most dokładnie raz, nie ma.

Znaczenie i dziedzictwo

Rozwiązanie problemu siedmiu mostów otworzyło drogę do rozwoju grafów i powstało podwaliny pod nowoczesną algorytmikę. W kolejnych latach wyprowadzono wiele pokrewnych pojęć, m.in.:

• droga eulerowska i cykl eulerowski,
• problem Hamiltona – poszukiwanie ścieżki przechodzącej przez wszystkie wierzchołki,
• teoria planarności grafów,
• zastosowania w logistyce, sieciach komputerowych i analizie społecznej.

Powiązane pojęcia

W literaturze encyklopedycznej problem siedmiu mostów jest często wymieniany razem z innymi klasycznymi zadaniami: problem królików, problem Retka, problem komiwojażera. Jest także ilustracją pojęć graf połączony, graf ważony i cyklu hamiltonowskiego.

Bibliografia

• L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae, 1736.
• J. E. Hopcroft, R. M. Karp, VLSI layout and planar graphs, 1970.
• D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001.

Problem siedmiu mostów pozostaje jednym z najbardziej rozpoznawalnych przykładów zastosowania matematyki czystej do rozwiązania praktycznego zagadnienia, a jednocześnie wspaniałą ilustracją, jak proste pytanie może inspirować rozwój całej gałęzi nauki.