Ścieżki i cykle Eulera wyjaśnione
Niektóre figury da się narysować jednym pociągnięciem, bez odrywania ołówka i bez powtarzania linii, a innych nie, choćby się próbowało bardzo długo. Nie trzeba próbować: policz linie w każdym rogu. Jeśli najwyżej dwa rogi mają nieparzystą liczbę linii, figurę da się narysować, a te rogi to miejsca, w których pociągnięcie musi się zacząć i skończyć. Leonhard Euler odkrył tę regułę w 1736 roku i założył nią teorię grafów.
Siedem mostów królewieckich
Pruskie miasto Królewiec, dziś Kaliningrad, leżało na obu brzegach rzeki Pregoły i na dwóch wyspach na niej, Kneiphofie i Lomse. Siedem mostów łączyło cztery części: po dwa z Kneiphofu do każdego brzegu, jeden między wyspami i po jednym z Lomse do każdego brzegu. Mieszczanie zastanawiali się, czy spacer może przejść przez każdy most dokładnie raz. Euler odpowiedział w pracy przedstawionej akademii w Petersburgu w 1735 roku, wydrukowanej w 1741: nie może. Jego kluczowym krokiem było odrzucenie wszystkiego poza częściami miasta i mostami między nimi, czyli dokładnie to, co robi graf: wierzchołek dla każdej części lądu i krawędź dla każdego mostu, z dwiema krawędziami tam, gdzie dwa mosty łączą te same miejsca.
Reguła stopni
Stopień wierzchołka to liczba krawędzi przy nim. Pociągnięcie przechodzące przez wierzchołek wchodzi jedną krawędzią, a wychodzi drugą, więc zużywa krawędzie tego wierzchołka parami. Tylko pierwszy i ostatni wierzchołek pociągnięcia może zachować krawędź bez pary. Dlatego wierzchołek o stopniu nieparzystym musi być początkiem albo końcem pociągnięcia. Kneiphof miał pięć mostów, a pozostałe trzy części po trzy: cztery wierzchołki nieparzyste, o dwa za dużo. Ogólnie graf spójny ma cykl Eulera, czyli pociągnięcie kończące się tam, gdzie się zaczęło, gdy każdy stopień jest parzysty, a ścieżkę Eulera, gdy dokładnie dwa stopnie są nieparzyste, od jednego do drugiego. Liczba wierzchołków nieparzystych nigdy nie wynosi jeden ani żadnej innej liczby nieparzystej: każda krawędź dodaje 2 do sumy wszystkich stopni, więc suma jest parzysta. Euler zauważył to również, a dziś nazywa się to lematem o uściskach dłoni.
Dlaczego reguła wystarcza
Euler pokazał, że figury o więcej niż dwóch wierzchołkach nieparzystych nie da się narysować, i stwierdził bez dowodu, że każdą inną figurę spójną da się. Dowód przedstawił Carl Hierholzer, niemiecki matematyk zmarły młodo w 1871 roku; jego praca ukazała się w 1873. Zacznij w wierzchołku nieparzystym, jeśli taki jest, a w przeciwnym razie gdziekolwiek, i idź nieużytymi krawędziami, dopóki się da. Ponieważ każdy inny wierzchołek ma stopień parzysty, utknąć można tylko w wierzchołku końcowym. Jeśli zostały krawędzie, niektóre dotykają dotychczasowej trasy, bo figura jest spójna. Z takiego wierzchołka idź znowu, aż utkniesz, co tym razem nastąpi z powrotem w nim, i wstaw pętlę do trasy w tym miejscu. Powtarzaj, aż nie zostanie żadna krawędź. Dowód jest zarazem najszybszym algorytmem: każdą krawędź ogląda się ustaloną liczbę razy.
Algorytm Fleury'ego: nie pal za sobą mostów
Pociągnięcie może zawieść nawet na figurze, którą da się narysować. Weź dwa trójkąty połączone jedną krawędzią i zacznij w rogu pierwszego: jeśli przejdziesz do drugiego trójkąta, zanim skończysz pierwszy, nigdy nie wrócisz. Krawędź łącząca jest mostem: jej usunięcie dzieli figurę na dwie części. Algorytm Fleury'ego z 1883 roku daje jedną regułę: w każdym wierzchołku wybierz krawędź, która nie jest mostem wśród pozostałych krawędzi, chyba że innej nie ma. Kto ją stosuje, zawsze kończy. Sprawdzanie mostu kosztuje czas, więc algorytm Fleury'ego jest wolniejszy niż Hierholzera, ale to ten, za którym można podążać ołówkiem, i to jego używa podpowiedź w aplikacji.
Naprawianie figury
Figura o k wierzchołkach nieparzystych wymaga k/2 pociągnięć. Aby narysować ją jednym, dodaje się krawędzie łączące wierzchołki nieparzyste w pary: każda nowa krawędź czyni dwa nieparzyste parzystymi. Przy k/2 − 1 krawędziach zostają dwa wierzchołki nieparzyste i wychodzi ścieżka; przy k/2 nie zostaje żaden i wychodzi cykl. Jeszcze jeden most w Królewcu, między dowolnymi dwiema z czterech części, umożliwiłby spacer, a dwa pozwoliłyby wrócić do punktu wyjścia. Historia zrobiła coś podobnego: dwa mosty przepadły w drugiej wojnie światowej, a dwa zastąpiła nowoczesna droga, i przez pięć mostów stojących dziś w starych miejscach można przejść po razie, z jednej wyspy na drugą.
Liczenie sposobów
Domek świętego Mikołaja, kwadrat z obiema przekątnymi i dachem, to niemiecka dziecięca wersja zagadki: „Das ist das Haus vom Ni-ko-laus” ma osiem sylab, po jednej na kreskę. Jego dwa dolne rogi to jedyne wierzchołki nieparzyste i z każdego z nich jest dokładnie 44 sposobów narysowania, razem 88. Dla grafów skierowanych liczbę cykli Eulera podaje wzór, twierdzenie BEST, od nazwisk de Bruijna, van Aardenne-Ehrenfest, Smitha i Tutte'a. Dla zwykłych grafów takiego wzoru nie znamy, a liczenie uchodzi ogólnie za trudne, więc aplikacja liczy małe figury, próbując każdego sposobu i pomijając kroki, które podzieliłyby figurę na dwie części.
Gdzie używa się ścieżek Eulera
Pług śnieżny, zamiatarka albo listonosz chce przejechać każdą ulicę raz i wrócić. Jeśli na każdym skrzyżowaniu schodzi się parzysta liczba ulic, wystarczy cykl Eulera; w przeciwnym razie niektóre ulice trzeba przejechać dwa razy, a wybór najtańszych to problem chińskiego listonosza, postawiony przez Meigu Guana w 1962 roku. Ploter pisakowy albo wycinarka laserowa oszczędza czas, rysując jak najwięcej linii bez odrywania narzędzia. W sekwencjonowaniu genomu miliony krótkich fragmentów DNA składa się, szukając ścieżki Eulera w grafie de Bruijna, w którym każdy fragment jest krawędzią. A ta sama reguła podpowiada, które rysunki w zeszycie z łamigłówkami warto próbować.
Sprawdź sam
Otwórz wyszukiwarkę ścieżek Eulera, aby samodzielnie obrysować dwanaście figur, od Królewca w 1736 roku i dzisiaj po gwiazdy, kwadraty w kwadratach i sześcian, albo narysuj własne z krawędziami równoległymi. Wierzchołki nieparzyste są wypełnione, każdy wierzchołek pokazuje swój stopień, a reguła stopni pod figurą mówi, co jest możliwe i jakie krawędzie by ją naprawiły. Gdy utkniesz, aplikacja powie, czy zacząłeś w złym wierzchołku, czy przeszedłeś przez most za wcześnie, i w którym kroku. Podpowiedź podaje bezpieczną krawędź, a Rozwiąż rysuje figurę algorytmem Fleury'ego, pokazując sprawdzanie mostu, albo Hierholzera, pokazując każde wstawienie.
Często zadawane pytania
Czy ścieżka Eulera to to samo co ścieżka Hamiltona?
Nie. Ścieżka Eulera używa każdej krawędzi raz i może odwiedzać wierzchołek wiele razy; ścieżka Hamiltona odwiedza każdy wierzchołek raz i nie musi używać każdej krawędzi. To, czy graf ma ścieżkę Eulera, rozstrzyga od razu policzenie wierzchołków nieparzystych, ale dla ścieżek Hamiltona nie znamy szybkiego testu, a znalezienie jednej to jeden z klasycznych trudnych problemów informatyki.
Czy reguła stopni działa, gdy dwa wierzchołki łączy więcej niż jedna krawędź?
Tak. Każda krawędź liczy się do stopnia obu swoich końców, niezależnie od tego, czy inna krawędź łączy te same dwa wierzchołki. Królewiec jest takim multigrafem, z dwoma mostami z Kneiphofu do każdego brzegu. Krawędź od wierzchołka do niego samego, pętla, dodaje 2 do jego stopnia i nigdy nie zmienia jego parzystości.
A co z ulicami jednokierunkowymi?
W grafie skierowanym każda krawędź ma kierunek, a reguła porównuje krawędzie wchodzące do każdego wierzchołka z wychodzącymi. Cykl Eulera istnieje, gdy w każdym wierzchołku tyle samo krawędzi wchodzi, co wychodzi, a krawędzie trzymają się razem, a ścieżka Eulera, gdy jeden wierzchołek ma o jedną krawędź wychodzącą więcej, inny o jedną wchodzącą więcej, a wszystkie pozostałe są zrównoważone. Ścieżka biegnie wtedy od pierwszego do drugiego.
Czy może istnieć figura o dokładnie jednym wierzchołku nieparzystym?
Nie. Stopnie wszystkich wierzchołków sumują się do podwojonej liczby krawędzi, bo każda krawędź ma dwa końce. Ta suma jest parzysta, więc liczba nieparzystych stopni w niej też musi być parzysta: 0, 2, 4 i tak dalej, nigdy 1 ani 3.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz wyszukiwarkę ścieżek Eulera