Czy graf Eulera może być niespójny?
Definicja jest taka:
"Graf eulerowski odznacza się tym, że da się w nim skonstruować cykl Eulera, czyli cykl, który przechodzi przez każdą jego krawędź dokładnie raz i wraca do punktu wyjściowego."
I jeszcze takie twierdzenie:
"Twierdzenie Eulera: W grafie można znaleźć cykl Eulera wtedy i tylko wtedy, gdy graf jest spójny i każdy jego wierzchołek ma parzysty stopień."
No i teraz biore najprostszy przypadek:
Pełny graf K3 (spójny, eulerowski)
Dokładam do zbioru wierzchołków wierzchołek izolowany. Mam 3 wierzchołki połączone w cykl i jeden luźny.
Do definicji pasuje a twierdzeniu Eulera przeczy. Jak to rozumieć?
Niespójny graf Eulera
-
- Użytkownik
- Posty: 351
- Rejestracja: 2 maja 2012, o 16:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 94 razy
Niespójny graf Eulera
To uproszczone definicja i nie obejmuje przypadku który przedstawiłeś.
Inna definicja określa nieskierowany graf eulerowski jako graf spójny, dla którego wszystkie wierzchołki są stopnia parzystego tak jak w twierdzeniu.
Można też złagodzić warunki twierdzenia mówiąc o spójności krawędziowej (dopuszczalne są wierzchołki izolowane). To czy przedstawiony przez Ciebie przykład zaliczyć do klasy grafów Eulera to w dużej mierze kwestia umowy. Na ogól odrzuca się przypadki grafów niespójnych (chociaż spójnych krawędziowo)
Inna definicja określa nieskierowany graf eulerowski jako graf spójny, dla którego wszystkie wierzchołki są stopnia parzystego tak jak w twierdzeniu.
Można też złagodzić warunki twierdzenia mówiąc o spójności krawędziowej (dopuszczalne są wierzchołki izolowane). To czy przedstawiony przez Ciebie przykład zaliczyć do klasy grafów Eulera to w dużej mierze kwestia umowy. Na ogól odrzuca się przypadki grafów niespójnych (chociaż spójnych krawędziowo)