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ż
Linki zewnętrzne
- Eric W. Weisstein, Eulerian Cycle, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.