ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классиче. - презентация

1 ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классиче ­ ская задача коммивояжера. Формулировка задачи. Коммивояжер должен совершить поездку по городам и вер­нуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму.

2 ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Взвешенный граф – граф, каждому ребру которого поставлено в соответствие некоторое числовое значение, называемое весом ребра. Элементами матрицы смежности взвешенного графа являются весовые значения ребер ( дуг ) графа.

3 ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра – связывающие их дороги. Кроме того, каждое ребро оснащено ве ­ сом, обозначающим транспортные затраты, необходимые для передвижения по соответствующей дороге, такие, как, например, рассто ­ яние между городами или время движения по дороге. Для решения задачи необходимо найти гамильтонов цикл минимального общего веса.

4 ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Методы решения задачи коммивояжера : метод ветвей и границ ( алгоритм Литтла ); алгоритм « ближайшего соседа » (« жадный алгоритм »); метод нахождения минимального остовного дерева (« деревянный алгоритм »); алгоритм Дейкстры.

5 ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Алгоритм « ближайшего соседа » относится к алгоритмам поиска субопти ­ мального решения. Субоптимальное решение необязательно даст цикл минимального o бщег o веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамиль ­ тоновых циклов.

6 ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Формулировка алгоритма. Пункты ( вершины ) обхода графа последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута

7 ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Пример. Применим алгоритм ближайшего соседа к графу, изо ­ браженному на рис За исходную вершину возьмем вершину D. Рисунок 15 А В СD

8 ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Решение. Вершины Маршрут Длина маршрута DD0 CDC3 ADCA9 BDCAB14 DDCABD24

9 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Существует класс графов, называемых деревьями. Дерево – связный граф, не содержащий циклов ( ацикличный граф ). Пусть G = ( V, Е ) – граф с n вершинами и m ребрами. Мож ­ но сформулировать несколько необходимых и достаточных условий, при которых G является деревом : любая пара вершин в G соединена единственным путем ; G связен и m = n- 1; G связен, а удаление хотя бы одного его ребра нарушает связность графа ; G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.

10 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ В любом связном графе найдется под ­ граф, являющийся деревом. Подграф в G, являющийся деревом и включающий в себя все вершины G, называется остовным деревом.

11 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Остовное дерево в графе G строится просто : выбираем произволь ­ ное его ребро и последовательно добавляем другие ребра, не созда ­ вая при этом циклов, до тех пор, пока нельзя будет добавить ника ­ кого ребра, не получив при этом цикла. Для построения остовного дерева в графе из n вершин необходимо выбрать ровно n - 1 ребро.

12 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Все остовные деревья графа ( рис. 16 ), представлены на рисунке 17. Рисунок 16

13 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Рисунок 17

14 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Нахождение минимального остовного дерева ( minimal spanning tree – MST ). В графе G=(V, E) рассмотрим U – некоторое подмножество V, такое что U і V-U не пусты. Пусть ( u, v ) – ребро наименьшей стоимости, одна вершина которого – u принадлежит U, а другая – v принадлежит V-U. Тогда существует некоторое MST, которое содержит ребро ( u, v ).

15 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ На этом свойстве основан алгоритм Прима. Начинаем с пустого U=0. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U. Перебрав все вершины, находим минимальный остов.

16 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Найдем минимальный остов графа ( рис. 18 ). Рисунок 18

17 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ U={0}, V-U={A,B,C,D,E}. Начнем с вершины В: U={B}, V-U={ A,C,D,E }. Выбираем ребро с наименьшим весом – это ребро ВА (вес – 1): U={B,A}, V-U={ C,D,E }. Теперь выбираем ребро с наименьшим весом к оставшимся вершинам, т. е. из V-U ={ C,D,E }. Если вес ребер одинаковый – выбираем любое, например ребро ВС ( вес ребра – 3): U={B,A,C}, V-U={ D,E }.

18 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Опять выбираем ребро с наименьшим весом к оставшимся вершинам, т. е. из V-U ={ D,E }, например, ребро СЕ ( вес ребра – 2): U={B,A,C, Е }, V-U={ D }. Остается ребро ED: U={B,A,C, Е,D}, V-U={ 0 }.

19 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ По предложенной взвешенной матрице смежности восстановить граф и найти его все возможные минимальные остовные деревья. abcde a04025 b40300 c03000 d20007 e50070

20 ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ