WikiDer > Ханойский график - Википедия

Hanoi graph - Wikipedia
Ханойский граф

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

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

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

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

который колеблется от максимума (когда равно нулю или единице и равно нулю) до (когда все диски на одной башне и является ). Следовательно градусы вершин в графике Ханоя варьируются от максимального как минимум . Общее количество ребер составляет[3]

За (без дисков) есть только одно состояние головоломки и одна вершина графа. , Ханойский граф можно разложить на копии меньшего графа Ханоя , по одному на каждое размещение самого большого диска. Эти копии соединяются друг с другом только в состояниях, когда самый большой диск может свободно перемещаться: это единственный диск в своей башне, а какая-то другая башня не занята.[4]

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

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

Ханойский граф это полный график на вершины. Поскольку они содержат полные графы, все более крупные графы Ханоя требуется по крайней мере цвета в любых раскраска графика. Они могут быть окрашены точно цветов, суммируя индексы башен, содержащих каждый диск, и используя сумму по модулю как цвет.[3]

Три башни

Частный случай ханойских графов, хорошо изученный со времен работ Скорее всего, Гранди и Смит (1944)[1][6] случай трехбашенных ханойских графов, . Эти графики имеют 3п вершины.Они есть графы пенниграфики контактов неперекрывающихся дисков агрегата в плоскости), с расположением дисков, напоминающим Треугольник Серпинского. Один из способов построения этого расположения - расположить количество Треугольник Паскаля по пунктам шестиугольная решеткас единичным интервалом и поместите единичный диск в каждую точку с нечетным номером. диаметр этих графиков, а длина решения стандартной формы загадки Ханойской башни (в которой все диски начинаются с одной башни и все должны перемещаться в другую башню) равна .[2]

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Какой диаметр у графиков за ?
(больше нерешенных задач по математике)

За структура ханойских графов изучена не так хорошо, и диаметр этих графов неизвестен.[2]Когда и или когда и , эти графы неплоские.[5]

Рекомендации

  1. ^ а б Hinz, Andreas M .; Клавжар, Санди; Петр, Цирил (2018), "2.3 Ханойские графики", Ханойская башня - мифы и математика (2-е изд.), Cham: Birkhäuser, p. 120, Дои:10.1007/978-3-319-73779-9, ISBN 978-3-319-73778-2, МИСТЕР 3791459
  2. ^ а б c d Имрих, Вильфрид; Клавжар, Санди; Ралл, Дуглас Ф. (2008), «2.2 Ханойские графики», Разделы теории графов: графы и их декартово произведение, Уэллсли, Массачусетс: А. К. Питерс, стр. 13–15, ISBN 978-1-56881-429-2, МИСТЕР 2468851
  3. ^ а б Аретт, Даниэль; Дори, Сюзанна (2010), «Раскраска и подсчет графиков Ханойской башни», Математический журнал, 83 (3): 200–209, Дои:10.4169 / 002557010X494841, МИСТЕР 2668333
  4. ^ Стюарт, Ян (2003), «Глава 1: Лев, лама и салат», Еще одна точная математика, в которую вы меня втянули, Mineola, NY: Dover Publications, ISBN 0-486-43181-9, МИСТЕР 2046372
  5. ^ а б Hinz, Andreas M .; Парисс, Даниэле (2002), "О планарности графиков Ханоя", Expositiones Mathematicae, 20 (3): 263–268, Дои:10.1016 / S0723-0869 (02) 80023-8, МИСТЕР 1924112
  6. ^ Scorer, R. S .; Гранди, П.М.; Смит, К.А.Б. (Июль 1944 г.), «Некоторые бинарные игры», Математический вестник, 28 (280): 96, Дои:10.2307/3606393