Page 86 - 2589

трикутника, зображено на рис.4.7,а, хоча внутрішні зв'язки в нім
нам ще невідомі. Який при цьому буде граф для m + 1 дисків?

Рисунок 4.7 - Перехід від m-графа до (m+1)-графу

Помітимо, що диск з номером m +1може займати на будь-

якому з кілочків тільки нижнє положення. При цьому інші m
дисків можуть переміщатися як завгодно відповідно до m -
графом без зміни положення (m+1)-го диска. Отже, граф для

(m+1) - дисків (рис.4.7,б) складатиметься з трьох m - графів,
позначених цифрами (у кружечках) 1, 2 і 3, що означають номер
кілочка, на якому знаходиться (m +1)--й диск. Залишається

з'ясувати тільки переходи від одного m- графа до іншого, що
відповідають переміщенню (m +1)-го диску.
Диск (m +1)- може бути перекладений тільки на вільний

кілочок, а це можливо лише у тому випадку, коли на одному з
кілків розташовані усі m менших дисків. Відповідно до цього на
рис.4.7,б показані можливі переходи (m +1)-го диска, позначені
цифрами 1, 2 і 3, означають номер кілочка, на якому знаходиться

m менших дисків.
Діаграма, показана на рис.4.7,б, дає загальний принцип
переходу від m - графа до (m +1) -графу. На рис.4.6,б приведені

графи переходів для двох і трьох дисків.
Перейдемо до завдання знаходження в графі найкоротшого
шляху, що сполучає початкову вершину з кінцевою. Оскільки
розглянуті графи порівняно прості, то найкоротший шлях

неважко знайти просто шляхом перебору можливих шляхів.

86