Ł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.
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ż
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.