Graf eulerowski
Graf eulerowski, znany również jako graf Eulera lub graf jednobieżny, jest rodzajem grafu, w którym można skonstruować cykl Eulera. Cykl ten przechodzi przez każdą krawędź grafu dokładnie raz. Problem poszukiwania cykli w grafach został po raz pierwszy podniesiony przez szwajcarskiego matematyka Leonharda Eulera w 1736 roku w kontekście mostów królewieckich. W celu znalezienia cyklu Eulera można wykorzystać algorytm Fleury’ego.
Rozważania Eulera
Euler postawił pytanie, czy w danym grafie istnieje możliwość skonstruowania ścieżki, która pozwala na przejście każdą krawędzią tylko raz. Odpowiedź brzmi, że jest to możliwe, gdy liczba wierzchołków o nieparzystym stopniu wynosi 0 lub 2.
Graf nieskierowany
Grafy, które analizował Euler, są obecnie klasyfikowane jako grafy nieskierowane. W tym kontekście:
- Stopień wierzchołka to liczba krawędzi przylegających do danego wierzchołka.
- Jeśli wszystkie wierzchołki mają stopień parzysty i graf jest spójny, można skonstruować cykl Eulera.
- Jeżeli najwyżej dwa wierzchołki mają nieparzysty stopień, możliwa jest tylko niezamknięta ścieżka Eulera.
Graf z cyklem Eulera nazywany jest grafem eulerowskim, natomiast graf z jedynie ścieżką Eulera jest określany jako półeulerowski.
Graf skierowany
Graf skierowany różni się od grafu nieskierowanego tym, że ruch odbywa się tylko w kierunkach wyznaczonych przez krawędzie. W tym przypadku:
- Stopień wchodzący to liczba krawędzi, które prowadzą do wierzchołka.
- Stopień wychodzący to liczba krawędzi, które wychodzą z wierzchołka.
Graf skierowany ma drogę Eulera, gdy wszystkie wierzchołki, z wyjątkiem dwóch, mają równe stopnie wchodzące i wychodzące. W jednym z tych wierzchołków stopień wychodzący jest o 1 większy niż wchodzący, a w drugim odwrotnie. Skierowany graf eulerowski to graf silnie spójny, w którym dla każdego wierzchołka liczba krawędzi wchodzących równa jest liczbie krawędzi wychodzących.
