Łańcuch Eulera (droga Eulera, ścieżka Eulera, szlak Eulera) to taka ścieżka w grafie, która przechodzi przez każdą jego krawędź dokładnie raz. Jeżeli w danym grafie możliwe jest utworzenie takiej drogi, to jest on nazywany grafem półeulerowskim.
Graf eulerowski
Osobny artykuł: Graf eulerowski.
Nazwa pochodzi od nazwiska szwajcarskiego matematyka Leonharda Eulera, który jako pierwszy, zajmował się problematyką związaną z drogami w grafach.
Aby spójny graf nieskierowany był półeulerowski może posiadać maksymalnie 2 wierzchołki nieparzystego stopnia. Analogicznie, aby spójny graf skierowany był półeulerowski może posiadać maksymalnie 2 wierzchołki, w których liczba krawędzi wchodzących i wychodzących różni się o 1.
Zobacz też
Najważniejsze pojęcia |
|
---|
Wybrane klasy grafów |
|
---|
Algorytmy grafowe |
|
---|
problemy grafowe |
|
---|
Inne zagadnienia |
|
---|