Niespójny graf Eulera

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
mis02
Użytkownik
Użytkownik
Posty: 30
Rejestracja: 15 gru 2009, o 17:19
Płeć: Mężczyzna
Lokalizacja: ///
Podziękował: 6 razy
Pomógł: 3 razy

Niespójny graf Eulera

Post autor: mis02 »

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ć?
Jacek_Karwatka
Użytkownik
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

Post autor: Jacek_Karwatka »

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)
mis02
Użytkownik
Użytkownik
Posty: 30
Rejestracja: 15 gru 2009, o 17:19
Płeć: Mężczyzna
Lokalizacja: ///
Podziękował: 6 razy
Pomógł: 3 razy

Niespójny graf Eulera

Post autor: mis02 »

Dzięki za odpowiedź, problem rozwiązany
ODPOWIEDZ