Łańcuch Eulera

Łańcuch Eulera

Łańcuch Eulera, znany również jako droga, ścieżka lub szlak Eulera, to ścieżka w grafie, która przechodzi przez każdą krawędź dokładnie raz. Graf, w którym można utworzyć taką drogę, nazywany jest grafem półeulerowskim.

Graf eulerowski

Nazwa „Łańcuch Eulera” pochodzi od szwajcarskiego matematyka Leonharda Eulera, który jako pierwszy badał problemy związane z drogami w grafach. Aby spójny graf nieskierowany był półeulerowski, musi spełniać określone warunki:

• Może mieć maksymalnie 2 wierzchołki o nieparzystym stopniu.

W przypadku spójnych grafów skierowanych, warunki te są następujące:

• Maksymalnie 2 wierzchołki, w których liczba krawędzi wchodzących i wychodzących różni się o 1.