Grafy eulerowskie i hamiltonowskie.

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
binio
Czasem tu bywam
Czasem tu bywam
Posty: 129
Rejestracja: 11 mar 2012, 21:45
Podziękowania: 27 razy
Otrzymane podziękowania: 32 razy
Płeć:

Grafy eulerowskie i hamiltonowskie.

Post autor: binio »

Sklejamy krawędzią dwa grafy pełne \(K_{6}\) oraz \(K_{7}\). Czy tak powstały graf jest eulerowski ? A Hamiltonowski ?
===================================
Według mnie nie jest eulerowski, bo licząc osobno, graf \(K_{6}\) ma wszystkie wierzchołki st = 5, a graf \(K_{7}\) ma wierzchołki stopnia = 6. W takim razie łącząc je krawędzią niewiele to zmieni, bo według założenia graf Eulerowski powinien mieć chyba wszystkie wierzchołki st. parzytego lub ewentualnie dwa nieparzystego, więc sklejenie i tak nic nie zmieni.
===================================
Z kolei co do Hamiltonowskiego, to każdy z osobna jak najbardziej jest i po złączeniu też chyba są, bo znajdzie się ścieżka Hamiltona, ale juz nie cykl. I teraz rodzi się moje pytanie, bo niektóre źródła podają tak, a drugie inaczej. Mianowicie, czy graf ze ścieżką (bez cyklu) można nazwać Hamiltonowskim, czy tylko Półhamiltonowskim?

Czy po prostu napisać jak takie zadanie trafię, to co napisałem powyżej? W ogóle czy mam dobry tok rozumowania ? Z góry dziękuję za odpowiedź, pozdrawiam :)
ODPOWIEDZ