Теория графов. Задача коммивояжера презентация

Основой всех таких задач служит классиче­ская задача коммивояжера.
Формулировка задачи. Коммивояжер должен совершить поездку по городам и вер­нуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму.

в соответствие некоторое числовое значение, называемое весом ребра. Элементами матрицы смежности взвешенного графа являются весовые значения ребер (дуг) графа.

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

Литтла);
алгоритм «ближайшего соседа» («жадный алгоритм»);
метод нахождения минимального остовного дерева («деревянный алгоритм»);
алгоритм Дейкстры.

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

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

на рис. 15. За исходную вершину возьмем вершину D.




Рисунок 15

А

В

С

D

6

8

5

3

7

10

содержащий циклов (ацикличный граф).
Пусть G = (V, Е) – граф с n вершинами и m ребрами. Мож­но сформулировать несколько необходимых и достаточных условий, при которых G является деревом:
• любая пара вершин в G соединена единственным путем;
• G связен и m = n-1;
• G связен, а удаление хотя бы одного его ребра нарушает связность графа;
• G ацикличен, но если добавить хотя бы одно ребро, то в G
появится цикл.

G, являющийся деревом и включающий в себя все вершины G, называется остовным деревом.

ребро и последовательно добавляем другие ребра, не созда­вая при этом циклов, до тех пор, пока нельзя будет добавить ника­кого ребра, не получив при этом цикла.
Для построения остовного дерева в графе из n вершин необходимо выбрать ровно n - 1 ребро.

16

G=(V, E) рассмотрим U – некоторое подмножество V, такое что U і V-U не пусты. Пусть (u, v) – ребро наименьшей стоимости, одна вершина которого – u принадлежит U, а другая – v принадлежит V-U. Тогда существует некоторое MST, которое содержит ребро (u, v).

к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U. Перебрав все вершины, находим минимальный остов.

весом – это ребро ВА (вес – 1): U={B,A}, V-U={C,D,E}.
Теперь выбираем ребро с наименьшим весом к оставшимся вершинам, т.е. из V-U ={C,D,E}.
Если вес ребер одинаковый – выбираем любое, например ребро ВС (вес ребра – 3): U={B,A,C}, V-U={D,E}.

из V-U ={D,E}, например, ребро СЕ (вес ребра – 2): U={B,A,C,Е}, V-U={D}. Остается ребро ED: U={B,A,C,Е,D}, V-U={0}.

его все возможные минимальные остовные деревья.