Теоретическая часть
Основные определения
Граф G = (V, E) -непустое множество вершин V и ребер E (являющееся подмножеством V 2), их соединяющих. Граф можно визуально представить в виде точек вершин, а также направленных отрезков, соединяющие их ребра.
Граф называется взвешенным, если каждому ребру поставлено в соответствие некоторое число, называемое весом ребра. Циклом называют путь, в котором первая и
последняя вершины совпадают.
Связный граф такой граф, между любой парой вершин которого, существует по крайней мере один путь. Дерево это связный ацикличный граф. Ацикличность означает, что между любой парой вершин в дереве существует только один путь. Остовное дерево связного неориентированного графа поддерево данного графа, в который входят все его вершины. Неформально говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим ребрам, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.
Минимальное остовное дерево в связанном, взвешенном, неориентированном графе это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
Алгоритм Краскала
Существует несколько алгоритмов, которые позволяют находить минимальное остовное дерево в заданном связном неориентированном графе G = (V, E). Наиболее
эффективным из них является Алгоритм Краскала [1]:
1.
На каждом шаге поддерживается набор
ребер минимального остова E .
В
самом начале оно является пустым, E = ∅.
2. Выберем еще не рассмотренное ребро (u, v) ∈ E, причем минимального веса.
3. Если все ребра рассмотрены, то алгоритм завершен, а граф G = (V, E ), является минимальным остовным деревом графа G = (V, E). Иначе выполнение с шага 2.
Рассмотрим подробнее шаг 3, а точнее, проверку на образование цикла. Для того
чтобы упростить задачу, будем поддерживать множество T непересекающихся подмножеств множества вершин V в графе.
В начале, предположим, что T = {G1 , G2 , . . . , G|V | }, где Gk = {k}. Проще говоря,
каждая вершина в самом начале входит в свое собственное подмножество. Теперь рассмотрим заново шаг 3 алгоритма, c учетом наличия этого множества:
• Если вершины u и v принадлежат различным множествам из T , то это значит, что было найдено ребро минимального веса, соединяющее два подмножества (компоненты связности) в одно.
Объединим эти два множества в одно, и добавим рассматриваемое ребро (u, v)
к множеству E .
Если вершины u и v принадлежат одному и тому же множеству из T , то такое
ребро пропускается, так как при его добавлении образуется цикл.
4 Пояснительная задача
Для чего необходимо понятие минимального остовного дерева? Вот один из примеров.
Задача. Имеются данные о расположении нескольких городов на плоскости, необходимо построить между ними дороги с использованием минимального количества асфальта так, чтобы из любого города существовал путь в остальные.
Решение. Необходимо построить неориентированный граф, состоящий из множества вершин всех городов, и ребер всех возможных пар городов, между которыми возможно построить дороги, а также определить весовую функцию между двумя вершинами в графе w : E → R таким образом (длина дороги):
ц (гб м) = (чг − чм )2 + (нг − нм )2
И найти в нем минимальное остовное дерево. Действительно, как следует из определений, минимальное остовное дерево исходного графа и будет решением задачи.