Gdyby taki cykl istniał, moglibyśmy bez odrywania ołówka narysować graf, przechodząc po każdej krawędzi jeden raz. Takie figury nazywamy jednobieżnymi lub unikursalnymi.

Obecnie w Kaliningradzie (czyli dawnym Królewcu) na rzece Pregole istnieje pięć mostów, z czego tylko dwa pochodzą jeszcze z czasów Eulera. Gdyby przedstawić je za pomocą grafu, wówczas dwa węzły byłyby stopnia drugiego, a dwa pozostałe – stopnia trzeciego. Możliwe jest utworzenie ścieżki przechodzącej przez każdy z mostów jedynie raz, ale ze względu na nieparzyste stopnie dwóch wierzchołków nie będzie ona cyklem Eulera – zakończy się w innym wierzchołku niż wierzchołek początkowy.

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.

Specyfikacja problemu:

Dane:

• macierzSasiedztwa – macierz sąsiedztwa grafu; tablica tablic (lista list) liczb naturalnych z przedziału <0, 1>

Wynik:

• komunikat informujący o tym, czy graf zawiera cykl Eulera

Zaczynamy od zapisania nagłówka funkcji istnienieCykluEulera, która jako argument przyjmuje macierz sąsiedztwa macierzSasiedztwa. W kolejnym kroku inicjalizujemy zmienną liczbaWierzcholkow jako rozmiar macierzy, czyli liczbę wierzchołków w grafie.

Następnie tworzymy tablicę (listę) stopnieWierzcholkow o długości liczbaWierzcholkow i wypełniamy ją wartościami początkowymi 0. Tworzymy również zmienną liczbaNieparzystych, której przypisujemy wartość 0. Zmienna będzie przechowywać liczbę wierzchołków o stopniu nieparzystym.

Zapisujemy pętlę, która będzie iterować po kolejnych wierzchołkach i zapisywać ich stopnie wierzchołków.

Wewnątrz tej pętli zapisujemy drugą pętlę, której zadaniem będzie sprawdzenie sąsiedztwa wierzchołka.

Dla każdego elementu tablicy (listy) stopnieWierzcholkow dodajemy wartość zmiennej macierzSasiedztwa[i][j] do wartości stopnia wierzchołka.

Po zakończeniu obu pętli obliczone zostają stopnie wszystkich wierzchołków.

Uruchamiamy pętlę, aby zliczyć wierzchołki o stopniu nieparzystym.

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

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

Wykonujemy instrukcję warunkową. Sprawdzamy, czy wartość zmiennej liczbaNieparzystych wynosi 0 oraz czy wartość zmiennej liczbaWierzcholkow jest większa od 0. Jeśli tak, oznacza to, że wszystkie wierzchołki mają stopień parzysty, a więc graf zawiera cykl Eulera. Wypisujemy odpowiedni komunikat.

Jeśli warunek nie zostaje spełniony, graf nie zawiera cyklu Eulera. Wtedy również wypisujemy komunikat.

Algorytm kończy swoje działanie.

funkcja istnienieCykluEulera(macierzSasiedztwa):
	liczbaWierzcholkow ← długość(macierzSasiedztwa)
    stopnieWierzcholkow ← [0] * liczbaWierzcholkow
    liczbaNieparzystych ← 0

    dla i = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
        dla j = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
            stopnieWierzcholkow[i] ← stopnieWierzcholkow[i] + macierzSasiedztwa[i][j]

   dla i = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
        jeżeli stopnieWierzcholkow[i] mod 2 != 0:
            liczbaNieparzystych += 1

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

Dla tak skonstruowanego algorytmu dane wejściowe opisujące graf reprezentujący Królewiec współcześnie wyglądałyby następująco:

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

Specyfikacja problemu:

Dane:

• listaSasiedztwa – lista sąsiedztwa grafu; tablica tablic (lista list) łańcuchów znaków

• liczbaWierzcholkow – liczba wierzchołków w grafie; liczba naturalna

Wynik:

• komunikat informujący o tym, czy graf zawiera cykl Eulera

funkcja istnienieCykluEulera(listaSasiedztwa[0..liczbaWierzcholkow - 1], liczbaWierzcholkow):    
  dla i = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
  	jeżeli długość(listaSasiedztwa[i]) mod 2 != 0:
  		wypisz("Graf nie zawiera cyklu Eulera")
  		przerwij wykonanie funkcji
   
  wypisz("Graf zawiera cykl Eulera")

Specyfikacja problemu:

Dane:

• macierzSasiedztwa – macierz sąsiedztwa grafu; tablica tablic (lista list) liczb naturalnych z przedziału <0, 1>

Wynik:

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

Zaczynamy od zapisania nagłówka funkcji istnienieSciezkiEulera, która jako argument przyjmuje macierz sąsiedztwa macierzSasiedztwa. W kolejnym kroku inicjalizujemy zmienną liczbaWierzcholkow jako rozmiar macierzy, czyli liczbę wierzchołków w grafie.

Następnie tworzymy tablicę (listę) stopnieWierzcholkow o długości liczbaWierzcholkow i wypełniamy ją wartościami początkowymi 0.

Zapisujemy pętlę, która będzie iterować po kolejnych wierzchołkach i zapisywać dla nich stopnie wierzchołków.

Wewnątrz tej pętli zapisujemy drugą pętlę, której zadaniem będzie sprawdzenie sąsiedztwa wierzchołka.

Dla każdego elementu tablicy (listy) stopnieWierzcholkow zwiększamy ten element o wartość zmiennej macierzSasiedztwa[i][j].

Po zakończeniu obu pętli obliczone zostają stopnie wszystkich wierzchołków.

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

Uruchamiamy pętlę, aby zliczyć wierzchołki o stopniu nieparzystym.

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

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

Wykonujemy instrukcję warunkową. 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 powyższych warunków nie jest spełniony, graf nie zawiera ani cyklu Eulera, ani ścieżki Eulera, zatem graf nie jest ani eulerowski, ani półeulerowski. Wypisujemy odpowiedni komunikat

Algorytm kończy swoje działanie.

funkcja istnienieSciezkiEulera(macierzSasiedztwa):
    liczbaWierzcholkow ← długość(macierzSasiedztwa)
    stopnieWierzcholkow ← [0] * liczbaWierzcholkow
    liczbaNieparzystych ← 0

    dla i = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
        dla j = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
            stopnieWierzcholkow[i] ← stopnieWierzcholkow[i] + macierzSasiedztwa[i][j]

    dla i = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
        jeżeli stopnieWierzcholkow[i] mod 2 != 0:
            liczbaNieparzystych ← liczbaNieparzystych + 1

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

Przykładowe dane wejściowe odpowiadające obecnym mostom królewieckim wyglądałyby tak jak w poprzednim algorytmie:

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

Specyfikacja problemu:

Dane:

• listaSasiedztwa – lista sąsiedztwa grafu; tablica tablic (lista list) łańcuchów znaków

• liczbaWierzcholkow – liczba wierzchołków w grafie; liczba naturalna

Wynik:

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

funkcja istnienieSciezkiEulera(listaSasiedztwa[0..liczbaWierzcholkow - 1], liczbaWierzcholkow):
  liczbaNieparzystych ← 0
    
  dla i = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
  	jeżeli długość(listaSasiedztwa[i]) mod 2 != 0:
  		liczbaNieparzystych ← liczbaNieparzystych + 1
    
  jeżeli liczbaNieparzystych = 0:
  	wypisz("Graf jest eulerowski.")
  w przeciwnym razie:
  jeżeli liczbaNieparzystych = 2:
  	wypisz("Graf jest półeulerowski.")
  w przeciwnym razie: 
  	wypisz("Graf nie jest ani eulerowski, ani półeulerowski.")

Wykorzystaliśmy funkcję długość(). Ma ona swoje odpowiedniki w językach programowania.

C++

sizeof(lista) / sizeof(lista[0])

Przykład:

#include <iostream>
using namespace std;

int main() {
    string lista[3] = {"kot", "pies", "rybki"};
    int x = sizeof(lista) / sizeof(lista[0]);
    cout << x << endl;
    
    return 0;
}

// wynik działania programu
// 3

Java

lista.length

Przykład:

public class Main {
    public static void main(String[] args) {
        String[] lista = {"kot", "pies", "rybki"};
        int x = lista.length;
        System.out.println(x);
    }
}

// wynik działania programu
// 3

Python

len(lista)

Przykład:

lista  = ["kot", "pies", "rybki"]
x = len(lista)
print(x)

# wynik działania programu
# 3