Путь минимальной стоимости обхода графа

1.

Путь минимальной
стоимости обхода
графа
z
Выполнил: студент группы 381903_4
Бычков Денис Александрович
Руководитель: Кандидат физикоматематических наук кафедры теоретической,
компьютерной и экспериментальной механики,
доцент Сабаева Татьяна Анатольевна.

2.

z
Постановка задачи.
Дан неполный взвешенный неориентированный
граф G = (V,E) и вершина v.
Необходимо найти минимальный путь,
исходящий из вершины v, который будет
включать все оставшиеся вершины графа G
ровно 1 раз и заканчиваться v.

3.

z
Компонента связности.
Взвешенный граф
Степень вершины
Перестановки
Необходимая теория

4.

z
Представление графа
Матрица смежности

5.

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

6.

z
Обход в глубину

7.

z
2 этап. Перестановки.
Алгоритм Нарайаны.
1.Найти максимальный индекс i для которого Ai < Аi+1
2. Найти максимальный индекс j для которого Aj > Ai.
3. Выполнить обмен Ai и Aj.
4. Записать последовательность Ai+1, …, An в обратном
порядке.

8.

z
Алгоритм Хипа
1. Вызвать функцию, передав значение k = числу элементов
2. Проверить k, если k ==1, использовать последовательность как
текущую перестановку. Закончить вызов функции.
3. Используя цикл от индекса первого элемента последовательности до
n:
a) Рекурсивно вызвать функцию, передав последовательность и
значение k-1.
б) Если k – четное, выполнить обмен i и k элемента местами, иначе
выполнить обмен первого и k элемента последовательности

9.

z
3 этап. Вычисление путей

10.

z
Тесты.

11.

z
Спасибо за Внимание!