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 implementacją algorytmu, 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 zawiera cykl, który przechodzi przez każdą jego krawędź dokładnie raz.

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:

R3KpsVySuOeuT

Ilustracja przedstawia tabelkę, górne kolumny są podpisane a, b, c, d, wiersze rak samo, w pierwszym wierszu znajdują się następujące liczby, 0, 1, 1, 1, w drugim, 1, 0, 0, 1, w trzecim 1, 0, 0, 1, w czwartym 1, 1, 1, 0.

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.

Poniżej przedstawiono algorytm sprawdzający, czy dany graf jest grafem eulerowskim. Argumentami funkcji są: macierz sąsiedztwa reprezentująca graf, na podstawie której sprawdzona zostanie parzystość stopni wierzchołków, oraz liczba wierzchołków grafu. Funkcja zwróci prawdziwy wynik jedynie w przypadku, gdy wejściowy graf jest spójny.

Specyfikacja problemu:

Dane:

• n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna

• macierzSasiedztwa – macierz sąsiedztwa grafu; tablica dwuwymiarowa liczb naturalnych

Wynik:

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

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:

R1eJLJbnGIkP5

Ilustracja przedstawia tabelkę sześć na sześć kratek. Jej kolumny i rzędy są oznaczone cyframi od 0 do 5. W pierwszym rzędzie wpisano 0, 1, 1, 0, 1, 0, w drugim rzędzie 1, 0, 1, 0, 1, 0, w trzecim rzędzie, 1, 1, 0, 1, 0, 1, w czwartym rzędzie 0, 0, 1, 0, 1, 0, w piątym rzędzie 1, 1, 0, 1, 0, 1, w szóstym rzędzie 0, 0, 1, 0, 1, 0.

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

Tworzymy stałą n, której przypisujemy wartość 6 (czyli liczbę wierzchołków).

Implementacja zaprezentowanej macierzy sąsiedztwa w języku C++:

const int n = 6;

int macierzSasiedztwa[n][n] = {
	{ 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 }
};

Wyniki będziemy testować dla zaprezentowanego grafu.

W programie wykorzystamy funkcję służącą do obliczania stopni wierzchołków grafu. Omówiliśmy ją w e‑materiale Stopień grafu, stopień wierzchołka, grafy spójne – implementacja w języku C++PGZnJdF0kStopień grafu, stopień wierzchołka, grafy spójne – implementacja w języku C++.

Funkcja:

void stopnieWierzcholkowWGrafie(int macierzSasiedztwa[n][n], int stopnieWierzcholkow[n]) {
    for (int i = 0; i < n; ++i) {
        stopnieWierzcholkow[i] = 0;
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnieWierzcholkow[i]++;
                if (i == j) {
                    stopnieWierzcholkow[i]++;
                }
            }
        }
    }
}

W programie wykorzystamy również funkcję, która na podstawie tablicy utworzonej przez funkcję stopnieWGrafie określi, czy w grafie znajduje się cykl Eulera.

Zapiszemy zatem nagłówek funkcji istnienieCykluEulera, która jako argument przyjmuje macierz sąsiedztwa macierzSasiedztwa.

Następnie tworzymy pustą tablicę stopnieWierzcholkow o długości n. Wypełniamy ją wartościami 0.

W kolejnym kroku wywołujemy funkcję stopnieWierzcholkowWGrafie dla macierzy sąsiedztwa oraz utworzonej tablicy.

bool istnienieCykluEulera(int macierzSasiedztwa[n][n]) {
    int stopnieWierzcholkow[n];
    stopnieWierzcholkowWGrafie(macierzSasiedztwa, stopnieWierzcholkow);

}

Tworzymy zmienną liczbaNieparzystych i przypisujemy jej wartość 0.

Zapisujemy pętlę for, która będzie iterować po kolejnych elementach tablicy przechowującej stopnie wierzchołków.

Jej zadaniem będzie zliczenie wierzchołków o stopniu nieparzystym.

Sprawdzamy warunek stopnieWierzcholkow[i] % 2 != 0. Jeśli warunek ten jest spełniony, zwiększamy wartość zmiennej liczbaNieparzystych o 1.

bool istnienieCykluEulera(int macierzSasiedztwa[n][n]) {
    int stopnieWierzcholkow[n];
    stopnieWierzcholkowWGrafie(macierzSasiedztwa, stopnieWierzcholkow);

    int liczbaNieparzystych = 0;
    for (int i = 0; i < n; i++) {
        if (stopnieWierzcholkow[i] % 2 != 0) {
            liczbaNieparzystych++;
        }
    }
}

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 i zwracamy wartość true.

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

bool istnienieCykluEulera(int macierzSasiedztwa[n][n]) {
    int stopnieWierzcholkow[n];
    stopnieWierzcholkowWGrafie(macierzSasiedztwa, stopnieWierzcholkow);

    int liczbaNieparzystych = 0;
    for (int i = 0; i < n; i++) {
        if (stopnieWierzcholkow[i] % 2 != 0) {
            liczbaNieparzystych++;
        }
    }

    if (liczbaNieparzystych == 0 and n > 0) {
        cout << "Graf zawiera cykl Eulera." << endl;
        return true;
    } else {
        cout << "Graf nie zawiera cyklu Eulera." << endl;
        return false;
    }
}

Kompletny kod programu:

#include <iostream>
using namespace std;

const int n = 6;

void stopnieWierzcholkowWGrafie(int macierzSasiedztwa[n][n], int stopnieWierzcholkow[n]) {
    for (int i = 0; i < n; ++i) {
        stopnieWierzcholkow[i] = 0;
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnieWierzcholkow[i]++;
                if (i == j) {
                    stopnieWierzcholkow[i]++;
                }
            }
        }
    }
}

bool istnienieCykluEulera(int macierzSasiedztwa[n][n]) {
    int stopnieWierzcholkow[n];
    stopnieWierzcholkowWGrafie(macierzSasiedztwa, stopnieWierzcholkow);

    int liczbaNieparzystych = 0;
    for (int i = 0; i < n; i++) {
        if (stopnieWierzcholkow[i] % 2 != 0) {
            liczbaNieparzystych++;
        }
    }

    if (liczbaNieparzystych == 0 and n > 0) {
        cout << "Graf zawiera cykl Eulera." << endl;
        return true;
    } else {
        cout << "Graf nie zawiera cyklu Eulera." << endl;
        return false;
    }
}

int main() {
    int macierzSasiedztwa[n][n] = {
    	{ 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 }
    };
    
    istnienieCykluEulera(macierzSasiedztwa);
    return 0;
}

Efekt działania programu:

Graf nie zawiera cyklu Eulera.

Przykład 1

Przetestujmy działanie programu dla grafu, o którym wiemy, że zawiera cykl Eulera, ponieważ wszystkie jego wierzchołki są parzystego stopnia.

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:

Linia 1. int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 2. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 3. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 4. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 5. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 6. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 7. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 8. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy średnik.

int macierzSasiedztwa[n][n] = {
    { 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 }
};

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 implementację algorytmu sprawdzającego, 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 twierdzeniu:

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

Specyfikacja problemu:

Dane:

• n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna

• macierzSasiedztwa – macierz sąsiedztwa grafu; tablica dwuwymiarowa liczb naturalnych

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ęć.

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.

Implementacja macierzy sąsiedztwa grafu w języku C++:

const int n = 8;

int macierzSasiedztwa[n][n] = {
	{ 0, 1, 0, 0, 0, 0, 0, 1 },
	{ 1, 0, 1, 1, 0, 0, 0, 0 },
	{ 0, 1, 0, 1, 0, 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 }
};

Wyniki będziemy testować dla zaprezentowanego grafu.

Ponownie wykorzystamy funkcję stopnieWierzcholkowWGrafie.

Zapiszmy nagłówek funkcji istnienieSciezkiEulera, która jako argument przyjmuje macierz sąsiedztwa macierzSasiedztwa.

W kolejnym kroku tworzymy tablicę stopnieWierzcholkow o długości równej liczbie wierzchołków – n.

Wywołujemy funkcję obliczającą stopnie wierzchołków. Jako argumenty przyjmuje macierz sąsiedztwa oraz utworzoną tablicę.

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

void istnienieSciezkiEulera(int macierzSasiedztwa[n][n]) {
    int stopnieWierzcholkow[n];
    stopnieWierzcholkowWGrafie(macierzSasiedztwa, stopnieWierzcholkow);

    int 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.

void istnienieSciezkiEulera(int macierzSasiedztwa[n][n]) {
    int stopnieWierzcholkow[n];
    stopnieWierzcholkowWGrafie(macierzSasiedztwa, stopnieWierzcholkow);

    int liczbaNieparzystych = 0;
    for (int i = 0; i < n; i++) {
        if (stopnieWierzcholkow[i] % 2 != 0) {
            liczbaNieparzystych++;
        }
    }
}

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 kod programu:

#include <iostream>
using namespace std;

const int n = 8;

void stopnieWierzcholkowWGrafie(int macierzSasiedztwa[n][n], int stopnieWierzcholkow[n]) {
    for (int i = 0; i < n; ++i) {
        stopnieWierzcholkow[i] = 0;
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnieWierzcholkow[i]++;
                if (i == j) {
                    stopnieWierzcholkow[i]++;
                }
            }
        }
    }
}

void istnienieSciezkiEulera(int macierzSasiedztwa[n][n]) {
    int stopnieWierzcholkow[n];
    stopnieWierzcholkowWGrafie(macierzSasiedztwa, stopnieWierzcholkow);

    int liczbaNieparzystych = 0;
    for (int i = 0; i < n; i++) {
        if (stopnieWierzcholkow[i] % 2 != 0) {
            liczbaNieparzystych++;
        }
    }

    if (liczbaNieparzystych == 0) {
        cout << "Graf jest eulerowski." << endl;
    } else if (liczbaNieparzystych == 2) {
        cout << "Graf jest poleulerowski." << endl;
    } else {
        cout << "Graf nie jest ani eulerowski, ani poleulerowski." << endl;
    }
}

int main() {
    int macierzSasiedztwa[n][n] = {
        { 0, 1, 0, 0, 0, 0, 0, 1 },
        { 1, 0, 1, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 1, 0, 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 }
    };


    istnienieSciezkiEulera(macierzSasiedztwa);
    return 0;
}

Wynik działania programu:

Graf jest poleulerowski.

Słownik