szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna
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?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
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
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 
 Graf Hamiltona i krawędź cięcia - zadanie 16  moncq  1
 Planarność, izomorfizm, cykl Hamiltona  jeth  5
 Ile jest permutacji z jedynką w cyklu długości k  Heniek1991  0
 Indukcja po grafie  matinf  1
 Przecięcia krawędzi w grafie  calusnik  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl