Planarność, izomorfizm, cykl Hamiltona

[jeth]

Witam,
mam kilka wątpliwości co do kilku zadań z grafów, prosiłbym o poradę, czy dobrze rozumuję
zadanie 1
a)
czy taki graf jest planarny?

moim zdaniem ma 9 ścian, więc wniosek ze wzoru Eulera nie jest spełniony:
\(\displaystyle{ m \le 2n-4}\)
czyli tutaj: \(\displaystyle{ m=13}\), \(\displaystyle{ 2n-4 = 10}\), zatem \(\displaystyle{ 13 \le 10}\) czyli sprzeczność, więc nie jest planarny

b) ile tu jest ścian?

odpowiedź brzmi 10?

zadanie 2
jak sprawdzić, czy grafy są izomorficzne?
ja bym to zrobił np. tak, że (oczywiście jeśli graf nie jest na tyle 'duży') policzyłbym wszystkie cykle w obu grafach, i jeśli są takie same, to grafy są izomorficzne

zadanie 3
znajdź cykl Hamiltona w podanym grafie
nie będę tutaj podawał tego grafu, ale użyłem 'algorytmu drzewa' i wyszło, że nie jest. Moje pytanie: czy 'algorytmem drzewa' zawsze można ustalić istnienie/nieistnienie cyklu hamiltonowskiego?

zadanie 4
czy w takim grafie jest skojarzenie?

chyba nie, bo skojarzenie nie musi używać wszystkich wierzchołków z całego grafu, ale musi użyć wszystkich wierzchołków z jednego zbioru. Mam rację?

Proszę o odpowiedź,
pozdrawiam.

[TPB]

Zadanie pierwsze a) - graf nie jest planarny.
Co do przykładu b), mi wychodzi również dokładnie 10 ścian.

Co do zadania 2 i kombinowania z tymi cyklami, to nie do końca. Jeżeli grafy są izomorficzne, to mają takie same cykle. Izomorficzność takie coś wymusza. Ale można sobie wyobrazić grafy, które mają takie same cykle, ale izomorficzne nie są.
Definicję izomorfizmu znajdziesz chociażby na Wikipedii, więc ja tutaj postaram Ci się wytłumaczyć to w miarę obrazowo. Dwa grafy są izomorficzne jak mają taką samą "strukturę". Weźmy ten graf z przykładu a). Nazwijmy go grafem G. Wyobraź sobie, że te krawędzie, które są takimi gładkimi liniami znajdą się w środku siedmiokąta, czyli będą jego przekątnymi. Graf wygląda inaczej, ale jest izomorficzny z grafem G. Ma taką samą strukturę. Jeżeli będziesz miał dane pewne dwa grafy i będziesz umiał sobie w wyobraźni włączyć odpowiednią 'animację' i poprzekształcać (rozciągnąć krawędzie, poodginać je itp, ale pod żadnym pozorem nie wolno Ci żadnych krawędzi dokładać czy urywać z grafu!) do tego drugiego, to będą one izomorficzne. Izomorficzny, to niemal identyczny. Izomorfizm zachowuje coś takiego jak:
-cykle (jeżeli jakiś graf ma cykl długości 5, to izomorficzny z nim także),
-st. wierzchołków i ich ilość (jeżeli jakiś graf ma dwa wierzchołki stopnia 3, to izomorficzny z nim również),
-ilość krawędzi (grafy izomorficzne mają taką samą ilość krawędzi).
I wiele innych rzeczy. Jeżeli któryś z tych warunków nie zachodzi, to nie są izomorficzne.

Co do zadania 3, to nie jestem pewny czy myślimy o tym samym algorytmie, ale wydaje mi się, że tak. Jeżeli w grafie istnieje cykl Hamiltona, to ten algorytm go znajdzie, a jak nie istnieje, to nie uzyskamy takiego cyklu.

[jeth]

super TBP, właśnie o takie rozwianie wątpliwości mi chodziło, bardzo dziękuję!
A tak przy okazji to zadam jeszcze takie pytanie: jak udowodnić twierdzenie, że "jeśli mapę sześcienną można pokolorować trzema kolorami, to jej graf jest dwudzielny" ?
szukałem w necie, ale dowodu nie znalazłem.

[TPB]

Niestety na to pytanie nie znam odpowiedzi. Nie lubię za bardzo teorii grafów, a u mnie nie dotarliśmy jeszcze do kolorowania map, więc nie bardzo wiem o czym mówimy . Ktoś bardziej kompetentny niech się wypowie.

Pozdrawiam.

[jeth]

Cóż, nie będę ukrywał, że ja wręcz nie znoszę teorii grafów, ale niestety muszę się zmierzyć z atrakcjami, jakie gwarantuje ten kurs... I tak dziękuję za wkład, pozdrawiam również

[norwimaj]

moim zdaniem ma 9 ścian,

Co to jest liczba ścian w dowolnym grafie (niekoniecznie planarnym)?

więc wniosek ze wzoru Eulera nie jest spełniony:

O jakim wniosku mowa? Nierówność \(\displaystyle{ k\le3w-6}\) jest spełniona.

b)
odpowiedź brzmi 10?

Chyba nie. \(\displaystyle{ s=2+k-w=2+15-10\ne10}\).