Łańcuch Eulera

Ł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ż

• zagadnienie mostów królewieckich
• Cykl Eulera