Cykl Eulera

R1BdPlvr8Lhbh1

Ilustracja przedstawia namalowany portret Leonharda Eulera. Mężczyzna ma na sobie niebieską koszulę oraz białą czapkę. Ma niebieskie oczy i nie ma zarostu.

Jak wspomnieliśmy we wprowadzeniu, w tym e‑materiale zajmiemy się między innymi algorytmem, za pomocą którego sprawdzimy, czy dany grafgrafgraf zawiera cyklcyklcykl Eulera (tzn. czy jest grafem eulerowskim).

O grafie mówimy, że jest grafem eulerowskim, jeśli istnieje w nim cykl, który zawiera każdą jego krawędź.

Wiemy już, że spójny graf zawiera cykl Eulera wtedy i tylko wtedy, gdy każdy wierzchołek jest parzystego stopnia. To, czy wierzchołki są parzystego stopnia, możemy odczytać np. z macierzy sąsiedztwa danego grafu czy z ilustracji go przedstawiającej.

Tak prezentuje się graf przedstawiający mosty i lądy w Królewcu z czasów Eulera (problem ten został omówiony w e‑materiale Zagadnienie mostów królewieckichPwWUgv9LEZagadnienie mostów królewieckich):

R1R1e2UlsUpOf

Ilustracja przedstawia graf. Znajdują się na nim trzy punkty podpisane wielkimi literami A, C, D oraz jeden nieopisany punkt. Punkty C, A oraz punkt nieopisany leżą na okręgu, w taki sposób, że punkt C leży naprzeciwko punktu nieopisanego, a punkt A pomiędzy nimi. Punkt te znajduje się na końcu poziomego odcinka pomiędzy punktem A oraz d, przy czym nie leży on na linii okręgu. Pomiędzy punktem A i C oraz A i punktem nieopisanym znajdują się dodatkowe krzywe łączące te punkty. Punkty C i D oraz D i punkt nieopisany są połączone prostymi odcinkami.

Graf przedstawiający pięć mostów współczesnego Królewca:

R1AIRY8pYxPSN

Ilustracja przedstawia czworokąt przypominający deltoid, jego punkty oznaczono dużymi literami a, b, c, d. małymi literami oznaczono jego ściany, prosta ab to a, prosta bd to b, prosta cd to d, prosta ca to c, a prosta ad to e.

Macierz sąsiedztwa zaprezentowanego grafu:

$\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 1& 1& 1& 0\end{array}\right]$

By graf zawierał cykl Eulera, wszystkie jego wierzchołki muszą być parzystego stopnia.

Sprawdźmy, czy graf reprezentowany przedstawioną macierzą sąsiedztwa jest grafem eulerowskim. Zacznijmy od sprawdzenia stopnia wierzchołka oznaczonego jako wierzchołek A.

Musimy odczytać zatem informacje zawarte w pierwszym wierszu macierzy. Wierzchołek A nie jest połączony krawędzią z samym sobą (nie zawiera zatem pętli). Jest natomiast połączony krawędzią z wierzchołkami B, C oraz D (ponieważ w komórkach odpowiadających tym wierzchołkom znajdują się jedynki).

Zatem z wierzchołka wychodzą trzy krawędzie. Stopień tego wierzchołka wynosi więc trzy, w konsekwencji graf nie jest grafem eulerowskim.

Przejdźmy do pseudkodu algorytmu sprawdzania, czy graf zawiera cykl Eulera.

Specyfikacja problemu:

Dane:

• macierzSąsiedztwa – macierz sąsiedztwa grafu; tablica tablic liczb naturalnych z przedziału <0, 1>

Wynik:

• komunikat informujący o tym, czy graf zawiera cykl Eulera (tzn. czy jest grafem eulerowskim)

Spójny graf zawiera cykl Eulera wtedy i tylko wtedy, gdy każdy wierzchołek jest parzystego stopnia. To, czy wierzchołki są parzystego stopnia, możemy odczytać z macierzy sąsiedztwa danego grafu.

Dany jest następujący graf spójny nieskierowany bez wag:

R18enn1SlDMh3

Ilustracja przedstawia pięciokąt wypukły. Jego wierzchołki są oznaczone kolejno cyframi 4, 0, 1, 2, 5. Wierzchołek 4 oraz 1 jest połączony przekątną, tak samo jak wierzchołek 2 i 0. Z wierzchołka 4 oraz 2 wychodzą proste, które spotykają się w punkcie oznaczonym 3, który znajduje się wewnątrz figury. Wszystkie wierzchołki i punkty są oznaczone niebieskimi kółkami.

Macierz sąsiedztwa zaprezentowanego grafu:

$\left[\begin{array}{cccccc}0& 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 0\end{array}\right]$

Ponieważ nie wszystkie wierzchołki grafu (tj. wierzchołki 0 oraz 1) są parzystego stopnia, graf nie jest grafem eulerowskim (nie zawiera cyklu Eulera).

W programie wykorzystamy funkcję służącą do obliczania stopni wierzchołków grafu. Od niej zaczniemy.

Funkcja jako argument przyjmuje macierz sąsiedztwa grafu.

Zapiszmy jej nagłówek.

funkcja stopnieWierzchołkówWGrafie(macierzSąsiedztwa, stopnieWierzchołków):

Zaczynamy od utworzenia zmiennej n, której przypisujemy liczbę wierzchołków grafu, czyli długość tablicy macierzSąsiedztwa. W kolejnym kroku tworzymy tablicę stopnieWierzchołków o długości n i wypełniamy ją zerami. Tablica będzie przechowywać informacje na temat stopni kolejnych wierzchołków.

funkcja stopnieWierzchołkówWGrafie(macierzSąsiedztwa, stopnieWierzchołków):
	n ← długość(macierzSąsiedztwa)
	stopnieWierzchołków ← [0] * n
   

Zapisujemy pętlę dla, która będzie iterować przez kolejne wierzchołki grafu. W tej pętli zapisujemy zagnieżdżoną pętlę dla, która również będzie iterować przez wierzchołki grafu.

W pętli zagnieżdżonej zapisujemy instrukcję warunkową, w której sprawdzimy, czy istnieje krawędź łącząca dwa wierzchołki. Jeśli tak, wartość odpowiedniego elementu tablicy stopnieWierzchołków zostanie zwiększona o 1.

funkcja stopnieWierzchołkówWGrafie(macierzSąsiedztwa, stopnieWierzchołków):
	n ← długość(macierzSąsiedztwa)
	stopnieWierzchołków ← [0] * n
    dla i = 0, 1, ..., n - 1 wykonuj:
        dla j = 0, 1, ..., n - 1 wykonuj:
            jeżeli macierzSąsiedztwa[i][j] != 0:
   stopnieWierzchołków[i] ← stopnieWierzchołków[i] + 1

Wewnątrz tej instrukcji warunkowej zapisujemy kolejną, która zwiększy wartość tego elementu drugi raz, jeśli krawędź to pętla (czyli wychodzi z tego samego wierzchołka, do którego wchodzi).

Funkcja zwraca tablicę stopnieWierzchołków.

funkcja stopnieWierzchołkówWGrafie(macierzSąsiedztwa, stopnieWierzchołków):
	n ← długość(macierzSąsiedztwa)
	stopnieWierzchołków ← [0] * n
    dla i = 0, 1, ..., n - 1 wykonuj:
        dla j = 0, 1, ..., n - 1 wykonuj:
            jeżeli macierzSąsiedztwa[i][j] != 0:
	stopnieWierzchołków[i] ← stopnieWierzchołków[i] + 1
                jeżeli i = j:
	stopnieWierzchołków[i] ← stopnieWierzchołków[i] + 1
                    
	zwróć stopnieWierzchołków

Przejdźmy do zapisania funkcji odpowiedzialnej za sprawdzenie, czy w danym grafie reprezentowanym macierzą sąsiedztwa znajduje się cykl Eulera.

Zaczynamy od zapisania nagłówka funkcji istnienieCykluEulera, która jako argument przyjmuje macierz sąsiedztwa macierzSąsiedztwa.

funkcja istnienieCykluEulera(macierzSąsiedztwa):

Zaczynamy stworzenia pustej tablicy stopnieWierzchołków, a następnie wywołania funkcji stopnieWierzchołkówWGrafie i przypisania wyników jej działania utworzonej tablicy stopnieWierzchołków.

funkcja istnienieCykluEulera(macierzSąsiedztwa):
	stopnieWierzchołków ← utwórz pustą tablicę
	stopnieWierzchołków ← stopnieWierzchołkówWGrafie(macierzSąsiedztwa)

W kolejnym kroku tworzymy zmienną liczbaNieparzystych i przypisujemy jej wartość 0. Wykorzystamy ją jako licznik wierzchołków o stopniu nieparzystym.

funkcja istnienieCykluEulera(macierzSąsiedztwa):
	stopnieWierzchołków ← utwórz pustą tablicę
	stopnieWierzchołków ← stopnieWierzchołkówWGrafie(macierzSąsiedztwa)
    liczbaNieparzystych ← 0

Zapisujemy pętlę dla, która będzie iterować przez kolejne elementy tablicy stopnieWierzchołków. W pętli zapisujemy instrukcję warunkową. Instrukcja warunkowa dla każdego elementu tablicy stopnieWierzchołków sprawdzi, czy jest on liczbą parzystą, czyli czy dzieli się przez liczbę 2 bez reszty.

Jeśli liczba nie dzieli się przez 2 bez reszty, zwiększamy wartość licznika liczbaNieparzystych o 1.

funkcja istnienieCykluEulera(macierzSąsiedztwa):
	stopnieWierzchołków ← utwórz pustą tablicę
	stopnieWierzchołków ← stopnieWierzchołkówWGrafie(macierzSąsiedztwa)
    liczbaNieparzystych ← 0
    
    dla stopień w stopnieWierzchołków wykonuj:
    	jeżeli stopień mod 2 != 0:
        	liczbaNieparzystych ← liczbaNieparzystych + 1

Po zakończeniu pętli zostaje obliczona liczba wierzchołków o stopniu nieparzystym.

Zapisujemy kolejną instrukcję warunkową, której zadaniem będzie wypisanie odpowiedniego komunikatu na podstawie tego, czy przynajmniej jeden z wierzchołków grafu ma nieparzysty stopień. Jeśli nie, graf jest grafem eulerowskim –zawiera cykl Eulera. Wypisujemy odpowiedni komunikat.

Jeśli zaś graf ma przynajmniej jeden wierzchołek stopnia nieparzystego, graf nie zawiera cyklu Eulera. Wypisujemy wtedy odpowiedni komunikat.

funkcja istnienieCykluEulera(macierzSąsiedztwa):
	stopnieWierzchołków ← utwórz pustą tablicę
	stopnieWierzchołków ← stopnieWierzchołkówWGrafie(macierzSąsiedztwa)
    liczbaNieparzystych ← 0
    
    dla stopień w stopnieWierzchołków wykonuj:
    	jeżeli stopień mod 2 != 0:
        	liczbaNieparzystych ← liczbaNieparzystych + 1

    jeżeli liczbaNieparzystych = 0:
        wypisz "Graf zawiera cykl Eulera."
    w przeciwnym razie:
        wypisz "Graf nie zawiera cyklu Eulera."

Kompletny algorytm:

funkcja stopnieWierzchołkówWGrafie(macierzSąsiedztwa, stopnieWierzchołków):
	n ← długość(macierzSąsiedztwa)
	stopnieWierzchołków ← [0] * n
    dla i = 0, 1, ..., n - 1 wykonuj:
        dla j = 0, 1, ..., n - 1 wykonuj:
            jeżeli macierzSąsiedztwa[i][j] != 0:
				stopnieWierzchołków[i] ← stopnieWierzchołków[i] + 1
                jeżeli i = j:
					stopnieWierzchołków[i] ← stopnieWierzchołków[i] + 1
                    
	zwróć stopnieWierzchołków
    
funkcja istnienieCykluEulera(macierzSąsiedztwa):
	stopnieWierzchołków ← utwórz pustą tablicę
	stopnieWierzchołków ← stopnieWierzchołkówWGrafie(macierzSąsiedztwa)
    liczbaNieparzystych ← 0
    
    dla stopień w stopnieWierzchołków wykonuj:
    	jeżeli stopień mod 2 != 0:
        	liczbaNieparzystych ← liczbaNieparzystych + 1

    jeżeli liczbaNieparzystych = 0:
        wypisz "Graf zawiera cykl Eulera."
    w przeciwnym razie:
        wypisz "Graf nie zawiera cyklu Eulera."

Polecenie 1

Przeanalizuj działanie programu dla zaprezentowanego grafu.

Dany jest następujący graf nieskierowany bez wag:

R1MbTs8xXp1kN

Ilustracja przedstawia graf składający się z dwóch nieregularnych czworokątów. Pierwszy z nich ma wierzchołki oznaczone jako 1, 2, 3 oraz 5, a drugi 1,6,3 oraz zero. Wierzchołki 1 oraz 3 są wierzchołkami wspólnymi. Dodatkowo na bok drugiego czworokąta pomiędzy punktem zero i trzy znajduje się punkt cztery. Punkty na wierzchołkach oznaczone są niebieskimi okręgami.

Macierz sąsiedztwa grafu:

$\left[\begin{array}{ccccccc}0& 1& 0& 0& 1& 0& 0\\ 1& 0& 1& 0& 0& 1& 1\\ 0& 1& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 1\\ 1& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0\end{array}\right]$

Zastanów się, jaki będzie wynik działania programu. Spróbuj odnaleźć w grafie, jeśli jest, cykl Eulera.

Pokaż rozwiązanie

Wynik działania programu:

Linia 1. Graf zawiera cykl Eulera kropka.

Graf zawiera cykl Eulera.

Przykładowy cykl Eulera:

Linia 1. 0 → 1 → 2 → 3 → 6 → 1 → 5 → 3 → 4 → 0.

0 → 1 → 2 → 3 → 6 → 1 → 5 → 3 → 4 → 0

Ścieżka Eulera

Przeanalizujmy teraz algorytm sprawdzania, czy w grafie można wyznaczyć ścieżkę Eulera. Jest to taka ścieżkaścieżkaścieżka, która przechodzi przez każdą krawędź grafu dokładnie raz i nie kończy się w wierzchołku, w którym się zaczynała.

Graf, który nie zawiera cyklu Eulera, a jedynie ścieżkę Eulera, nazywamy grafem półeulerowskim. Aby graf można było nazwać półeulerowskim, musi on spełniać warunek zawarty w poniższym twierdzeniu.

Na tej podstawie wcześniej przedstawiony algorytm można zmodyfikować tak, aby sprawdzał zarówno, czy graf jest eulerowski, jak i półeulerowski.

Specyfikacja problemu:

Dane:

• macierzSąsiedztwa – macierz sąsiedztwa grafu; tablica tablic liczb naturalnych z przedziału <0, 1>

Wynik:

• komunikat informujący o tym, czy graf jest eulerowski, półeulerowski lub czy nie jest ani eulerowski, ani półeulerowski

Dany jest następujący graf spójny nieskierowany bez wag:

RwNYxXmfzqT33

Spójny graf nieskierowany bez wag składający się z ośmiu wierzchołków oraz dziewięciu krawędzi. Wierzchołek jeden połączony jest krawędziami z wierzchołkami zero, dwa i trzy. Wierzchołek dwa z wierzchołkiem cztery. Wierzchołek trzy z wierzchołkami cztery i zero. Wierzchołek zero z wierzchołkiem siedem. Wierzchołek siedem łączy krawędź z wierzchołkiem sześć. Wierzchołek sześć połączony jest z wierzchołkiem pięć.

Macierz sąsiedztwa zaprezentowanego grafu:

$\left[\begin{array}{cccccccc}0& 1& 0& 0& 0& 0& 0& 1\\ 1& 0& 1& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1& 0& 1\\ 1& 0& 0& 0& 0& 0& 1& 0\end{array}\right]$

Ponieważ nie wszystkie wierzchołki grafu są parzystego stopnia, graf nie jest grafem eulerowskim (nie zawiera cyklu Eulera). Natomiast dwa wierzchołki (1 oraz 5) są nieparzystego stopnia, zatem graf jest grafem półeulerowskim – zawiera zatem ścieżkę Eulera.

Ponownie wykorzystamy funkcję stopnieWierzchołkówWGrafie.

Zapiszmy nagłówek funkcji istnienieŚcieżkiEulera, która jako argument przyjmuje macierz sąsiedztwa macierzSąsiedztwa.

W kolejnym kroku tworzymy pustą tablicę stopnieWierzchołków.

Wywołujemy funkcję obliczającą stopnie wierzchołków stopnieWierzchołkówWGrafie. Wynik jej działania zapisujemy w utworzonej tablicy stopnieWierzchołków.

Następnie tworzymy i inicjalizujemy zmienną liczbaNieparzystych wartością 0. Zmienna będzie przechowywać liczbę wierzchołków o stopniu nieparzystym.

funkcja istnienieŚcieżkiEulera(macierzSąsiedztwa):
	stopnieWierzchołków ← utwórz pustą tablicę
	stopnieWierzchołków ← stopnieWierzchołkówWGrafie(macierzSąsiedztwa)
    liczbaNieparzystych ← 0

Zapisujemy pętlę, która będzie iterować po kolejnych wierzchołkach. Jej zadaniem będzie zliczenie wierzchołków o stopniu nieparzystym.

By to zrobić, zapisujemy instrukcję warunkową. Jeśli warunek jest spełniony, zwiększamy wartość zmiennej liczbaNieparzystych o 1.

funkcja istnienieŚcieżkiEulera(macierzSąsiedztwa):
	stopnieWierzchołków ← utwórz pustą tablicę
	stopnieWierzchołków ← stopnieWierzchołkówWGrafie(macierzSąsiedztwa)
    liczbaNieparzystych ← 0
    
    dla stopień w stopnieWierzchołków wykonuj:
    	jeżeli stopień mod 2 != 0:
        	liczbaNieparzystych ← liczbaNieparzystych + 1

Po zakończeniu pętli zostaje obliczona liczba wierzchołków o stopniu nieparzystym.

Zapisujemy instrukcje warunkowe, za pomocą których sprawdzimy odpowiednie własności grafu. W pierwszej sprawdzamy, czy wartość zmiennej liczbaNieparzystych wynosi 0.

Jeśli tak, oznacza to, że wszystkie wierzchołki mają stopień parzysty, a więc mamy do czynienia z grafem eulerowskim. Wypisujemy odpowiedni komunikat.

Jeśli wartość zmiennej liczbaNieparzystych wynosi 2, oznacza to, że dokładnie dwa wierzchołki mają stopień nieparzysty, co oznacza, że graf zawiera ścieżkę Eulera i jest grafem półeulerowskim. Wypisujemy odpowiedni komunikat.

W przeciwnym razie, gdy żaden z warunków nie jest spełniony, graf nie zawiera ani cyklu Eulera, ani ścieżki Eulera, zatem nie jest ani eulerowski, ani półeulerowski. Wypisujemy odpowiedni komunikat.

Kompletny algorytm:

funkcja stopnieWierzchołkówWGrafie(macierzSąsiedztwa, stopnieWierzchołków):
	n ← długość(macierzSąsiedztwa)
	stopnieWierzchołków ← [0] * n
    dla i = 0, 1, ..., n - 1 wykonuj:
        dla j = 0, 1, ..., n - 1 wykonuj:
            jeżeli macierzSąsiedztwa[i][j] != 0:
				stopnieWierzchołków[i] ← stopnieWierzchołków[i] + 1
                jeżeli i = j:
					stopnieWierzchołków[i] ← stopnieWierzchołków[i] + 1
                    
	zwróć stopnieWierzchołków
    
funkcja istnienieŚcieżkiEulera(macierzSąsiedztwa):
	stopnieWierzchołków ← utwórz pustą tablicę
	stopnieWierzchołków ← stopnieWierzchołkówWGrafie(macierzSąsiedztwa)
    liczbaNieparzystych ← 0
    
    dla stopień w stopnieWierzchołków wykonuj:
    	jeżeli stopień mod 2 != 0:
        	liczbaNieparzystych ← liczbaNieparzystych + 1

    jeżeli liczbaNieparzystych = 0:
        wypisz "Graf jest eulerowski."
    w przeciwnym razie jeżli liczbaNieparzystych = 2:
        wypisz "Graf jest półeulerowski."
    w przeciwnym razie:        
        wypisz "Graf nie jest ani eulerowski, ani półeulerowski."

Słownik