Algorytm Fleury’ego
Algorytm Fleury’ego to metoda, która umożliwia znalezienie cyklu Eulera w grafie eulerowskim.
Poszukiwanie cyklu Eulera w grafie
Rozważmy graf G, który jest grafem eulerowskim. Aby odnaleźć cykl Eulera rozpoczynający się od konkretnego wierzchołka v, należy przeszukiwać ścieżkę cykliczną, eliminując napotkane krawędzie i zbierając odwiedzane wierzchołki na stosie. Dzięki temu można:
- zawrócić po ścieżce i wydrukować napotkane krawędzie,
- sprawdzić, czy dla każdego wierzchołka dostępne są ścieżki prowadzące z innych kierunków (które można połączyć w jedną ścieżkę).
Algorytm wymaga utworzenia lokalnej kopii grafu, aby można było usunąć poszukiwaną ścieżkę. Dlatego klasa definiująca abstrakcyjny typ danych graf powinna mieć konstruktor kopiujący oraz tworzyć pełną i odseparowaną kopię grafu. W założeniu algorytmu przyjęto, że tak jest. W przeciwnym razie, po zakończeniu działania algorytmu, należałoby ponownie przeszukać ścieżkę Eulera, dodając z powrotem wszystkie jej krawędzie.
Pseudokod algorytmu
W poniższym przykładzie algorytm zwraca wynik, dodając do pewnej sekwencyjnej struktury kolejne wierzchołki w odwrotnej kolejności niż te znajdujące się na ścieżce. Struktura ta może być dowolna i nazywana jest po prostu „rozwiązaniem”. Zakłada się również, że dostępny jest stos S, na którym można przeprowadzać operacje PUSH i POP oraz sprawdzać, czy stos jest pusty za pomocą funkcji EMPTY. Jeśli graf G ma konstruktor kopiujący, a wierzchołkiem początkowym jest v, a końcowym w, to działanie algorytmu można przedstawić w następujących krokach:
- IF NOT G jest grafem eulerowskim THEN END
- Przypisz G’ = G
- Dopisz do rozwiązania wierzchołek v
- WHILE wierzchołek v nie jest izolowany DO
- 5. Przypisz w indeks dowolnego wierzchołka incydentnego z v
- 6. S.PUSH v
- 7. Usuń z G’ krawędź w – v
- 8. Przypisz v = w
- END DO
- IF NOT S.EMPTY THEN
- 10. Przypisz v = S.POP
- 11. Dopisz do rozwiązania wierzchołek v
- 12. GO TO 4.
- ELSE END
Dowód poprawności algorytmu
Podczas poszukiwania cyklu Eulera w grafie eulerowskim G, wierzchołek końcowy w jest tożsamy z wierzchołkiem początkowym v. Graf G jest spójny, a stopień każdego wierzchołka jest liczbą parzystą. Poprawność algorytmu zostanie udowodniona przy użyciu indukcji względem liczby krawędzi.
Algorytm rozpoczyna się od stworzenia lokalnej kopii G’ grafu G oraz dodania końcowego wierzchołka do odwrotnej listy wierzchołków, które należy kolejno odwiedzać, aby odnaleźć cykl Eulera w grafie G.
W krokach 4 – 8 algorytmu, zaczynając od danego wierzchołka v, indeks aktualnie rozpatrywanego wierzchołka odkładany jest na stosie, następnie wybierana jest dowolna krawędź z nim incydentna, przechodząc do kolejnego wierzchołka i usuwając tę krawędź z grafu. Operacja ta powtarzana jest aż do momentu, gdy dotrze się do wierzchołka, który nie ma już więcej krawędzi.
Proces ten musi zakończyć się w wierzchołku v. Dzieje się tak, ponieważ jeśli stopnie wszystkich w wierzchołków w grafie są parzyste, to jeżeli obecnie rozpatrywany wierzchołek jest różny od wierzchołka początkowego, w grafie znajdują się dokładnie dwa wierzchołki o nieparzystych stopniach – początkowy oraz aktualny. Skoro rozpatrywany wierzchołek ma nieparzysty stopień, można go opuścić, przechodząc do kolejnego. Stąd wynika, że jeżeli wierzchołka nie można opuścić, to jest on wierzchołkiem początkowym.
Jedną z możliwości jest przejście całego cyklu Eulera w punktach 4 – 8. Jeśli to nastąpi, następuje koniec dowodu, ponieważ późniejszy powrót do pętli WHILE w kroku 12 nic nie zmienia. W przeciwnym razie, wszystkie pozostałe w grafie wierzchołki mają parzyste stopnie (ponieważ usunięto z każdego parzystą liczbę krawędzi), choć mogą nie być połączone. Oznacza to, że każda spójna składowa grafu G’ pozostała po usunięciu pewnego cyklu w krokach 4 – 8 ma cykl Eulera. Usunięta ścieżka cykliczna łączy te trasy w cykl Eulera dla oryginalnego grafu. Gdyby tak nie było, suma pozostałych spójnych składowych oraz usuniętego cyklu nie byłaby grafem spójnym, co przeczy założeniu.
W krokach 9 – 12 opisanego algorytmu, zdejmując ze stosu kolejne wierzchołki, przemierza się (od końca, co nie zmienia dowodu) ścieżkę cykliczną, zbaczając z niej w każdym przypadku, gdy natrafi się na nieizolowany wierzchołek (gdy spełniony jest warunek 4). Następnie aktualnie zdjęty ze stosu wierzchołek przyjmuje się za wierzchołek początkowy i powracając do kroku 4, rekurencyjnie wywołuje się algorytm znajdujący trasę Eulera dla spójnej składowej. Każda taka podtrasa jest właściwą trasą Eulera, która prowadzi z powrotem do wierzchołka na ścieżce cyklicznej, na której rozpoczęła się, co wynika z indukcyjnego założenia dowodu.
Każda podtrasa może stykać się ze ścieżką cykliczną wielokrotnie. W takim przypadku jednak każda podtrasa jest przemierzana tylko raz – gdy się na nią wejdzie.
Linki zewnętrzne
Eric W.E.W. Weisstein, Fleury’s Algorithm, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).
