Potęgi grafów i cykle hamiltona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
rubik1990
Użytkownik
Użytkownik
Posty: 520
Rejestracja: 28 sty 2009, o 19:39
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 14 razy
Pomógł: 86 razy

Potęgi grafów i cykle hamiltona

Post autor: rubik1990 »

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
Dumel
Użytkownik
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

Post autor: Dumel »

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}\)
ODPOWIEDZ