szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 mar 2015, o 13:19 
Użytkownik

Posty: 4
Lokalizacja: olsz
Witam. Zna ktoś może jakiś dowód na cykl Hamiltona w grafie kostki?
Góra
Mężczyzna Offline
PostNapisane: 16 mar 2015, o 14:04 
Użytkownik

Posty: 166
Lokalizacja: Bytom
Indukcja. Oczywiście taki istnieje jeżeli nasza kostka jest jednowymiarowa. Jeżeli wiemy, że taki cykl istnieje dla kostki n-wymiarowej, to kostka n+1-wymiarowa to po prostu dwie zlepione kostki n-wymiarowe. Przejdź cyklem Hamiltona startującym z tego punktu łączącego po jednej kostce, przejdź do drugiej, zhamiltonuj drugą, wróć.

Bardziej formalnie: Niech 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 Q_{n+1}=\{0,1\}\times Q_n. Przypuśćmy indukcyjnie, że Q_n posiada cykl Hamiltona. Dla ustalenia uwagi, niech cykl ten startuje z wierzchołka (0,...,0) i kończy na (1,0,...,0). Wówczas nasz cykl Hamiltona w Q_{n+1} wygląda następująco:
(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)
Góra
Mężczyzna Offline
PostNapisane: 16 mar 2015, o 14:51 
Użytkownik

Posty: 4
Lokalizacja: olsz
A może wiesz jak policzyć ilość cykli w Q_{4} ?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Teoria grafów] dowód, graf dwudzielny, graf planarny  matinf  3
 zliczyć liczbę spójnych składowych w grafie dla permutacji.  matinf  2
 Dowód pokolorowania płaszczyzny i okregów dwoma kolorami  Oleszko12  1
 Elementy zbioru, drogi w grafie  novikxxx  1
 Dowód, dwumian Newtona  withdrawn  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl