Matematyka.pl

Przedstaw cztery pięciowierzchołkowe grafy: a) niehamiltonowski i nieeulerowski, b)
eulerowski i hamiltonowski, c) eulerowski, ale nie hamiltonowski, d) hamiltonowski, ale
nie eulerowski.

Warunek na to, żeby graf mial cykl Eulera znasz? Tu naprawdę nie trzeba wiele, nieco rysowania

Wiem,że jak się to zrozmumie,to jest proste.Ale my tego nie mieliśmy na ćwiczeniach a wiem że na egzaminie może się pojawić.A co do tego warunku to mam zapisane,że cykl Eulera to szlak domknięty,przechodzący przez wszystkie krawędzie grafu,ale jakoś w praktyce nie potrafię zastosować tej definicji

No to jest trochę mało. Graf ma cykl Eulera wttw. gdy stopnie wszystkich wierzchołków są parzyste. Spróbuj to zastosować, w przypadku cyklu Hamiltona wystarczy tylko definicja, bo też nie ma takiego warunku jak na cykl Eulera.

A możesz pokazać jakiś podkunkt,bo nadal tego nie rozumiem.

Najpierw postaram się zmusić Ciebie do pokazania jakiegoś podpunktu, Twoich prób. Zrób to, na podstawie Twoich ewentualnych błędów dojdziemy do rozwiązania

-- 14 cze 2011, o 16:58 --to jest rysunek do podpunktu c ale nie wiem czy dobrze

Super! Jest dobrze, czy spróbujesz uzasadnić, dlaczego nie ma cyklu Hamiltona? Jakiś taki argument, który przekona każdego.

No więc cykl Eulera istnieje,ponieważ każdy wierzchołek ma parzysty stopień,a nie ma cyklu Hamiltona,ponieważ jeżeli robię szlak z wierzchołka A i po kolei przechodzę przez wierzchołki:D,B,C,D,E,A,to przez D przechodzę 2 razy a w cyklu Hamiltona przez kazdy wierzchołek mogę przejść tylko raz?

No nie jest to do końca ścisłe, raczej chodzi o to, że musisz przejść przez ten wierzchołek węzłowy conajmniej dwa razy.
Teraz spróbuj inne przykłady, wydaje mi się, że są nawet łątwiejsze od tego.

a) nieeulerowski i niehamiltonowski ---> jaki znasz typ grafu w którym masz kilka wierzchołków st. nieparzystego (np \(\displaystyle{ d_v=1}\))?
b) eulerowski i hamiltonowski ---> jaki stopień muszą mieć wierzchołki by oba warunki zachodziły jednocześnie? I jaki graf bedzie nam to spełniał?
d) hamiltonowski, nieeulerowski ---> przykład z wikipedii może Cię łatwo natchnąć

podpunkt d

-- 14 cze 2011, o 18:06 --

podpunkt a,dobrze?

-- 14 cze 2011, o 18:14 --

i podpunkt b-- 14 cze 2011, o 21:53 --adek05 możesz zobaczyć czy dobrze narysowałam te grafy?

Jest okej. W a wystarczyłby graf bez krawędzi, w b cykl ale to jest jak najbardziej okej.

Dzięki bardzo

Dodam tylko jeszcze jako uzupełnienie o co mi chodziło w podpowiedziach
a) dowolne drzewo
b) zwykły pięciokąt