Graf półeulerowski

Graf półeulerowski (graf semieulerowski) – graf rozważany w teorii grafów. Graf półeulerowski zawiera w sobie ścieżkę, która pozwala przejść przez wszystkie jego krawędzie tylko raz. Ścieżka ta nazywana jest ścieżką Eulera.

Graf półeulerowski

Graf eulerowski

Jeżeli ścieżka Eulera jest zamknięta, to nazywana jest cyklem Eulera. Graf zawierający taki cykl nazywany jest eulerowskim. Nazwa pochodzi od nazwiska szwajcarskiego matematyka Leonharda Eulera, który jako pierwszy, zajmował się problematyką związaną z drogami w grafach.

Rozważania Eulera

Zagadnienie rozważane przez Eulera można przedstawić w następujący sposób:

Jeżeli mamy określony graf, to czy możliwe jest skonstruowanie ścieżki, która pozwala na przejście każdej krawędzi grafu tylko raz?

Euler stwierdził, że aby możliwe było zbudowanie takiej ścieżki, liczba wierzchołków nieparzystego stopnia musi wynosić 0 lub 2.