Udowodnić, że graf \(\displaystyle{ L(G)}\) ma cykl Hamiltona jeśli graf prosty \(\displaystyle{ G}\) jest hamiltonowski lub eulerowski.
Uwagi:
Graf \(\displaystyle{ L(G)}\) jest to graf którego wierzchołkom odpowiadają jednoznacznie krawędzie grafu \(\displaystyle{ G}\), a wierzchołki w \(\displaystyle{ L(G)}\) są połączone krawędzią, jeśli odpowiadające im \(\displaystyle{ G}\) te krawędzi są połączone, tj. mają wspólny wierzchołek.
Np. gdy \(\displaystyle{ G}\) ma 4 wierzchołki (litera Y) to \(\displaystyle{ L(G)}\) jest \(\displaystyle{ K_3}\) (trójkąt). Dorysowanie w \(\displaystyle{ G}\) czwartej krawędzi da \(\displaystyle{ L(G)}\) o pięciu krawędziach itd.
Własność grafu krawędziowego
-
mol_ksiazkowy
- Użytkownik
- Posty: 11403
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
-
MatXXX
- Użytkownik
- Posty: 59
- Rejestracja: 2 gru 2014, o 18:25
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 17 razy
Własność grafu krawędziowego
Niech \(\displaystyle{ G}\) posiada cykl Eulera \(\displaystyle{ C_e=(e_1,e_2, ... e_n)}\). Wtedy dla \(\displaystyle{ i\in[1,n-1]}\) prawdą jest, że \(\displaystyle{ e_i}\) oraz \(\displaystyle{ e_{i+1}}\) posiadają wspólny wierzchołek. To samo dla \(\displaystyle{ e_1}\) i \(\displaystyle{ e_n}\). W grafie \(\displaystyle{ L(G)}\) cykl Hamiltona stworzą wierzchołki odpowiadające cyklowi Eulera w \(\displaystyle{ G}\), bo są one wszystkimi wierzchołkami \(\displaystyle{ L(G)}\), dwa kolejne są zawsze połączone, nie przechodzimy przez żaden z nich dwukrotnie, połączone są w cykl.
Niech \(\displaystyle{ G}\) posiada cykl Hamiltona \(\displaystyle{ C_h=(v_1,v_2,..v_n)}\). Wtedy cykl ten korzysta z krawędzi \(\displaystyle{ e_{i,i+1}}\) łączących wierzchołki \(\displaystyle{ v_i}\) oraz \(\displaystyle{ v_{i+1}}\) a do tego z krawędzi \(\displaystyle{ e_{n,1}}\), niech zbiór tych krawędzi to \(\displaystyle{ E_h}\). Oprócz nich istnieją w \(\displaystyle{ G}\) inne krawędzie łączące pewne dwa wierzchołki należące do cyklu Hamiltona.
Utwórzmy z graf krawędziowy tylko z podgrafu zawierającego \(\displaystyle{ C_h}\) oraz \(\displaystyle{ E_h}\). W \(\displaystyle{ E_h}\) krawędzie się nie powtarzają i każda ma wspólny wierzchołek z dwoma innymi, różnymi od siebie krawędziami, więc tak utworzony graf krawędziowy będzie cyklem, a więc będzie cyklem Hamiltona.
Teraz będziemy dokładać brakujące krawędzie indukcyjnie.
Baza: Weźmy pewną krawędź \(\displaystyle{ e=(v_x,v_y)}\) nie należącą do \(\displaystyle{ E_h}\). Wybierzmy dokładnie jeden z dwóch wierzchołków krańcowych. Bez straty ogólności wybierzmy \(\displaystyle{ v_x}\). Wiemy, że do grafu krawędziowego należą wierzchołki \(\displaystyle{ v_{x, x+1\pmod{n}}}\) oraz \(\displaystyle{ v_{x-1\pmod{n}, x}}\). Dołóżmy wierzchołek \(\displaystyle{ v_{x,y}}\) odpowiadający dokładanej krawędzi. Wtedy powstała 3-klika z wierzchołków \(\displaystyle{ v_{x,y}, v_{x-1\pmod{n}, x}, v_{x, x+1\pmod{n}}}\). A więc w początkowym cyklu Hamiltona możemy zastąpić \(\displaystyle{ v_{x-1\pmod{n}, x}, v_{x, x+1}}\) przez ścieżkę Hamiltona z tejże kliki z początkiem w \(\displaystyle{ v_{x,y}, v_{x-1\pmod{n}, x}}\) a końcem w \(\displaystyle{ v_{x, x+1\pmod{n}}}\).
Krok indukcyjny analogicznie, bo po dołożeniu wierzchołka do grafu krawędziowego powstanie klika z elementów już wcześniej dołożonych (może ich nie być) oraz dołożonego w tym kroku, czyli można wybrać analogiczną ścieżkę Hamiltona, którą zastąpimy fragment początkowego cyklu.
Niech \(\displaystyle{ G}\) posiada cykl Hamiltona \(\displaystyle{ C_h=(v_1,v_2,..v_n)}\). Wtedy cykl ten korzysta z krawędzi \(\displaystyle{ e_{i,i+1}}\) łączących wierzchołki \(\displaystyle{ v_i}\) oraz \(\displaystyle{ v_{i+1}}\) a do tego z krawędzi \(\displaystyle{ e_{n,1}}\), niech zbiór tych krawędzi to \(\displaystyle{ E_h}\). Oprócz nich istnieją w \(\displaystyle{ G}\) inne krawędzie łączące pewne dwa wierzchołki należące do cyklu Hamiltona.
Utwórzmy z graf krawędziowy tylko z podgrafu zawierającego \(\displaystyle{ C_h}\) oraz \(\displaystyle{ E_h}\). W \(\displaystyle{ E_h}\) krawędzie się nie powtarzają i każda ma wspólny wierzchołek z dwoma innymi, różnymi od siebie krawędziami, więc tak utworzony graf krawędziowy będzie cyklem, a więc będzie cyklem Hamiltona.
Teraz będziemy dokładać brakujące krawędzie indukcyjnie.
Baza: Weźmy pewną krawędź \(\displaystyle{ e=(v_x,v_y)}\) nie należącą do \(\displaystyle{ E_h}\). Wybierzmy dokładnie jeden z dwóch wierzchołków krańcowych. Bez straty ogólności wybierzmy \(\displaystyle{ v_x}\). Wiemy, że do grafu krawędziowego należą wierzchołki \(\displaystyle{ v_{x, x+1\pmod{n}}}\) oraz \(\displaystyle{ v_{x-1\pmod{n}, x}}\). Dołóżmy wierzchołek \(\displaystyle{ v_{x,y}}\) odpowiadający dokładanej krawędzi. Wtedy powstała 3-klika z wierzchołków \(\displaystyle{ v_{x,y}, v_{x-1\pmod{n}, x}, v_{x, x+1\pmod{n}}}\). A więc w początkowym cyklu Hamiltona możemy zastąpić \(\displaystyle{ v_{x-1\pmod{n}, x}, v_{x, x+1}}\) przez ścieżkę Hamiltona z tejże kliki z początkiem w \(\displaystyle{ v_{x,y}, v_{x-1\pmod{n}, x}}\) a końcem w \(\displaystyle{ v_{x, x+1\pmod{n}}}\).
Krok indukcyjny analogicznie, bo po dołożeniu wierzchołka do grafu krawędziowego powstanie klika z elementów już wcześniej dołożonych (może ich nie być) oraz dołożonego w tym kroku, czyli można wybrać analogiczną ścieżkę Hamiltona, którą zastąpimy fragment początkowego cyklu.