Na początek podam definicję:
Jeśli \(\displaystyle{ G=(V,E)}\) to k-tą potęgą grafu G nazywamy graf \(\displaystyle{ G^{k}=(V,E_{k})}\), gdzie dla każdej pary wierzchołków \(\displaystyle{ x}\) i \(\displaystyle{ y}\), \(\displaystyle{ xy \in E_{k} \Leftrightarrow dist_{G} \{x,y\}\le k}\)
Mam problem z tym zadaniem :
Jeśli \(\displaystyle{ G}\) jest spójny to graf \(\displaystyle{ G^{3}}\) jest grafem Hamiltona
Proszę o wskazówki
Potęgi grafów i cykle hamiltona
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Potęgi grafów i cykle hamiltona
wystarczy to udowodnić dla drzew , a dla grafów z cyklami rozważyć wtedy dowolne drzewo rozpinające.
aby to zaindukowac wzmocnie nieco teze (G niech bedzie drzewem):
w grafie \(\displaystyle{ G^3}\) istnieje cykl Hamiltona \(\displaystyle{ v_1 \to v_2 \to ... \to v_n \to v_1}\) taki ze
\(\displaystyle{ d_G(v_1,v_n)=1}\)
n - liczba wierzchołków.
dla małych n łatwo sprawdzić że jest to prawda.
weźmy n+1 wierzchołkowe drzewo ukorzenione. \(\displaystyle{ u}\) - korzeń. \(\displaystyle{ t_1,...,t_k}\) - wierzchołki incydentne z u. Najpierw lecimy z \(\displaystyle{ u}\) do \(\displaystyle{ t_1}\). jeśli \(\displaystyle{ t_1}\) jest liściem to lecimy do \(\displaystyle{ t_2}\). jeśli nie to wykorzystujemy założenie indukcyjne dla poddrzewa ukorzenionego w \(\displaystyle{ t_1}\), przy czym otrzymany cykl ucinamy na końcu. mamy wiec sciezke Hamiltona w poddrzewie, zaczynającą się w \(\displaystyle{ t_1}\) i kończącą się w \(\displaystyle{ v}\) incydentnym z \(\displaystyle{ t_1}\). tak się fajnie składa że teraz z \(\displaystyle{ v}\) możemy polecieć do \(\displaystyle{ t_2}\) i powtórzyć procedurę. Na koniec coś tam połączymy z \(\displaystyle{ u}\) i dostaniemy cykl Hamiltona. Aby zakończyć dowód trzeba jeszcze pokazać że istnieje cykl Hamiltona o własności podanej w tezie indukcyjnej. Ale to jest łatwe, bo wytarczy drzewo ukorzenić w wierzchołku incydentnym z dowolnym liściem \(\displaystyle{ l}\), i \(\displaystyle{ l}\) odwiedzić na samym końcu procedury, tj \(\displaystyle{ t_k=l}\)
aby to zaindukowac wzmocnie nieco teze (G niech bedzie drzewem):
w grafie \(\displaystyle{ G^3}\) istnieje cykl Hamiltona \(\displaystyle{ v_1 \to v_2 \to ... \to v_n \to v_1}\) taki ze
\(\displaystyle{ d_G(v_1,v_n)=1}\)
n - liczba wierzchołków.
dla małych n łatwo sprawdzić że jest to prawda.
weźmy n+1 wierzchołkowe drzewo ukorzenione. \(\displaystyle{ u}\) - korzeń. \(\displaystyle{ t_1,...,t_k}\) - wierzchołki incydentne z u. Najpierw lecimy z \(\displaystyle{ u}\) do \(\displaystyle{ t_1}\). jeśli \(\displaystyle{ t_1}\) jest liściem to lecimy do \(\displaystyle{ t_2}\). jeśli nie to wykorzystujemy założenie indukcyjne dla poddrzewa ukorzenionego w \(\displaystyle{ t_1}\), przy czym otrzymany cykl ucinamy na końcu. mamy wiec sciezke Hamiltona w poddrzewie, zaczynającą się w \(\displaystyle{ t_1}\) i kończącą się w \(\displaystyle{ v}\) incydentnym z \(\displaystyle{ t_1}\). tak się fajnie składa że teraz z \(\displaystyle{ v}\) możemy polecieć do \(\displaystyle{ t_2}\) i powtórzyć procedurę. Na koniec coś tam połączymy z \(\displaystyle{ u}\) i dostaniemy cykl Hamiltona. Aby zakończyć dowód trzeba jeszcze pokazać że istnieje cykl Hamiltona o własności podanej w tezie indukcyjnej. Ale to jest łatwe, bo wytarczy drzewo ukorzenić w wierzchołku incydentnym z dowolnym liściem \(\displaystyle{ l}\), i \(\displaystyle{ l}\) odwiedzić na samym końcu procedury, tj \(\displaystyle{ t_k=l}\)