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ż
edytujLinki zewnętrzne
edytuj- Eric W. Weisstein, Eulerian Cycle, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).