Algorytmy

Cykl Eulera

  • 2007-05-28 17:28
  • 0 komentarzy
  • 1618 odsłon
  • Oceń ten tekst jako pierwszy
Cykl Eulera to taka droga w grafie, która przechodzi przez każdą jego krawędź dokładnie raz i powraca do początku (jest zamknięta). Jeżeli w danym grafie możliwe jest utworzenie takiej drogi, 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 znajdywania cyklu Eulera w grafie można użyć algorytmu Fleury'ego. Warunkiem koniecznym i wystarczającym na to by graf nieskierowany był eulerowski jest spójność oraz parzystość stopni wszystkich wierzchołków. Natomiast warunkiem w grafie skierowanym jest spójność oraz taka sama ilość krawędzi wchodzących i wychodzących dla każdego wierzchołka.