Mam takie zadanie:
Dla każdej liczby naturalnej \(\displaystyle{ k}\) istnieje graf o spójności \(\displaystyle{ k}\), bez cyklu Hamiltona.
Trzeba wychodzić od tego,że dla każdej takiej liczby istnieje graf zawierający podgraf będący podpodziałem grafu \(\displaystyle{ K_{5}}\) i \(\displaystyle{ K_{3,3}}\)??
Cykl hamiltona w grafie
-
gardner
Cykl hamiltona w grafie
Jasne,robiłem dopiero co zadanie z planarnością i z rozpędu wpisałem.
Znalazłem warunek konieczny na obecność cyklu hamiltona:
Jeżeli graf \(\displaystyle{ G}\) jest hamiltonowski to dla każdego niepustego podzbioru \(\displaystyle{ V^{'}}\) zbioru wierzchołków \(\displaystyle{ V(G)}\) zachodzi
\(\displaystyle{ \omega (V(G)\ -\ V')\le |V'|}\)
gdzie \(\displaystyle{ \omega (G)}\) oznacza liczbę spójnych składowych grafu \(\displaystyle{ G}\).
Znalazłem warunek konieczny na obecność cyklu hamiltona:
Jeżeli graf \(\displaystyle{ G}\) jest hamiltonowski to dla każdego niepustego podzbioru \(\displaystyle{ V^{'}}\) zbioru wierzchołków \(\displaystyle{ V(G)}\) zachodzi
\(\displaystyle{ \omega (V(G)\ -\ V')\le |V'|}\)
gdzie \(\displaystyle{ \omega (G)}\) oznacza liczbę spójnych składowych grafu \(\displaystyle{ G}\).