Cykl Eulera
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
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.
Warunkiem koniecznym i wystarczającym na to by graf był eulerowski jest spójność oraz parzystość stopni wszystkich wierzchołków.
