Dowód na istnienie cyklu Hamiltona w grafie kostki
-
luki1423
- Użytkownik
- Posty: 4
- Rejestracja: 16 mar 2015, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: olsz
- Podziękował: 1 raz
Dowód na istnienie cyklu Hamiltona w grafie kostki
Witam. Zna ktoś może jakiś dowód na cykl Hamiltona w grafie kostki?
-
Everard
- Użytkownik
- Posty: 166
- Rejestracja: 11 lip 2007, o 22:59
- Płeć: Mężczyzna
- Lokalizacja: Bytom
- Pomógł: 49 razy
Dowód na istnienie cyklu Hamiltona w grafie kostki
Indukcja. Oczywiście taki istnieje jeżeli nasza kostka jest jednowymiarowa. Jeżeli wiemy, że taki cykl istnieje dla kostki \(\displaystyle{ n}\)-wymiarowej, to kostka \(\displaystyle{ n+1}\)-wymiarowa to po prostu dwie zlepione kostki \(\displaystyle{ n}\)-wymiarowe. Przejdź cyklem Hamiltona startującym z tego punktu łączącego po jednej kostce, przejdź do drugiej, zhamiltonuj drugą, wróć.
Bardziej formalnie: Niech \(\displaystyle{ Q_n=\{0,1\}^n}\), gdzie dwa ciągi zerojedynkowe są połączone jeżeli różnią się dokładnie jednym wyrazem. Widzimy, że wówczas \(\displaystyle{ Q_{n+1}=\{0,1\}\times Q_n}\). Przypuśćmy indukcyjnie, że \(\displaystyle{ Q_n}\) posiada cykl Hamiltona. Dla ustalenia uwagi, niech cykl ten startuje z wierzchołka \(\displaystyle{ (0,...,0)}\) i kończy na \(\displaystyle{ (1,0,...,0)}\). Wówczas nasz cykl Hamiltona w \(\displaystyle{ Q_{n+1}}\) wygląda następująco:
\(\displaystyle{ (0,0,...,0)\underbrace{\rightarrow \dots \rightarrow}_{\mbox{ cykl Hamiltona}} (0,1,0...,0) \rightarrow (1,1,...,0)\underbrace{\rightarrow \dots \rightarrow}_{\mbox{ cykl Hamiltona w odwrotnej kolejności}} (1,0,...,0)}\)
Bardziej formalnie: Niech \(\displaystyle{ Q_n=\{0,1\}^n}\), gdzie dwa ciągi zerojedynkowe są połączone jeżeli różnią się dokładnie jednym wyrazem. Widzimy, że wówczas \(\displaystyle{ Q_{n+1}=\{0,1\}\times Q_n}\). Przypuśćmy indukcyjnie, że \(\displaystyle{ Q_n}\) posiada cykl Hamiltona. Dla ustalenia uwagi, niech cykl ten startuje z wierzchołka \(\displaystyle{ (0,...,0)}\) i kończy na \(\displaystyle{ (1,0,...,0)}\). Wówczas nasz cykl Hamiltona w \(\displaystyle{ Q_{n+1}}\) wygląda następująco:
\(\displaystyle{ (0,0,...,0)\underbrace{\rightarrow \dots \rightarrow}_{\mbox{ cykl Hamiltona}} (0,1,0...,0) \rightarrow (1,1,...,0)\underbrace{\rightarrow \dots \rightarrow}_{\mbox{ cykl Hamiltona w odwrotnej kolejności}} (1,0,...,0)}\)