Page 84 - 2589

багато завдань вибору найбільш економічного способу перекладу
динамічної системи з одного стану в інше і т. п. В математиці
розроблений ряд методів для розвязку подібних завдань. Проте

дуже часто методи, засновані на використанні графів,
виявляються найменш трудомісткими.

Завдання про найкоротший шлях на графі в загальному
вигляді може бути сформульоване таким чином. Даний
неорієнтований граф G  (V ,E ).Кожному ребру цього графа

приписано деяке число (el )  0, яке називається довжиною

ребра. У окремих випадках (el ) може бути відстанню між
вершинами, що сполучаються ребром e, часом або вартістю
проїзду по цьому ребру і т. п. При цьому будь-який ланцюг 

характеризуватиметься довжиною

l( )   l( e).
e  
Потрібно для двох довільних вершин a і b графа G знайти

шлях  , причому такий, щоб його повна довжина була
ab
найменшою.

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

5.7.2 Знаходження найкоротшого шляху в графі з

ребрами однакової довжини

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

з деякої точки зору усі переходи, що робляться за один крок,
еквівалентні. Наведемо приклад завдання, яке зводиться до
розгляду графа з ребрами одиничної довжини. Це завдання може
служити ілюстрацією способів побудови графів для різних

конкретних випадків.

Приклад 4.5: Завдання про ханойську вежу. Цю задачу

придумав французький математик Едуард Лука у 1883 році.
Дошка має три стержні. На перший нанизані m дисків, діаметр
яких спадає від низу до верху. Постановка задачі: перекладаючи
диски по одному, розмістити їх в тому ж порядку на третьому

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

84