ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.06.2021

Просмотров: 220

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Лекция 7

Нахождение кратчайших путей

1 Эйлеров граф

2 Гамильтонов граф

3. Деревья, леса

4. Построение минимального остовного дерева

Алгоритм Краскала

Алгоритм Прима



Постановка задачи

Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна?

В общем случае, задачу можно сформулировать так. Пусть дан связный неориентированный граф G(V;E), и каждой его дуге  е  сопоставлено некоторое число w(j), называемое весом или длиной этой дуги. Сумму весов дуг дерева в дальнейшем будем называть весом дерева или его множества дуг. Требуется найти такое основное дерево Т, содержащего все вершины графа G, у которого вес был бы минимален.

Такое дерево будет называться минимальным остовным деревом.

Рис. 1. Минимальное остовное дерево. Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.

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

Рис.2-а. Минимальное остовное дерево.
Суммарный вес равен 3.

Рис.2-б. Минимальный покрывающий подграф.
Суммарный вес равен 0.

Также считаем, что для любой пары ребер их весовые характеристики будут различны. Это гарантирует уникальность построенного минимального остовного дерева. Для примера, если все ребра имеют единичный вес, то любое остовное дерево будет минимальным (с суммарным весом v-1, где v – количество вершин в графе).

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

Области применения

  • Разработка сетей. Ранее был приведен пример о соединении n городов в единую телефонную сеть с минимальной суммарной стоимостью соединений.

  • Производство печатных плат. По аналогии с сетью: мы хотим соединить n контактов проводами с минимальной суммарной стоимостью. (Здесь стоит отметить, что задача о минимальном остовном дереве является упрощением реальности. В самом деле, если соединяемые контакты находятся в вершинах единичного квадрата, разрешается соединять любые его вершины, и вес соединения равен его длине, то минимальное покрывающее дерево будет состоять из трех сторон квадрата. Между тем все его четыре вершины можно электрически соединить двумя пересекающимися диагоналями, суммарная длина которых будет равна 2√2, что меньше 3 в первом случае).

  • Минимальное остовное дерево может использоваться для визуализации многоаспектных, многомерных данных, например, для отображения их взаимосвязи (на картинке ниже продемонстрировано дерево схожести различных животных видов по размеру костей).



Рис.4. Минимальное остовное дерево может нагляднее представить эволюцию животных видов.
С помощью него можно разбивать животных на группы и классы.

  • Наука, и в частности биология, используют многомерные данные для группировки объектов, растений, животных. Минимальное остовное дерево позволяет разбивать их на взаимосвязанные классы, четко отслеживая близкие по строению и характеристикам группы.



Построение минимального остовного дерева

Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева. Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u,v) выбирается так, чтобы не нарушить этого свойства: A {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро на шаге 3. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A – одна компонента). Таким образом цикл выполняется (n-1) раз.

Лемма: пусть Т – минимальное остовное дерево. Тогда любое ребро е из T – безопасное. 


Теорема: Пусть G(V;E) – связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А – некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда ребро минимального веса из E(K) будет безопасным. 


Определение. Безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.

Алгоритм Краскала

А лгоритм был предложен Джозефом Краскалом в 1957 г.

Алгоритм состоит из двух фаз. На подготовительной фазе все дуги удаляются из дерева и упорядочиваются по возрастанию их весов. В графе остаются только вершины, каждая из которых образует отдельную компоненту связности.

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


На рисунках К1-К8 представлена работа алгоритма.



Рис. К1. Начальная фаза. Минимальный покрывающий лес пуст.



Рис. К2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А.



Рис. К3. Следующее безопасное ребро с весом 6. Добавляем его.



Рис. К4.



Рис. К5.



Рис. К6.



Рис. К7.



Рис. К8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Теорема. Остовное дерево, которое строится описанным алгоритмом, имеет минимальный вес.

Алгоритм Прима-Ярника













Этот алгоритм обычно называется алгоритмом Прима, так как он стал широко известен по статье Роберта Прима, опубликованной в 1956 г. (левое фото). Впоследствии стало известно, что в 1930 г. этот алгоритм был открыт чешским математиком Войтехом Ярником (1897-1970) (правое фото), основные научные интересы которого были в области теории чисел.

Предложенный ими алгоритм очень прост:

Как и алгоритм Крускала, алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро. Алгоритм Прима относится к группе алгоритмов наращивания минимального остова: на каждом шаге существует не более одной нетривиальной (не состоящей из одной вершины) компоненты связности, и каждый к ней добавляется ребро наименьшего веса, соединяющее вершины компоненты с остальными вершинами. По теореме такое ребро является безопасным.

Теорема. Остовное дерево, которое строится описанным алгоритмом, имеет минимальный вес.



Рис. П1. Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер.



Рис. П2. Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.



Рис. П3. Следующее безопасное ребро с весом 11. Добавляем его.



Рис. П4.



Рис. П5.



Рис. П6.



Рис. П7.



Рис. П8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.