Algorytm Fleury'ego
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Algorytm Fleury'ego – algorytm zaproponowany w teorii grafów pozwalający na odszukanie cykl Eulera w grafie eulerowskim.
[edytuj] Poszukiwanie ścieżki Eulera w grafie
Przypuśćmy, że dany jest graf G i że G jest grafem eulerowskim. Chcemy teraz znaleźć cykl Eulera wiodący od określonego wierzchołka v. Bezpośrednia rekurencyjna implementacja (poszukiwanie ścieżki poprzez sprawdzanie krawędzi i wykonywanie rekurencyjnych wywołań w celu znalezienia ścieżki w pozostałej części grafu) daje wykładniczą złożoność obliczeniową. Jednak nie chcemy akceptować takiej złożoności, ponieważ przetestowanie istnienia ścieżki jest bardzo łatwe, skąd wynika, że powinien również istnieć efektywny algorytm znajdujący ścieżkę Eulera.
Można uniknąć wydłużania czasu testując – przy stałym koszcie (w przeciwieństwie do nieznanych kosztów użycia wywołania rekurencyjnego) – czy użyć danej krawędzi, czy nie. Z punktu widzenia wydajności czasowej bardziej praktyczne jest jednak inne podejście: Można przemierzać ścieżkę cykliczną usuwając napotkane krawędzie i gromadząc na stosie napotkane wierzchołki, dzięki czemu:
- Możemy zawrócić po ścieżce i wydrukować jej krawędzie
- Możemy sprawdzić, czy dla każdego wierzchołka istnieją ścieżki prowadzące z innych stron (które można połączyć w jedną ścieżkę).
Zwróćmy uwagę na fakt, że algorytm wymaga stworzenia kopii lokalnej grafu, aby móc z niej usunąć poszukiwaną ścieżkę. Dlatego też jest niezwykle ważne, czy klasa definiująca abstrakcyjny typ danych graf posiada konstruktor kopiujący oraz czy tworzy on 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.
[edytuj] Pseudokod algorytmu
Przyjmijmy, że 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”. Przyjmijmy również, że dysponujemy stosem 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
[edytuj] Dowód poprawności algorytmu
Załóżmy, że poszukujemy cyklu Eulera w grafie eulerowskim G. Wówczas 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 wykażemy używając 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ładamy indeks aktualnie rozpatrywanego wierzchołka na stosie, wybieramy dowolną krawędź z nim incydentną, przechodzimy po niej do kolejnego wierzchołka i usuwamy tę krawędź z grafu. Operację tę powtarzamy tak długo, dopóki nie znajdziemy się w wierzchołku, który nie ma już więcej krawędzi.
Zauważmy, że 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żemy go opuścić, przechodząc do kolejnego. Stąd wynika, przez zaprzeczenie, że jeżeli wierzchołka nie możemy 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, to kończy dowód, 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. Zwróćmy uwagę na fakt, że 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 przemierzamy (od końca, ale to nie zmienia dowodu) ścieżkę cykliczną, zbaczając z niej w każdym przypadku, gdy natrafimy na nieizolowany wierzchołek (gdy spełniony będzie warunek 4). Następnie przyjmujemy aktualnie zdjęty ze stosu wierzchołek za wierzchołek początkowy i powracając w do kroku 4 wywołujemy rekurencyjnie algorytm znajdujący trasę Eulera dla spójnej składowej. Zauważmy, że 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 zresztą z indukcyjnego założenia dowodu.
Należy dodatkowo zauważyć, że każda podtrasa może się zetknąć ze ścieżką cykliczną wiele razy. W takim przypadku jednak każdą podtrasę i tak przemierzymy tylko jeden raz – wtedy, kiedy na nią wejdziemy.
