Liczba cykli hamiltonowskich na wykresie Sierpińskiego


18

Jestem nowy na tym forum i jestem tylko fizykiem, który robi to, aby utrzymać swój mózg w dobrej formie, więc proszę okaż łaskę, jeśli nie używam najbardziej eleganckiego języka. Proszę również zostawić komentarz, jeśli uważasz, że inne tagi byłyby bardziej odpowiednie.

Próbuję rozwiązać ten problem, dla którego muszę obliczyć liczbę cykli hamiltonowskich w tym rzędzie Sierpińskiego-wykresu . (Zobacz także powyższy link do definicji i zdjęć wykresów Sierpińskiego)n S nC(n)nSn

Znalazłem , ale musiałem coś pomieszać, ponieważ moje rozwiązanie nie pasuje do podanej wartości . Moja argumentacja składa się z bardzo podstawowych myśli i nie mogę znaleźć błędu. Każda pomoc jest mile widziana. Nawet jeśli wydaje się to długie, myśli stają się trywialne, jeśli spojrzysz na wykresy podczas śledzenia.C ( 5 ) = 71328803586048C(n)C(5)=71328803586048

(a) W danym wykresie wywołać zewnętrzne narożniki . Następnie określam następujące ilości: A , B , CSnA,B,C

N(n):= liczba Hamiltona ścieżki do .C.AC

N¯(n):= liczba ścieżek od do , które odwiedzają każdy węzeł raz wyjątkiem .C BACB

Nazwie też takie ścieżki - lub - ścieżki typu poniżej.ˉ NNN¯

(b) Łatwo zauważyć, że N(n)=N¯(n) .

Powód jest następujący: Rozważ ścieżkę typu NPocząwszy od A ścieżka ta ma postać (A,...,X1,B,X2,...,C) . Zastępując segment (X1,B,X2) przez (X1,X2) , otrzymujemy ścieżkę typu N¯ . Ta operacja jednoznacznie odwzorowuje wszystkie ścieżki typu N ścieżki typu N¯ .

(c) Wyprowadzamy rekurencję .N(n+1)=2N(n)3

Weźmy pod uwagę ścieżkę typu od do i oznaczymy podtróby w zewnętrznych narożnikach przez . Oczywiste jest, że ścieżka typu odwiedzi każdy podtok dokładnie raz, zaczynając od przez do . Rozważmy teraz węzeł w którym dotykają się podteksty i . Istnieją dwie możliwości, gdy ścieżka jest odwiedzana przez ten punkt: (i) przed opuszczeniem lub (ii) po wejściu doA B A , B , C T A , T B , T C N T A T B T C Z T A T CNABA,B,CTA,TB,TCNTATBTCZTATCTATC. W takich przypadkach te trzy podścieżki wewnątrz są rodzajów : (i) lub (II) , odpowiednio. Mając to na uwadze, możemy liczyćTA,TB,TC N,N,N¯ N¯,N,N

N(n+1)=N(n)N(n)N¯(n)+N¯(n)N(n)N(n) i (b) otrzymujemy górny rekurencja.

(d) Rozwiązujemy rekurencję (c) z i otrzymujemy .N(1)=1N(n)=230+31+...+3n2

(e) Rozważmy cykl hamiltonowski na wykresie . Ponieważ każdy z trzech podrygentów jest połączony z innymi tylko za pomocą dwóch węzłów, jasne jest, że cykl wejdzie do każdego pod-trójkąta dokładnie raz przez jeden węzeł łączący, a następnie „wypełni” go, a na koniec opuści przez drugi węzeł łączący. Stąd cykl Hamiltonian w składa się z trzech podścieżek typu w podtangulach, z których wszystkie mają strukturę . Możemy wnioskować o liczbie cykli hamiltonowskichSnSnNSn1

C(n)=N(n1)3 .

Wynika to jednak dlan=5

C(5)=N(4)3=81923=54975581388871328803586048

gdzie to ostatnie należy uzyskać zgodnie ze stroną problemu (link powyżej).

Jeszcze raz dziękuję za wszelką pomoc lub komentarze.


To jest naprawdę zabawne, wywnioskowałem wszystko z tych samych pomysłów i popełniłem dokładnie ten sam błąd =) Czy już to rozwiązałeś?
flawr

Odpowiedzi:


11

Dobry pomysł! Problem wydaje się znajdować na etapie . Zastąpienie ( X 1 , B , X 2 ) w N- ścieżce przez ( X 1 , X 2 ) daje ˉ N- ścieżkę, ale nie każda ˉ N- ścieżka zawiera ( X 1 , X 2 ) . Więc to nie jest bijection. To tylko mówi N ( n ) ˉ N ( n ) .(b)(X1,B,X2)N(X1,X2)N¯N¯(X1,X2)N(n)N¯(n)

Lub możesz faktycznie wykazać, że , co daje N ( n + 1 ) = 3 N 3 .N¯(n)=3N(n)/2N(n+1)=3N3


Dzięki, złożyłeś mój dzień + kolejne podziękowania za pozostawienie poprawnego dowodu jako ćwiczenia dla mnie!
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.