Mosty królewieckie i twierdzenie Eulera o grafach
Twierdzenie Eulera o grafach
W grafie spójnym:
- cykl Eulera (droga zamknięta przechodząca przez każdą krawędź dokładnie raz) istnieje wtedy i tylko wtedy, gdy wszystkie wierzchołki mają stopień parzysty;
- ścieżka Eulera (droga otwarta o tej własności) istnieje wtedy i tylko wtedy, gdy dokładnie dwa wierzchołki mają stopień nieparzysty - i to one są jej końcami.
Zagadka, od której zaczęła się teoria grafów
Osiemnastowieczny Królewiec leżał nad rzeką Pregołą, która opływała wyspę Kneiphof i dzieliła miasto na cztery części połączone siedmioma mostami. Mieszkańcy zadawali sobie pytanie: czy da się przejść przez wszystkie siedem mostów, każdy dokładnie raz, i wrócić do punktu wyjścia?
Nikomu się to nie udawało, ale nikt nie potrafił też wyjaśnić dlaczego. W 1736 roku problem rozstrzygnął Leonhard Euler - i przy okazji stworzył nową dziedzinę matematyki.
Pomysł Eulera - od mapy do grafu
Euler zauważył, że kształt wysp, długość mostów i odległości nie mają żadnego znaczenia. Liczy się wyłącznie to, co z czym jest połączone. Zastąpił więc części miasta punktami (wierzchołkami), a mosty liniami (krawędziami) - i tak powstał pierwszy w historii graf.
Stopień wierzchołka to liczba wychodzących z niego krawędzi. W Królewcu wynosił on kolejno , , i - wszystkie nieparzyste.
Dowód
Pokaż dowódUkryj dowód
Krok 1. Warunek konieczny. Wyobraźmy sobie, że spacer istnieje. Weźmy dowolny wierzchołek nie będący początkiem ani końcem trasy. Za każdym razem, gdy do niego wchodzimy, musimy z niego wyjść - a każde wejście i wyjście zużywa inną krawędź. Krawędzie „zużywają się” więc parami, czyli stopień takiego wierzchołka musi być parzysty.
Krok 2. Początek i koniec. Dla trasy zamkniętej (cyklu) początek jest jednocześnie końcem - wyjście na starcie paruje się z powrotem na mecie, więc i tam stopień jest parzysty. Dla trasy otwartej początek ma o jedno wyjście więcej niż wejść, a koniec o jedno wejście więcej niż wyjść - oba te wierzchołki mają stopień nieparzysty, a wszystkie pozostałe parzysty.
Krok 3. Rozstrzygnięcie zagadki. W Królewcu nieparzysty stopień mają cztery wierzchołki, a dopuszczalne są zero albo dwa. Spacer nie istnieje - i nie jest to kwestia sprytu, lecz arytmetyki.
Krok 4. Warunek wystarczający (druga strona równoważności). Załóżmy, że graf jest spójny i wszystkie stopnie są parzyste. Ruszamy z dowolnego wierzchołka i idziemy, nie powtarzając krawędzi. Utknąć możemy tylko w punkcie startu - w każdym innym wierzchołku po wejściu zostaje nieparzyście wiele krawędzi, więc zawsze jest którędy wyjść. Otrzymujemy cykl. Jeśli nie objął wszystkich krawędzi, bierzemy wierzchołek tego cyklu, z którego wychodzą jeszcze nieużyte krawędzie, budujemy z nich kolejny cykl i wklejamy go w poprzedni. Powtarzamy, aż zużyjemy wszystkie krawędzie. To rozumowanie jest zarazem algorytmem - nosi nazwę algorytmu Hierholzera.
Rysowanie jednym pociągnięciem
Zabawa „narysuj bez odrywania ołówka i bez powtarzania linii” to dokładnie ten sam problem.
- Koperta (prostokąt z przekątnymi dachu) ma dwa wierzchołki nieparzyste - da się ją narysować jednym pociągnięciem, ale trzeba zacząć w jednym z nich i skończyć w drugim.
- Koperta z zamkniętą klapą (prostokąt, przekątne i dach) ma cztery wierzchołki nieparzyste - nie da się.
- Dowolna figura o wszystkich stopniach parzystych da się narysować zaczynając gdziekolwiek i wracając do startu.
Dzięki twierdzeniu Eulera odpowiedź zajmuje kilka sekund: wystarczy policzyć, ile wierzchołków ma nieparzystą liczbę wychodzących linii. Jeśli zero - tak, w dowolnym miejscu. Jeśli dwa - tak, ale tylko startując w jednym z nich. Jeśli więcej - nie.
Po co to komu
- Planowanie tras. Odśnieżanie ulic, odczyt liczników, wywóz śmieci, kontrola sieci - wszędzie tam trzeba przejechać każdą krawędź sieci, najlepiej bez powtórek. To „problem chińskiego listonosza”, którego rozwiązanie zaczyna się od twierdzenia Eulera: jeśli nieparzystych wierzchołków jest więcej niż dwa, trzeba je pododawać w pary i zdublować najkrótsze połączenia.
- Sekwencjonowanie DNA. Współczesne asemblery genomów składają odczyty w graf de Bruijna i szukają w nim właśnie ścieżki Eulera.
- Projektowanie układów scalonych i frezowanie CNC - minimalizacja pustych przejazdów głowicy to ten sam problem.
- Topologia. Praca Eulera z 1736 roku jest uznawana za początek nie tylko teorii grafów, ale i topologii - pierwszej dziedziny, w której geometria przestała zależeć od odległości.
Kto i kiedy
Leonhard Euler przedstawił rozwiązanie Akademii Petersburskiej w 1736 roku w pracy Solutio problematis ad geometriam situs pertinentis - „rozwiązanie zadania dotyczącego geometrii położenia”. Sam podał pełny dowód tylko warunku koniecznego (że spacer jest niemożliwy); uzupełnienie o warunek wystarczający opublikował Carl Hierholzer w 1873 roku.
Los obszedł się z mostami surowo: dwa zniszczyło bombardowanie Królewca w 1944 roku, dwa kolejne rozebrano przy odbudowie miasta jako Kaliningradu. Z siedmiu mostów zostało pięć - i po dzisiejszym układzie spacer Eulera jest wykonalny, bo nieparzysty stopień mają już tylko dwa wierzchołki.
Najczęstsze pytania
Dlaczego kształt miasta nie ma znaczenia? Bo o istnieniu trasy decyduje wyłącznie struktura połączeń. To pierwszy przykład rozumowania topologicznego: liczy się „co z czym”, a nie „jak daleko”.
Czym różni się cykl od ścieżki Eulera? Cykl wraca do punktu startu (zero wierzchołków nieparzystych), ścieżka kończy się gdzie indziej (dokładnie dwa wierzchołki nieparzyste).
Czy liczba wierzchołków nieparzystych może być nieparzysta? Nie. Suma wszystkich stopni równa się podwojonej liczbie krawędzi, więc jest parzysta - a to wymusza parzystą liczbę wierzchołków nieparzystego stopnia. Dlatego przypadki „jeden” albo „trzy” nie istnieją.
Czym to się różni od problemu komiwojażera? Tu odwiedzamy każdą krawędź, tam każdy wierzchołek. Różnica wydaje się kosmetyczna, a jest przepaścią: problem Eulera rozwiązuje się natychmiast, a komiwojażer jest NP-trudny.
Czy graf mostów da się „naprawić” jednym mostem? Tak. Dobudowanie jednego mostu między dwoma wierzchołkami nieparzystymi zmienia ich stopnie na parzyste - zostają dwa nieparzyste, więc pojawia się ścieżka Eulera.
Podsumowanie
- Spacer po siedmiu mostach Królewca nie istnieje, bo wszystkie cztery wierzchołki grafu mają stopień nieparzysty.
- Cykl Eulera istnieje ⟺ graf jest spójny i wszystkie stopnie są parzyste; ścieżka ⟺ dokładnie dwa wierzchołki są nieparzyste.
- Dowód warunku koniecznego to jedno zdanie: każde wejście wymaga wyjścia, więc krawędzie zużywają się parami.
- Ten sam warunek rozstrzyga zabawę „jednym pociągnięciem” i realne problemy planowania tras.
- Praca Eulera z 1736 roku uchodzi za początek teorii grafów i topologii.
