하노이 그래프

그래프 이론과 레크리에이션 수학에서, 하노이 그래프는 정점이 하노이 탑 퍼즐의 가능한 상태를 나타내고, 가장자리가 상태 쌍들 간의 허용 가능한 움직임을 나타내는 방향성이 없는 그래프다.

건설

퍼즐은 크기가 다른 디스크 세트로 구성되며 고정된 타워 세트에 크기가 증가하는 순서로 배치된다.$k{\displaystyle }$ ${\displaystyle k}$타워에$$ $n{\displaystyle }$ ${\displaystyle$ n$}디스크$가 있는 퍼즐에 대한 하노이 그래프는 ${\displaystyle {}_{}^{}}$ n ${\$^[1][2] 퍼즐의 각 상태는 디스크당 하나의 타워 선택에 의해 결정되므로 그래프에는 ${\displaystyle {kn}^{}}$ ${\$ k$^{n}$ 정점이$$ 있다.^[2]

퍼즐의 움직임에서, 한 탑의 가장 작은 원반은 비어있는 탑이나 가장 작은 원반이 더 큰 탑으로 옮겨진다.$u{\displaystyle }$ ${\displaystyle u}$개의$$ 비어 있는 타워가 있는 경우 허용 가능한 이동 수는

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

which ranges from a maximum of ${\displaystyle {\tbinom {k}{2}}}$ (when ${\displaystyle u}$ is zero or one and ${\displaystyle {\tbinom {u}{2}}}$ is zero) to ${\displaystyle k-1}$ (when all disks are on one tower and ${\displaystyle u}$ is ${\displaystyle k-1$$}}$ 따라서 하노이 그래프에서 정점의 정도는 최대 $({\displaystyle k\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{2}{}}$) ${\$부터 최소 ${\displaystyle \mathrm{k}}$- 1 ${\displaystyle k-1}$까지 다양하다$.$ 총 에지 수는 다음과^[3] 같다.

${\displaystyle {\frac {1}{1}:{2}}: {\binom {k}{2}}: {\bigl (}k^{n}-(k-2)^{n}{\bigr )}.}$

$k{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle k=0}($디스크 없음)의 경우 퍼즐의 상태는 하나, 그래프의 꼭지점은 하나만 있다.> ${\displaystyle k>0$의 경우, 하노이 그래프 ${\displaystyle {}_{}^{}}$ n ${\$$}}}$은(는) 가장 큰 디스크의 각 배치마다 하나씩 작은 하노이 그래프 $H{\displaystyle {}_{}^{}}$ k -${\displaystyle 1_{}^{}}$의 $k{\displaystyle }$ ${\$ 복사본으로$$ 분해할 수 있다$$.이 복사본들은 가장 큰 디스크가 자유롭게 이동할 수 있는 주에서만 서로 연결된다: 그것은 그것의 탑에 있는 유일한 디스크고, 몇몇 다른 타워는 비어있다.^[4]

일반 속성

모든 하노이 그래프에는 해밀턴 사이클이 포함되어 있다.^[5]

하노이 그래프 $H{\displaystyle {}_{}^{}}$ ${\displaystyle k_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$1}는$$k {\$displaystyle$ k$} 정점$에 대한 완전한$$ 그래프다.완전한 그래프를 포함하기 때문에 모든 대형 하노이 그래프 ${\displaystyle {}_{}^{}}$ n ${\$은(는) 그래프 색상에 적어도 $k{\displaystyle }$ ${\displaysty$ k$} 색상$이 필요하다$$$$.각 디스크가 포함된 타워의 인덱스를 합산하고, 색상으로$$ 합계 모듈로 $k{\displaystyle }$ ${\displaystyle k}$을(를) 사용하여 정확히 $k{\displaystyle }$ ${\displaystyle$ k$}$ 색상으로$$ 색칠할 수 있다.^[3]

삼탑

득점왕, 그룬디앤스미스(1944)^[1][6]의 작품 이후 잘 연구된 하노이 그래프의 특별한 사례는 3층 하노이 그래프의 경우, $H{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$n$\}\}\}\}\}$이러한 그래프 3n vertices과.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-outp(OEIS:A000244)다.다고.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-onlyᆬ3(3n − 1)/2 가장자리(OEIS:A029858).[7]그것들은 시에르핀스키 삼각형과 유사한 디스크 배열을 가진 페니 그래프(비행기 내 비 겹치지 않는 유닛 디스크의 접촉 그래프)이다.이 배열을 구성하는 한 가지 방법은 파스칼의 삼각형 숫자를 6각형 격자 점 위에 단위 간격을 두고 배열하고, 숫자가 홀수인 각 점에 단위 디스크를 배치하는 것이다.이 그래프의 직경과 하노이 탑 퍼즐의 표준형식에 대한 솔루션 길이(디스크는 모두 하나의 타워에서 시작되어 하나의 타워로 이동해야 함)는 2n-1{2^{n\displaystyle}-1}이다.[2]

타워 3개 이상

> ${\displaystyle k>3}$의 경우 하노이 그래프의 구조가 잘 이해되지 않으며, 이러한 그래프의 직경은 알 수 없다.^[2]> ${\displaystyle k>4}$과 > 0 ${\displaystyle n>0}$일 때${\displaystyle }또는{\displaystyle }$ ${\displaystyle \mathrm{k}}$ =$$4 {\$displaystyle k=$4$$}과n >2 {\$displaysty n>2}$일 때 이러한 그래프는 평면이 아니다^[5]

참고 항목

• 시에르핀스키 삼각형

참조