Graf nieplenarny, hamiltonowski, nieeulerowski

stachurskipiotr424 · Post autor: **stachurskipiotr424** » 24 cze 2016, o 02:16

Mam takie zadanie muszę stwierdzić czy istnieje graf nieplanarny hamiltonowski, nieeulerowski którego maksymalny stopień wierzchołka jest \(\displaystyle{ \le 4}\), jeżeli tak to mam podać jego przykład, a jeżeli nie mam mam to uzasadnić.
Proszę o pomoc

mostostalek · Post autor: **mostostalek** » 24 cze 2016, o 17:15

\(\displaystyle{ K_{3,3}}\)?

stachurskipiotr424 · Post autor: **stachurskipiotr424** » 25 cze 2016, o 20:47

Dziękuje za odpowiedź, czyli masz na myśli np. ten graf?

... h_K3,3.svg

on na pewno jest nieeulerowski, i według mnie jest hamiltonowski.

Co Ty o tym sądzisz?

mostostalek · Post autor: **mostostalek** » 26 cze 2016, o 12:02

Nie tylko według Ciebie jest hamiltonowski.. On jak najbardziej jest hamiltonowski.. Wystarczy znaleźć ścieżkę Hamiltona.. Do tego ma własności, które potrzebowałeś: \(\displaystyle{ deg(v)=3}\) dla każdego \(\displaystyle{ v}\) oraz jest nieplanarny.. Wynika to choćby z twierdzenia mówiącego, że graf jest planarny kiedy nie zawiera podgrafu \(\displaystyle{ K_{3,3} \ \hbox{i }K_5}\)