grafy eulerowskie i hamiltonowskie

kasienkaj91 · Post autor: **kasienkaj91** » 13 cze 2011, o 16:16

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

adek05 · Post autor: **adek05** » 13 cze 2011, o 16:26

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

kasienkaj91 · Post autor: **kasienkaj91** » 13 cze 2011, o 16:38

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

adek05 · Post autor: **adek05** » 13 cze 2011, o 16:56

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.

kasienkaj91 · Post autor: **kasienkaj91** » 13 cze 2011, o 18:57

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

adek05 · Post autor: **adek05** » 13 cze 2011, o 19:05

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

kasienkaj91 · Post autor: **kasienkaj91** » 14 cze 2011, o 16:57

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

adek05 · Post autor: **adek05** » 14 cze 2011, o 17:16

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

kasienkaj91 · Post autor: **kasienkaj91** » 14 cze 2011, o 17:35

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?

adek05 · Post autor: **adek05** » 14 cze 2011, o 17:51

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.

Inkwizytor · Post autor: **Inkwizytor** » 14 cze 2011, o 17:52

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ąć

kasienkaj91 · Post autor: **kasienkaj91** » 14 cze 2011, o 17:54

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?

adek05 · Post autor: **adek05** » 14 cze 2011, o 22:25

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

kasienkaj91 · Post autor: **kasienkaj91** » 14 cze 2011, o 23:10

Dzięki bardzo

Inkwizytor · Post autor: **Inkwizytor** » 15 cze 2011, o 00:22

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