Граф головоломки с p подставками

Графом называется пара множеств (V(G),E(G)), где V(G) – произвольное множество вершин и E(G) – множество пар вершин, ребер графа. На одном и том же множестве вершин можно построить разные графы, например, набору вершин {A,B,C} можно сопоставить пары {AB,BC} или {AB,BC,AC}.

В случае с задачей о ханойской башне мы можем за вершины графа принять все допустимые расположения дисков на подставках. Ребра будут соединять только те положения, которые можно получить одно из другого ровно за одно перекладывание. Обозначим первую подставку буквой A, вторую – B, третью – C. Количество колечек в головоломке обуславливает число символов в названии вершины. Так, например, вершина AACB обозначает положение четырех колечек в головоломке, два самых больших кольца лежат на подставке A, третье по величине кольцо лежит на подставке C, и самое маленькое на подставке B.

image001.png

Граф соответствующий головоломке с p подставками и n колечками будем обозначать Gpn. Попытаемся понять, как устроены графы для классического случая трех подставок. Если в головоломке одно колечко, то ее положение описывается простым набором вершин V(G31)={A,B,C}. Любое положение получается за один ход из предыдущего, поэтому E(G31)={AB,BC,CA}. 

image009.png

Для n=2 количество вершин уже будет равно 32=9, вершины графа удобно расположить как на рисунке

image016.png

Для n=3 граф представлен на рисунке 

image019.png

Зафиксируем некоторое значение i. Ребра графа можно подразделить на две категории. Это ребра, соединяющие вершины, имена которых отличаются лишь последними i символами, такие ребра мы назовем локальными, и все остальные ребра – мосты, устанавливающие связь между подграфами, с локальными ребрами. Так для i=1 локальными ребрами будут только те, которые соответствуют перекладыванию самого маленького колечка. А вот при i=2 к списку локальных ребер добавятся некоторые ребра, ранее именовавшиеся мостами и так далее.

image022.png

Поиск оптимального алгоритма перекладывания колечек - это поиск кратчайшего пути в графе, соединяющего вершину AA…A с вершиной CC…C. Очевидно, что в графе G3n это просто сторона получившегося треугольника. Количество вершин на одной стороне равно 2n, а количество ребер соответственно 2n-1.

С увеличением числа подставок граф головоломки усложняется и уже не имеет такой понятной структуры. Давайте попробуем понять, как будет выглядеть граф для четырех подставок. Алфавит из которого мы берем символы для имен вершин графа теперь будет содержать 4 разные буквы {A,B,C,D}. Граф G41 будет тетраэдром

image033.png

Для того, чтобы получить граф G42 создаем четыре копии графа G41. Добавляем в именах вершин первой копии символ A, в именах второй – символ B, третьей – символ C, четвертой – D и достраиваем мосты

image038.png

Аналогично строится G43 и т.д.

image044.png

Про такой граф можно сказать, что он имеет самоподобную структуру. Если мы зафиксируем i, а затем склеим все вершины, соединенные локальными ребрами в одну, то мы получим граф G4n-1.

Пусть число подставок в головоломке произвольно и равно p. Если число дисков равно n, то алфавит для имен графа состоит из p символов, а имена вершин имеют длину n. Будем использовать сокращенную запись имен. Если имя содержит цепочку повторяющихся символов, будем ее сворачивать, так, например

 image050.png  или image053.png

Перекладывание дисков алгоритмом Фрейма-Стюарта дает пути в графе, соединяющие вершины An1 и Anp и проходящие через вершину An-q1Aq2 для некоторого q и k≠1, p. По этой причине будем называть вершины вида An1 до 

An-q1Aq2 состоит только из локальных ребер, вторая – только из мостов от An-q1Aq2 до An-qpAq2, а третья повторяет по форме первую траекторию и также состоит из локальных ребер. 

Анализируя граф можно убедиться, что любой кратчайший путь P от An1 до Anp, проходящий через некоторую особую вершину может быть заменен на путь Q такой же длины, состоящий из трех путей Q1, Q2 и Q3, таких, что Q1, Q3 состоят из локальных ребер, а Q2 из мостов.

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

image078.png

данный путь реализуется перекладываниями по алгоритму Фрейма-Стюарта. Единственное что нужно обосновать для завершения доказательства оптимальности алгоритма Фрейма-Стюарта это то, что любой искомый кратчайший  проходит через какую-нибудь специальную вершину. Для p=4 это удалось [7], а для p>4 пока нет.

Читать дальше


[7] Žerovnik, J. Self Similarities of the Tower of Hanoi Graphs and a proof of the Frame-Stewart Conjecture//J. Žerovnik/ The Amer. Math. Mon. 121:1, 2016.