Wykres Hanoi

Wykres Hanoi ${\ Displaystyle H_ {3} ^ {7}}$

W teorii grafów i matematyce rekreacyjnej grafy Hanoi są grafami nieskierowanymi , których wierzchołki reprezentują możliwe stany układanki Wieży Hanoi , a krawędzie reprezentują dopuszczalne ruchy między parami stanów.

Budowa

Wykres Hanoi (czarne dyski) wyprowadzony z nieparzystych wartości w trójkącie Pascala ${\ Displaystyle H_ {3} ^ {5}}$

Układanka składa się z zestawu dysków o różnych rozmiarach, umieszczonych w rosnącej kolejności na stałym zestawie wież. Wykres Hanoi dla układanki z dyskami na wieżach jest oznaczony $n}}$${$ \ displaystyle H_ {k ${$ Każdy stan układanki jest określony przez wybór jednej wieży dla każdego dysku, więc $ma$ .

W ruchach układanki najmniejszy dysk na jednej wieży jest przesuwany albo do niezajętej wieży, albo do wieży, której najmniejszy dysk jest większy. Jeśli są $wieże$ , liczba dopuszczalnych ruchów wynosi

${\ Displaystyle {\ binom {k} {2}} - {\ binom {u} {2}},}$

${2}}}$ maksimum $}$ kiedy $Displaystyle$ zero lub jeden i ${\ tbinom {u$ wynosi zero) do $($ wszystkie dyski są na jednej wieży i $Displaystyle$ k $k-1}$ ) Dlatego stopnie wierzchołków na grafie Hanoi waha się od maksimum $minimum$ k - $k-1}$ Całkowita liczba krawędzi wynosi

${\ Displaystyle {\ Frac {1} {2}} {\ binom {k} {2}} {\ bigl (} k ^ {n} - (k-2) ^ {n} {\ bigr)}.}$

Dla ${\ displaystyle k = 0}$ (bez dysków) istnieje tylko jeden stan układanki i jeden wierzchołek wykresu. Dla ${\ Displaystyle k> 0}$${\ Displaystyle H_ {k} ^ {n-1}}$ Hanoi można rozłożyć na kopie mniejszego wykresu Hanoi $\ Displaystyle H_ {k} ^ {n}} na$$displaystyle k}$ , po jednym dla każdego umieszczenia największego dysku. Te kopie są połączone ze sobą tylko w stanach, w których największy dysk może się swobodnie poruszać: jest to jedyny dysk w swojej wieży, a inna wieża jest niezajęta.

Właściwości ogólne

${\ Displaystyle H_ {3} ^ {3}}$ z 12 krawędziami usuniętymi w celu uzyskania cyklu Hamiltona

Każdy wykres Hanoi zawiera cykl Hamiltona .

Wykres $jest$ kompletnym wykresem $_$ _ _ Ponieważ zawierają pełne wykresy, wszystkie większe wykresy Hanoi $wymagają$$co$ najmniej wykresu . Można je pokolorować dokładnie $kolorami,$ sumując indeksy wież zawierających każdy dysk i używając sumy ${\ displaystyle k}$ jako kolor.

Trzy wieże

$.$ który został dobrze zbadany od czasu pracy Scorera Grundy'ego i Smitha (1944), jest przypadek wykresów Hanoi z trzema . Grafy te mają 3 ⁿ wierzchołków ( OEIS : A000244 ) i 3(3 ⁿ - 1) / 2 krawędzie ( OEIS : A029858 ). Są to wykresy groszowe ( wykresy kontaktowe nienakładających się dysków jednostkowych na płaszczyźnie), z układem dysków przypominającym trójkąt Sierpińskiego . Jednym ze sposobów skonstruowania tego układu jest ułożenie liczb trójkąta Pascala w punktach siatki sześciokątnej z odstępami jednostkowymi i umieszczenie krążka jednostkowego w każdym punkcie, którego liczba jest nieparzysta. Średnica tych wykresów i długość rozwiązania standardowej postaci układanki Wieża Hanoi (w której wszystkie dyski zaczynają się na jednej wieży i wszystkie muszą przenieść się do innej wieży) wynosi ${\ Displaystyle 2 ^ {n} -1}$ .

Więcej niż trzy wieże

Nierozwiązany problem z matematyki :

Jaka jest średnica wykresów ${\ displaystyle H_ {k} ^ {n}}$ dla ${\ displaystyle k> 3}$ ?

(więcej nierozwiązanych problemów z matematyki)

Dla ${\ displaystyle k> 3}$ struktura wykresów Hanoi nie jest tak dobrze poznana, a średnica tych wykresów jest nieznana. Gdy ${\ displaystyle k> 4}$ i ${\ displaystyle n> 0}$ lub gdy ${\ displaystyle k = 4}$ i ${\ displaystyle n> 2}$ te wykresy są niepłaskie.

Zobacz też

• Trójkąt Sierpińskiego