Matematyka.pl

Witam mam za zadanie sprawdzić czy ten graf (podany w załączniku) jest hamiltonowski. Wydaje mi się że nie jest bo żadnego cyklu hamiltona nie potrafię znaleźć ale to oczywiście nie jest żaden dowód. Ogólnie zauważyłem, że o ile na pokazanie że graf jest hamiltonowski, jest kilka sposobów np. tw. Diraca, tw. Orego czy po prostu wskazanie tego cyklu w grafie tak pokazanie że graf NIE jest hamiltonowski jest o wiele trudniejsze. Czy ktoś mógłby poradzić na co zwracać uwagę w takim przypadku?

A sprawdzałeś tw. Grinberga ? (Jest to graf planarny) a więc poniższa suma jeżeli będzie to graf hamiltonowski będzie równa zero:

\(\displaystyle{ \sum_{i=3}^{n} (i-2)(x_{i}-y_{i})=0}\)

\(\displaystyle{ n=13}\)

Gdzie: \(\displaystyle{ x_{i}, y_{i}}\) - to ściany o \(\displaystyle{ i }\)- krawędziach... (\(\displaystyle{ x_{i}}\) - zewnętrzene, \(\displaystyle{ y_{i}}\) - wewnętrzne)

U Ciebie jest:

\(\displaystyle{ 9}\) ścian o czterech krawędziach

i jedna ściana ta zewnętrzna o sześciu krawędziach, więc powyższa suma będzie miała wygląd:

(*) \(\displaystyle{ 2\left( x_{1}-y_{1}\right) +4\left( x_{2}-y_{2}\right) =0 }\)

Niech:

\(\displaystyle{ x_{i}}\) - ściany zewnętrzne, \(\displaystyle{ y_{i} }\) - ściany wewnętrzne

Ale:

\(\displaystyle{ x_{2}+y_{2}=1 \Rightarrow x_{2}=0 \wedge y_{2}=1 \vee y_{2}=0 \wedge x_{2}=1}\)

\(\displaystyle{ x_{1}+y_{1}=9}\)

Więc (*) po podstawieniach i poskracaniach będzie miał postać:

\(\displaystyle{ x_{1}-9+x_{1}+2=0 \vee x_{1}-9+x_{1}-2=0 }\)

Lub jak kto woli:

\(\displaystyle{ 2x_{1}=7 \vee 2x_{1}=11}\)

Co nie może mieć miejsca a więc graf nie będzie Hamiltonowski...

Poza tym to graf dwudzielny (niepełny) o nieparzystej liczbie wierzchołków tj. niehamiltonowski.