ALG - Cykl Eulera

by NOWIESZ

Definicja:

Pamiętacie z dzieciństwa zabawę w rysowanie koperty bez odrywania długopisu? To jest właśnie problem znajdowania łańcucha Eulera w grafie. Gdyby dodać warunek, że musimy zacząć i skończyć rysować w tym samym miejscu (tak się nie da) to byłby to problem znajdowania cyklu Eulera.

Cykl Eulera, to taki cykl w grafie, która zawiera każdą krawędź grafu, przy czym każdą dokładnie raz. Natomiast łańcuch Eulera to taka droga (czyli nie musi się kończyć tam gdzie zaczyna), która zawiera każdą krawędź grafu dokładnie raz.
Dotyczy to zarówno grafów nieskierowanych, jak i skierowanych.

Warunek istnienia cyklu:

Żeby znaleźć cykl/łańcuch Eulera w grafie trzeba najpierw sprawdzić czy istnieje. Przede wszystkim (i nie można o tym zapomnieć!) należy sprawdzić czy graf jest spójny (ale nie liczymy samotnych wierzchołków). Dla grafu skierowanego należy sprawdzić spójność jego nieskierowanego odpowiednika (tzn. chwilowo pozbawiamy krawędzi kierunku). Oczywiście gdy graf nie jest spójny to nie istnieje cykl Eulera (no bo jak obejść wszystkie krawędzie jeżeli nie można do którejś dojść?).
Teraz wystarczy zliczyć ile jest krawędzi wychodzących/wchodzących z/do każdego wierzchołka i sprawdzić jeden prosty warunek. W przypadku grafów skierowanych cykl Eulera istnieje wtedy i tylko wtedy gdy do każdego wierzchołka wchodzi tyle samo krawędzi co wychodzi (uwaga: pętla jednocześnie wchodzi i wychodzi). Natomiast w przypadku grafów nieskierowanych z każdego wierzchołka musi wychodzić parzysta liczba krawędzi (jedna połowa okaże się wchodzącymi, a druga połowa wychodzącymi).
Jeżeli chcemy znaleźć tylko łańcuch Eulera to możemy sobie pozwolić na drobne odstępstwo od powyższego warunku w dokładnie dwóch wierzchołkach. Czyli w przypadku grafów nieskierowanych dwa wierzchołki mogą mieć nieparzystą liczbę sąsiadów; w przypadku grafów skierowanych z dwóch wierzchołków liczba krawędzi wchodzących i wychodzących może się różnić o jeden.

Opis algorytmu:

Sprawdziwszy czy cykl istnieje możemy się zabrać za jego znalezienie. Zatem znajdujemy dowolny cykl w grafie (oznaczmy go sobie przez C0), startując z dowolnego wierzchołka. Następnie usuwamy wszystkie krawędzie tego cyklu. Prawdopodobnie spowoduje nam to rozspójnienie grafu i pojawi się kilka spójnych składowych (jeśli się nie pojawią to znaczy, że już wszystkie krawędzie zostały użyte i cykl znaleźliśmy). Każda z tych składowych ma punkt (co najmniej jeden) wspólny z naszym cyklem i właśnie od tego punktu zaczynamy rekurencyjne szukanie cyklu Eulera w tej składowej (i tak dla każdej składowej).
Następnie należy znaleziony cykl w każdej składowej połączyć z głównym cyklem. Jest to rzecz dość naturalna: jeżeli przeglądając cykl C0 dojdziemy do wierzchołka, który należy do jakiejś składowej, to zamiast podążać dalej tym cyklem wchodzimy w cykl tej składowej i dopiero po powrocie z niego kontynuujemy podróż w C0.

Może dla pełnej jasności ujmę to nieco inaczej (mniej książkowo). I to raczej tej wersji będę trzymać się w podanym poniżej algorytmie.
Znajdujemy jakiś cykl w grafie. Następnie przechodzimy po wierzchołkach, jednocześnie zapisując przebyte krawędzie na jakąś ogólną listę. Jeżeli dojdziemy do wierzchołka, z którego wychodzi krawędź, której jeszcze nie przeszliśmy to z tego wierzchołka zaczynamy rekurencyjne znajdowanie (pod)cyklu Eulera (a wynik tego powinien także znaleźć sie na tej ogólnej liście). Trzeba jednak pamiętać, żeby nie przechodzić krawędzi, które już raz przeszliśmy (kiedykolwiek). Po wyjściu z rekurencji można kontynuować podróż po głównym cyklu, chyba że z tego wierzchołka jeszcze wystają nieprzebyte krawędzie.
W praktyce znalezione cykle będę trzymać na stosie.

Jeżeli chcemy znaleźć jedynie łańcuch Eulera a nie cykl, to musimy wystartować z jednego wierzchołka, w którym nie był spełniony powyższy warunek. Później musimy znaleźć jakąkolwiek drogę do drguiego takiego wierzchołka. Dalej już jest tak samo - przeglądamy tą drogę i rekurencyjnie wyszukujemy cykle Eulera.

Najlepszą reprezentacją grafu do wykonania tego algorytmu są listy następników. Jeżeli ktoś koniecznie potrzebuje koniecznie inną reprezentację powinien zasymulować korzystanie z niej jak korzystanie z list następników.
Taka reprezentacja daje nam tą przewagę, że jeżeli odwiedzimy jakąś krawędź to przesuwamy wskaźnik na liście i więcej do tej krawędzi nie wrócimy. Przez to nie trzeba ani usuwać krawędzi z grafu, ani zapamiętywać przebyte krawędzie.

No to czas na (pseudo)kod. Założenie jest takie, że warunek istnienia cyklu Eulera został sprawdzony i wypadł pozytywnie.
Żeby znaleźć cykl Eulera należy wywołać procedurę EulerCycle z dowolnym wierzchołkiem (ale nie samotnym) podanym jako parametr.
Wynikiem jej działania będzie lista, w której będą zapisane kolejne wierzchołki (mogą się powtarzać) cyklu Eulera, które już łatwo przerobić na krawędzie. Lista jest jednak zapisana w odwrotnej kolejności, dlatego najlepiej jakby była strukturą LIFO - wtedy kolejność zdejmowania z niej byłaby prawidłowa. Można ten problem jeszcze załatwić np. używając zamiast stosu (patrz algorytm) kolejkę.

  procedure EulerCycle(v: Integer);
  {znajduje cykl Eulera poczawszy od wierzch. v; nie przechodzi przebytych krawedzi}
  begin
    w:=v;
    Put_On_Stack(w);
    repeat    {znajdowanie pewnego cyklu}
      w:=Get_Next_Succ(w);   {pobiera kolejny wierzch. z listy nastepnikow w;
                              przesuwa wskaznik na tej liscie na nastepny wierzch.}
      Put_On_Stack(w);  {dodaje kolejny wierzcholek do stosu}
    until w=v;   {konczy petle, gdy cykl sie zamknie}

    Get_Form_Stack(w);
    repeat  {przegladanie znalezionego cyklu}
      if No_Next_Succ(w) then    {z w nie wychodzi wiecej krawedzi}
        Put_On_List(w)     {wstawia wierzcholek na ogolna liste}
      else
        EulerCycle(w);    {znajdujemy rekurencyjnie podcykl Eulera startujac z w}
      Get_Form_Stack(w);   {bierzemy i usuwamy kolejny wierzch. cyklu ze stosu}
    until w=v;
    Put_On_List(v);
  end;

Powyższy algorytm działa dla grafów skierowanych. Dla grafów nieskierowanych powstaje jednak problem. W powyższym algorytmie bazowałem na tym, że jak przesunąłem wskaźnik na liście następników, to rozważana krawędź już się nigdy więcej nie pojawi. Niestety w grafach nieskierowanych ta sama krawędź jest na dwóch listach. Dlatego trzeba dodatkowo pamiętać krawędzie użyte.
Prosty kod pobrania kolejnego następnika (patrz pierwsza pętla) oraz sprawdzenia istnienia następnika (patrz druga pętla) powinien być zastąpiony przez mniej więcej taki:

   { pobranie kolejnego następnika }
   [...]
   repeat
     x:=Get_Next_Succ(w);    {szuka następnika w}
   until Not_Used(x,w);  {az znajdzie nieuzyta krawedz}
   Used(x,w);
   Used(w,x);    {zapamietuje, ze krawedzie zostaly uzyte}
   w:=x;
   [...]

   { sprawdzenie istnienia kolejnego następnika }
   [...]
   No_Succ:=True;
   while not No_Next_Succ do
   begin
     x:=Watch_Next_Succ(w);  {bierze nastepnika, ale nie przesuwa wskaznika}
     if Not_Used(x,w) then   {jezeli nie uzyty to ...}
     begin
       NoSucc:=False;   {stwierdza, ze istnieja nastepniki i opuszcza petle}
       Break;       
     end;
     x:=Get_Next_Succ(w);  {przesuwa wskaznik na liscie nastepnikow w}
   end;
   if NoSucc then
   [...]

Złożoność czasowa:

Może powiecie, że się powtarzam i jestem nudny, ale muszę to napisać. Algorytm przegląda każdą krawędź pewną stałą (niewielką) liczbę razy. Zatem działa w czasie O(E) (o ile została wybrana sensowna reprezentacja grafu).