Ханойский график

Схема состояний и ходов в головоломке «Ханойская башня»

Ханойский график ${\displaystyle H_{3}^{7}}$

В теории графов и занимательной математике ханойские графы — это неориентированные графы , вершины которых представляют возможные состояния головоломки «Ханойская башня» , а ребра — допустимые перемещения между парами состояний.

Строительство

Граф Ханоя (черные круги), полученный из нечетных значений в треугольнике Паскаля. ${\displaystyle H_{3}^{5}}$

Головоломка состоит из набора дисков разных размеров, размещенных в порядке возрастания размера на фиксированном наборе башен. Граф Ханоя для головоломки с дисками на башнях обозначается . ^{[1] [2]} Каждое состояние головоломки определяется выбором одной башни для каждого диска, поэтому граф имеет вершины. ^[2] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle H_{k}^{n}}$ ${\displaystyle k^{n}}$

В ходах головоломки наименьший диск на одной башне перемещается либо на незанятую башню, либо на башню, наименьший диск которой больше. Если есть незанятые башни, то число допустимых ходов равно ${\displaystyle u}$

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

который варьируется от максимума (когда равен нулю или единице и равен нулю) до (когда все диски находятся на одной башне и равен ). Таким образом, степени вершин в графе Ханоя варьируются от максимума до минимума . Общее количество ребер равно ^[3] ${\displaystyle {\tbinom {k}{2}}}$ ${\displaystyle u}$ ${\displaystyle {\tbinom {u}{2}}}$ ${\displaystyle k-1}$ ${\displaystyle u}$ ${\displaystyle k-1}$ ${\displaystyle {\tbinom {k}{2}}}$ ${\displaystyle k-1}$

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

Для (без дисков) есть только одно состояние головоломки и одна вершина графа. Для граф Ханой можно разложить на копии меньшего графа Ханой , по одной для каждого размещения наибольшего диска. Эти копии соединены друг с другом только в состояниях, где наибольший диск свободен для перемещения: это единственный диск в своей башне, а какая-то другая башня не занята. ^[4] ${\displaystyle k=0}$ ${\displaystyle k>0}$ ${\displaystyle H_{k}^{n}}$ ${\displaystyle k}$ ${\displaystyle H_{k}^{n-1}}$

Общие свойства

${\displaystyle H_{3}^{3}}$с 12 удаленными ребрами, чтобы получить гамильтонов цикл

Каждый граф Ханоя содержит гамильтонов цикл . ^[5]

Граф Ханоя — это полный граф на вершинах. Поскольку они содержат полные графы, все большие графы Ханоя требуют по крайней мере цветов в любой раскраске графа . Они могут быть раскрашены ровно цветами, суммируя индексы башен, содержащих каждый диск, и используя сумму по модулю в качестве цвета. ^[3] ${\displaystyle H_{k}^{1}}$ ${\displaystyle k}$ ${\displaystyle H_{k}^{n}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Три башни

Частным случаем графов Ханоя, который был хорошо изучен со времен работы Скорера, Гранди и Смита (1944) ^{[1] [6],} является случай трехбашенных графов Ханоя, . Эти графы имеют 3 n вершин ( OEIS : A000244 ) и ⁠ ${\displaystyle H_{3}^{n}}$ 3(3n ⁻ 1)/2⁠ ребра ( OEIS : A029858 ). ^[7] Это графы пенни ( графы контактов неперекрывающихся единичных дисков на плоскости) с расположением дисков, напоминающим треугольник Серпинского . Один из способов построения этого расположения — расположить числа треугольника Паскаля в точках гексагональной решетки с единичным интервалом и поместить единичный диск в каждую точку, номер которой нечетен. Диаметр этих графов и длина решения стандартной формы головоломки «Ханойская башня» (в которой все диски начинаются на одной башне и должны все переместиться на одну другую башню) равны. ^[2] ${\displaystyle 2^{n}-1}$

Более трех башен

Нерешенная задача по математике :

Каков диаметр графиков ? ${\displaystyle H_{k}^{n}}$ ${\displaystyle k>3}$

(еще нерешенные проблемы по математике)

Для структура графов Ханоя не так хорошо изучена, а диаметр этих графов неизвестен. ^[2] Когда и или когда и , эти графы непланарны. ^[5] ${\displaystyle k>3}$ ${\displaystyle k>4}$ ${\displaystyle n>0}$ ${\displaystyle k=4}$ ${\displaystyle n>2}$

Смотрите также

• треугольник Серпинского

Ссылки

1. Hinz, Andreas M.; Klavžar, Sandi ; Petr, Ciril (2018), "2.3 Ханойские графики", Ханойская башня — мифы и математика (2-е изд.), Cham: Birkhäuser, стр. 120, doi : 10.1007/978-3-319-73779-9, ISBN 978-3-319-73778-2, г-н  3791459
2. Имрих, Вильфрид ; Клавжар, Сэнди ; Ралл, Дуглас Ф. (2008), "2.2 Ханойские графы", Темы в теории графов: Графы и их декартово произведение , Уэллсли, Массачусетс: AK Peters, стр. 13–15, ISBN 978-1-56881-429-2, г-н  2468851
3. Аретт, Даниэль; Доре, Сюзанна (2010), «Раскраска и подсчет на графах Ханойской башни», Mathematics Magazine , 83 (3): 200–209, doi :10.4169/002557010X494841, MR  2668333, S2CID  120868360
4. Стюарт, Ян (2003), «Глава 1: Лев, лама и салат», Another Fine Math You've Got Me Into , Минеола, Нью-Йорк: Dover Publications, ISBN 0-486-43181-9, МР  2046372
5. Хинц, Андреас М.; Парисс, Даниэле (2002), «О планарности ханойских графов», Expositiones Mathematicae , 20 (3): 263–268, doi : 10.1016/S0723-0869(02)80023-8 , MR  1924112
6. Скорер, RS; Гранди, PM ; Смит, CAB (июль 1944 г.), «Некоторые бинарные игры», The Mathematical Gazette , 28 (280): 96, doi :10.2307/3606393, JSTOR  3606393, S2CID  125099183
7. «Граф Ханоя».