Cykl Eulera

Cykl Eulera to taki cykl w grafie, który przechodzi przez każdą jego krawędź dokładnie raz. Jeżeli w danym grafie możliwe jest utworzenie takiego cyklu, to jest on nazywany grafem eulerowskim.

Nazwa pochodzi od nazwiska szwajcarskiego matematyka Leonharda Eulera, który jako pierwszy zajmował się problematyką związaną z drogami w grafach. Do znajdowania cyklu Eulera w grafie można użyć algorytmu Fleury’ego. Warunkiem koniecznym i wystarczającym na to by spójny graf nieskierowany był eulerowski jest parzystość stopni wszystkich wierzchołków. Natomiast warunkiem w spójnym grafie skierowanym jest taka sama liczba krawędzi wchodzących i wychodzących dla każdego wierzchołka.

Zobacz też

• Łańcuch Eulera
• Cykl Hamiltona

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Eulerian Cycle, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).