Witam. Mam dwa grafy i muszę określić, który jest eulerowski, a który półeulerowski i narysować ścieżkę/cykl Eulera.
W jaki prosty sposób, znaleźć między nimi różnice? (W praktyce, bo teorię znam) i od czego dobrze jest zacząć rysowanie ścieżki/cyklu? Prosiłbym o pomoc w tych dwóch konkretnych przypadkach.
Graf eulerowski a półeulerowski
-
Paulina-Anna
- Użytkownik
- Posty: 201
- Rejestracja: 6 gru 2009, o 14:57
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 16 razy
- Pomógł: 24 razy
Graf eulerowski a półeulerowski
1) Jeśli graf ma jakikolwiek wierzchołek nieparzystego stopnia, to nie ma w nim cyklu eulerowskiego.
Jeśli graf jest spójny i każdy wierzchołek jest parzystego stopnia, to istnieje co najmniej jeden cykl eulerowski.
2) Jeśli graf ma więcej niż \(\displaystyle{ 2}\) wierzchołki nieparzystego stopnia, to nie może mieć ścieżki eulerowskiej.
Jeśli graf jest spójny i ma dokładnie dwa wierzch. niep. stopnia, to ma co najmniej jedną eulerowską ścieżkę, która musi zaczynać się w jednym z wierzch. niep. stopnia i kończyć w innym wierzch. niep. stopnia.
3) Suma stopni wszystkich wierzchołków grafu jest liczbą parzystą (dwa razy liczba krawędzi).
W każdym grafie liczba wierzchołków nieparzystego stopnia jest parzysta.
Algorytm Fleury'ego w grafie spójnym, w którym każdy wierzchołek jest parzystego stopnia:
Jeśli graf jest spójny i każdy wierzchołek jest parzystego stopnia, to istnieje co najmniej jeden cykl eulerowski.
2) Jeśli graf ma więcej niż \(\displaystyle{ 2}\) wierzchołki nieparzystego stopnia, to nie może mieć ścieżki eulerowskiej.
Jeśli graf jest spójny i ma dokładnie dwa wierzch. niep. stopnia, to ma co najmniej jedną eulerowską ścieżkę, która musi zaczynać się w jednym z wierzch. niep. stopnia i kończyć w innym wierzch. niep. stopnia.
3) Suma stopni wszystkich wierzchołków grafu jest liczbą parzystą (dwa razy liczba krawędzi).
W każdym grafie liczba wierzchołków nieparzystego stopnia jest parzysta.
Algorytm Fleury'ego w grafie spójnym, w którym każdy wierzchołek jest parzystego stopnia: