szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 mar 2015, o 12: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 13: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 13: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 
 Udowodnij ze w grafie  drooone  3
 Drzewa spinające w grafie  kuba_g  1
 Twierdzenie o minimalnym stopniu w grafie k-krytycznym  Majeskas  4
 Transpozycje dowód  lgamon  1
 Skojarzenia w grafie, minimalizacja sumy długości karawędzi.  e715489  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl