Ханой график

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

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

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

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

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

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

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

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

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

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

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

Три башни

Частный случай ханойских графов, хорошо изученный со времен работы Скорера, Гранди и Смита (1944). ^[1]^[6] это случай ханойских графов с тремя башнями, $H_{3}^{n}$ . Эти графики имеют $3 н$ вершины ( OEIS : A000244 ) и $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 3(3 н − 1) / 2 ⁠$ ребра ( OEIS : A029858 ). ^[7]Это пенни-графы ( графы контактов непересекающихся единичных дисков на плоскости) с расположением дисков, напоминающим треугольник Серпинского . Один из способов построения такого расположения — расположить числа треугольника Паскаля в точках шестиугольной решетки с единичным интервалом и поместить единичный круг в каждую точку, номер которой нечетен.Диаметр равны этих графов и длина решения стандартной формы головоломки Ханойской башни (в которой все диски начинаются с одной башни и все должны переместиться на другую башню) $2^{n}-1$ . ^[2]

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

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

Какой диаметр графов

H_{k}^{n}

для

k>3

?

(еще нерешенные задачи по математике)

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

См. также

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

Ссылки

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

[hkp-1] Jump up to: Перейти обратно: ^а ^б Хинц, Андреас М.; Клавжар, Санди ; Петр, Сирил (2018), «2.3 Ханойские графики», Ханойская башня - мифы и математика (2-е изд.), Cham: Birkhäuser, стр. 120, номер домена : 10.1007/978-3-319-73779-9 , ISBN. 978-3-319-73778-2 , МР 3791459

[ikr-2] Jump up to: Перейти обратно: ^а ^б ^с ^д Имрих, Вильфрид ; Клавжар, Санди ; Ралл, Дуглас Ф. (2008), «2.2 Ханойские графы», Темы теории графов: графы и их декартово произведение , Уэлсли, Массачусетс: AK Peters, стр. 13–15, ISBN 978-1-56881-429-2 , МР 2468851

[ad-3] Jump up to: Перейти обратно: ^а ^б Аретт, Даниэль; Доре, Сюзанна (2010), «Раскраска и подсчет графиков Ханойской башни», Mathematics Magazine , 83 (3): 200–209, doi : 10.4169/002557010X494841 , MR 2668333 , S2CID 120868360

[afm-4] Стюарт, Ян (2003), «Глава 1: Лев, лама и салат», Еще одна прекрасная математика, в которую вы меня втянули , Минеола, Нью-Йорк: Dover Publications, ISBN 0-486-43181-9 , МР 2046372

[hp-5] Jump up to: Перейти обратно: ^а ^б Хинц, Андреас М.; Парисс, Даниэле (2002), «О планарности ханойских графов», Expositiones Mathematicae , 20 (3): 263–268, doi : 10.1016/S0723-0869(02)80023-8 , MR 1924112

[sgs-6] бомбардир, РС; Гранди, ПМ ; Смит, CAB (июль 1944 г.), «Некоторые бинарные игры», The Mathematical Gazette , 28 (280): 96, doi : 10.2307/3606393 , JSTOR 3606393 , S2CID 125099183

[7] «Ханойский график» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]