Cykl Eulera i Hamiltona

Zanim opiszę cykle i ścieżki znalezione w grafach przez XVIII w. matematyka i fizyka Leonhard Eulera zacznę od podstaw. Do zrozumienia twierdzenia niezbędna jest znajomość ścieżki i cyklu w grafie. Zaczniemy więc od ścieżki.

Ścieżka to wierzchołki i krawędzie łączące te wierzchołki. Wierzchołki mogą posiadać krawędzie tworzące tzw. pętlę (lub cyklem własnym) czyli prowadzić do tego samego wierzchołka, z którego wychodzą.

Specjalnym typem ścieżki jest ścieżka prosta czyli taka, w której wierzchołki się nie powtarzają. Od pojęcia ścieżki łatwo przejść do pojęcia cyklu gdyż jest nim ścieżka zamknięta czyli taka, po której można się przejść tak jakby “w koło” i skończyć na tym samym wierzchołku. Analogicznie możemy określi też cykl jako prosty – taki bez powtórzeń krawędzi.

Wiemy czym jest ścieżka i cykl pora na sedno wpisu czyli Cykl Eulera i Hamiltona.

Cykl prosty zawierający każdą krawędź dokładnie raz to cykl Eulera. Zatem graf, który takowy cykl zawiera nazywamy grafem Eulerowskim. Mówiąc bardziej obrazowo graf z cyklem Eulera możemy narysować bez odrywania ołówka od kartki. Jest cykl więc jest i ścieżka Eulera czyli ponownie jest to droga zawierająca każdą krawędź.

Sprawa się ma bardzo podobnie jeśli chodzi o cykl i ścieżki Hamiltona. Zasadniczą różnicą jest to, że występują tam wierzchołki nie krawędzie. Cykl Hamiltona to cykl zawierający każdy wierzchołek dokładnie raz. To samo ścieżka Hamiltona – każdy wierzchołek jest w niej dokładnie raz oczywiście nie licząc tego, że startujemy i kończymy w tym samym wierzchołku. Interesujący przykład grafu Hamiltonowskiego czyli zawierającego cykl Hamiltona można znaleźć w wiki.

graf dwunastościanu foremnego

Prawda, że ładny 🙂

Leave your comment: