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