Sprawdzenie, czy graf jest, lub nie jest hamiltonowski
Sprawdzenie, czy graf jest, lub nie jest hamiltonowski
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 (12.4 KiB) Przejrzano 375 razy
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Sprawdzenie, czy graf jest, lub nie jest hamiltonowski
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...
\(\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...
- mol_ksiazkowy
- Użytkownik
- Posty: 11445
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3156 razy
- Pomógł: 748 razy
Re: Sprawdzenie, czy graf jest, lub nie jest hamiltonowski
Poza tym to graf dwudzielny (niepełny) o nieparzystej liczbie wierzchołków tj. niehamiltonowski.