Dziś zajmiemy się drogami i cyklami Eulera. I na poczatek kilka definicji. Niech G = (V, E) będize grafem spójnym nieskierowanym (n >= 3). Drogą Eulera nazywamy drogę prostą (w której nie powtarzają się krawędzie), która zawiera wszystkie krawędzie grafu. Cykl Eulera to cykl prosty, który zawiera wszystkie krawędzie grafu. Mówi się tez o grafie Eulerowskim. Jest to taki graf, w którym istnieje cykl Eulera. I jeszcze mamy graf pseudo Eulerowski. Jest to graf, w którym istnieje nie zamknięta droga Eulera.

W roku 1736 zostało wprowadzone twierdzenie Eulera, które mówi, że każdy graf spójny nieskierowany (n >= 3, gdzie n to liczba wierzchołków) ma cykl Eulera wtedy i tylko wtedy, gdy stopień każdego z jego wierzchołków jest parzysta. Zatem gdy stopień wierzchołka jest parzysty, to taki graf jest grafem Eulera. Dobrym przykładem wierzchołka jest ten na ilustracji obok.

Z powyżego twierdzenia Eulera wynika jednocześnie kolejne z twierdzeń.

Graf spójny nieskierowany (n >= 3) jest grafem pseudo Eulera wtedy i tylko wtedy, gdy istnieją w nim dokładnie dwa wierzchołki stopnia niepatrzystego, a pozostałe wierzchołki mają stopień parzysty.

Do znajdowania cyklu (drogi) w grafach Eulerowskich, lub pseudo Eulerowskich, służy nam algorytm Fleurego. Składa się on z dwóch kroków. W pierwszym wychodzimy z dowolnego wierzchołka (wierzchołka stopnia nieparzystego), a następnie w drugim przechodzimy po krawędziach usuwając je z zastrzeżeniem, że nie przechodzimy po krawędziach, które są mostami. Wszystkie z powyższych definicji tak samo się stosuje dla grafów skierowanych.

Przejdźmy teraz do dróg i cykli Hamiltona. Niech G będzie grafem nieskierowanym spójnym (n >= 3). Droga Hamiltona nazywamy droge elementarną (gdzie nie powtarzają się wierzchołki), która zawiera wszystkie wierchołki grafów. Cyklem Hamiltona z kolei nazywamy taki cykl elementarny, który zawiera wszystkie wierzchołki grafu. Cykl Hamiltona to graf, w którym istnieje cykl Hamiltona. I teraz pytanie jak taki cykl Hamiltona znależć. Aby tego dokonać należy przeszukać wszystkie możliwe drogi. Załóżmy, że mamy graf o 10 wierzchołkach V = {1, 2, 3, …, 10}. Drogi w tym grafie będą określone bijekcją

|Bij (V)| = 10! Czyli mamy tu do czynienia ze złożonością problemu O(n!) klasy NP. Jednak jeśli graf jest stosunkowo duży, to uciążliwe jest przeszukiwanie wszystkich kombinacji. Stąd istnieją tak zwane warunki dostateczne Hamiltonowości. Są to twierdzenia tego typu, że jest jakiś warunek (że coś w grafie jest spełnione) i jeśli ten warunek jest spełniony, to graf jest hamiltonowski. Jednak nie działa to w druga stronę. I mamy trzy takie twierdzenia, które są warunkami dostatecznymi Hamiltonowości grafu:

1. Jeśli dla każdej pary niezależnych wierzchołków, czyli
   

d(u) + d(v) >= n, gdzie d(u) to stopień wierzchołka, to stąd wynika, że graf jest Hamiltonowski.

2. Jeśli dla każdego wierzchołka v jego stopień, czyli d(v) >= n/2, to wówczas graf G jest Hamiltonowski.

3. Niech m = |E| (liczba krawędzi w grafie). Jeśli
   , to wtedy graf G jest Hamiltonowski.

Jeśli na przykład pierwszy warunek dostateczny nie jest spełniony, to mówi się, że dla pierwszego warunku nie można orzec, czy graf jest Hamiltonowski. I wówczas sprawdzamy kolejny warunek. Jeśli trzy nie sa spełnione, to znaczy, ze graf nie jest Hamiltonowski.

d(i) = 4

---