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

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

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

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

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

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

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

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

ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Решение.

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

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

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

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

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

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

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

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

ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ 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}.

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

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

ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Задача. Являются ли графы, задаваемые следующими ма­трицами смежности, деревьями?