Sprawdzenie, czy graf jest, lub nie jest hamiltonowski

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
KLR_S
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 1 gru 2021, o 20:56
Płeć: Mężczyzna
wiek: 20

Sprawdzenie, czy graf jest, lub nie jest hamiltonowski

Post autor: KLR_S »

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?
Załączniki
Zrzut ekranu 2022-01-17 201559.png
Zrzut ekranu 2022-01-17 201559.png (12.4 KiB) Przejrzano 345 razy
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Sprawdzenie, czy graf jest, lub nie jest hamiltonowski

Post autor: arek1357 »

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...
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Re: Sprawdzenie, czy graf jest, lub nie jest hamiltonowski

Post autor: mol_ksiazkowy »

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