Пояснительная записка
к курсовому проекту
тема: Построение минимального остовного дерева графа методом Прима
Введение
При проектировании железных дорог, линий электропередачи и других линий коммуникации возникает проблема построения сети с минимальными затратами. В теории графов такая задача успешно решается путем построения минимального остовного дерева неориентированного графа. Данная задача имеет несколько методов решения. Один из них – алгоритм Прима. Суть этого метода заключается в последовательном добавлении к остову минимального, «безопасного» ребра (ребра, которое не образует цикла). В данной работе представлена программа, базирующаяся на алгоритме Прима, которая вычисляет минимальное остовное дерево неориентированного графа и делает визуализацию графа.
1. Историческая справка
Известный алгоритм построения минимального остовного дерева восходит к Войтеху Ярнику (Vojtech Jarnik) [1930]. Он больше известен под именем алгоритма Прима (Robert Prim). Р. Прим независимо от Ярника придумал его в 1956 и представил более подробное и детальное описание, чем первооткрыватель. Еще раз этот алгоритм открыл Эдсгер Дейкстра (Edsger Wybe Dijkstra) в 1958 году, но название осталось за Примом, т. к. у Дейкстры уже был алгоритм с его именем (поиск кратчайших путей в ориентированном графе). Этот алгоритм можно отнести к группе алгоритмов, построенных на наращивании дерева: существует только одна нетривиальная компонента (остальные представляют собой одиночные вершины), и она постепенно наращивается добавлением «безопасных» ребер. Время работы алгоритма Джарника-Прима может достигать O (E+VlogV) при использовании фибоначчиевых куч.
2. Построение минимального остовного дерева Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева с использованием жадной стратегии. Итак, пусть дан связный неориентированный граф G (V; E) c n вершинами и весовая функция w: E → R.
Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u, v) выбирается так, чтобы не нарушить этого свойства: A ∪ {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.
Вот как выглядит общий алгоритм построения минимального остовного дерева:
MST-GENERIC (G, w)
1: A ← 0
2: while (пока) A не является остовом
3: do найти безопасное ребро (u, v) ∈ E для A
4: A ← A ∪ {(u, v)}
5: return A
По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро на шаге 3. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A – одна компонента). ............
