Algorytm Fleury’ego

Algorytm Fleury’ego – algorytm pozwalający na odszukanie cyklu Eulera w grafie eulerowskim.

Poszukiwanie cyklu Eulera w grafie edytuj

Dany jest graf G taki że G jest grafem eulerowskim. Aby znaleźć cykl Eulera wiodący od określonego wierzchołka v, można przemierzać ścieżkę cykliczną, usuwając napotkane krawędzie i gromadząc na stosie napotkane wierzchołki, dzięki czemu uzyskuje się możliwość:

zawrócenia po ścieżce i wydrukowania ich krawędzi
sprawdzenia, czy dla każdego wierzchołka istnieją ścieżki prowadzące z innych stron (które można połączyć w jedną ścieżkę).

Algorytm wymaga stworzenia kopii lokalnej grafu, aby móc z niej usunąć poszukiwaną ścieżkę. Dlatego też klasa definiująca abstrakcyjny typ danych graf powinna posiadać konstruktor kopiujący oraz tworzyć kompletną i odseparowaną kopię grafu. W implementacji algorytmu przyjęto, że tak jest. W przeciwnym wypadku po zakończeniu działania algorytmu należałoby jeszcze raz przemierzyć ścieżkę Eulera, ponownie dodając do grafu wszystkie jej krawędzie.

Pseudokod algorytmu edytuj

W poniższym przykładzie algorytm zwraca wynik, wpisując do pewnej sekwencyjnej struktury kolejne wierzchołki w odwrotnej kolejności, niż znajdują się na ścieżce. Struktura ta może być całkowicie dowolna i jest określana jako po prostu „rozwiązanie”. Przyjęto również, że dostępny jest stos S, na którym można wykonywać operacje PUSH i POP oraz sprawdzać, czy stos jest pusty, funkcją EMPTY. Jeśli zadany graf G posiada konstruktor kopiujący, początkowym wierzchołkiem ścieżki jest v, a końcowym w, wówczas działanie algorytmu można przedstawić w następujących krokach:

1. IF NOT   G jest grafem eulerowskim   THEN   END
2. Przypisz   G’ = G
3. Dopisz do rozwiązania wierzchołek v
4. 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
9. 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 edytuj

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 i stopień każdego wierzchołka jest liczbą parzystą. Poprawność algorytmu zostanie wykazana przy użyciu indukcji względem liczby krawędzi.

Algorytm rozpoczyna się od stworzenia lokalnej kopii G’ grafu G i 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, odkładany jest indeks aktualnie rozpatrywanego wierzchołka na stosie, następnie wybiera się dowolną krawędź z nim incydentną, przechodzi się po niej do kolejnego wierzchołka i usuwa się tę krawędź z grafu. Operacja ta powtarzana jest tak długo, dopóki nie przejdzie się do wierzchołka, który nie ma już więcej krawędzi.

Proces ten musi się zakończyć w wierzchołku v. Wynika to z faktu, że jeżeli stopnie wszystkich w wierzchołków w grafie były parzyste, wówczas jeżeli obecnie rozpatrywany wierzchołek jest różny od wierzchołka początkowego, to w grafie znajdują się dokładnie dwa wierzchołki nieparzystych stopni – początkowy oraz obecny. Skoro aktualnie rozpatrywany wierzchołek jest nieparzystego stopnia, można go opuścić, przechodząc do kolejnego. Stąd wynika, przez zaprzeczenie, ż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 całego cyklu. Jeśli ono nastąpi, następuje koniec dowodu, ponieważ późniejszy powrót do pętli WHILE w kroku 12 nic nie zmienia. W przeciwnym wypadku wszystkie pozostałe w grafie wierzchołki są parzystego stopnia (ponieważ usunęliśmy z każdego parzystą liczbę krawędzi), chociaż mogą nie być połączone. Wynika stąd, że każda spójna składowa grafu G’ pozostałego po usunięciu pewnego cyklu w krokach 4 – 8 posiada cykl Eulera. Usunięta właśnie ścieżka cykliczna łączy te trasy w cykl Eulera dla wejściowego grafu. Gdyby tak nie było, wówczas suma pozostałych spójnych składowych i usuniętego w krokach 4 – 8 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, ale to nie zmienia dowodu) ścieżkę cykliczną, zbaczając z niej w każdym przypadku, gdy natrafi się na nieizolowany wierzchołek (gdy spełniony będzie warunek 4). Następnie przyjmuje się aktualnie zdjęty ze stosu wierzchołek za wierzchołek początkowy i powracając w do kroku 4 wywołuje się rekurencyjnie 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 się rozpoczęła, co wynika z indukcyjnego założenia dowodu.

Każda podtrasa może się zetknąć ze ścieżką cykliczną wiele razy. W takim przypadku jednak każdą podtrasę i tak przemierza się tylko jeden raz – wtedy, kiedy się na nią wejdzie.

Linki zewnętrzne edytuj

Eric W.E.W. Weisstein Eric W.E.W., Fleury's Algorithm, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).