Файл: А.В. Бирюков Дискретная математика.pdf

Ниже приведена рабочая вспомогательная таблица.

Начало пути Х1 назовем активной вершиной с постоянной мет-

кой 0. Расстояние от Х1 до смежных вершин Х2 и Х3 имеют временные метки 7 и 2, а расстояния до остальных вершин помечены симво-

9

лом ∞. Из двух временных меток 7 и 2 выбираем меньшую и при-

сваиваем ей постоянную метку 2 (вторая строка таблицы). При этом активной вершиной становится Х3.

Расстояния от Х1 до вершин Х2, Х4, Х5, смежных с Х3 , равны 5, 8, 5 (третья строка таблицы). Выбираем их них первое наименьшее и

присваиваем ему постоянную метку 5. При этом активной становится вершина Х2 и т. д.

Процесс поиска кратчайшего пути заканчивается на ак-

тивной вершине Х7, когда постоянная метка присваивается вершине Х8. Сам путь восстанавливается обратным ходом: Х8 , Х6 , Х4 , Х3 , Х1 .

3) Задача коммивояжера

Пусть имеется полный взвешенный граф Кn. Требуется найти гамильтонов цикл наименьшего веса. Если вес ребра отождествляется с его длиной, то эта задача интерпретируется как поиск кратчайшего простого цикла, содержащего все вершины графа.

У полного неориентированного графа с n вершинами число гамильтоновых циклов равно (n -1)!/2. На рис. 12 изображен полный

взвешенный граф К4 , имеющий 3! / 2 = 3 гамильтоновых цикла: 1, 2, 3, 4, 1; 1, 2, 4, 3, 1; 1, 3, 2, 4, 1.

Рис. 12

Длины или веса этих циклов равны соответственно 11, 14, 17. Следовательно, решением задачи является цикл 1, 2, 3, 4, 1.

10