Минимальное остовное дерево графа — это остовное дерево какого-либо графа, которое имеет самый маленький из возможных вес, то есть минимальную сумму числовых значений рёбер, входящих в остов.
Введение
Проблема определения остовного дерева с минимальным весом чаще всего формулируется следующим образом: имеется n-ное количество городов, которые требуется связать между собой дорогами таким образом, чтобы иметь возможность проехать из каждого города в любой иной город непосредственно или же через другие города, при этом можно осуществлять строительство дорог между выбранными двумя городами и задана себестоимость построения всех этих дорог. Необходимо определить, какие конкретно дороги лучше построить, чтобы общие вложения средств были минимальны. Такая задача формулируется в терминологии теории графов как задача об определении минимального остовного дерева графа, у которого вершинами являются города, а рёбрами являются дороги между парами городов, которые нужно построить. Весом ребра считается стоимость построения каждой дороги.
Другим примером может служить подразделение рисунков на сегменты и формирование объектных границ, которое является одной из определяющих операций в компьютерном зрении и применяется при распознавании образов и выделении объектов. В общем случае, данная методика аналогична сортировке и может оказать помощь при решении более сложных задач. С этих позиций необходимо чёткое и ясное понимание принципов работы алгоритмов такого вида.
Алгоритм Краскала
Смысл алгоритма Краскала заключается в формировании базы, а конкретно остова дерева исходного графа, который имеет минимальное значение. Возьмём наиболее типовой пример. Имеется карта и на ней помечены выбранные города, которые необходимо соединить набором дорог. И поставлено одно условие, что суммарную протяжённость дорог требуется сделать минимальной. Для решения такой задачи требуется наличие следующих компонентов:
- Комплект нужных графов.
- Формулировка алгоритма Краскала.
- Дополнительная структура, требуемая для эффективного выполнения этого алгоритма.
Рисунок 1. Алгоритм Краскала. Автор24 — интернет-биржа студенческих работ
В сформулированной задаче вершинами графа Vj считаются города, а рёбрами e(Vi, Vj) тогда будут дороги, которые соединяют города. Исходным параметром, помимо этого, считаются дистанции между городами Vi, Vj, являющиеся весами рёбер W(e(Vi, Vj)). Требуется найти минимальное остовное дерево, иными словами найти дерево в графе, не обладающее циклами, чтобы сумма весов рёбер была минимальной, а каждая вершина была достижимой.
Для выполнения такого алгоритма, нужно определить множество вершин G таким порядком, чтобы все его вершины были так же в минимальном остовном дереве. Чтобы достигнуть поставленной цели, необходимо:
Отсортировать все рёбра графа согласно возрастанию их весов, то есть увеличению дорожных дистанций.
Выполнить проход рёбер согласно увеличению их веса и сделать анализ окончания ребра e = (a,b):
- Если вершины a и b принадлежат одному множеству, то можно сделать вывод, что они уже входят в состав некоего подмножества малого минимального остовного дерева. И существует свой подграф с самой маленькой суммой рёбер. Такое ребро алгоритм должен пропустить, так как иначе оно способно привести к формированию цикла в дереве.
- Если вершины a и b принадлежат разным подмножествам малого минимального остовного дерева, то это означает, что их нужно объединить, так как определена дорога (ребро) с минимальной длиной, объединяющая два подмножества в одно целое. Рёбра, которые имеют меньшую длину, алгоритмом уже проанализировал, и объединить их с меньшим весом, чем текущий, вариантов не будет. Такое ребро заносится в набор рёбер, которые нужны для создания минимального остовного дерева, а множества объединяются в одно.
- Выполнение объединяющего цикла в алгоритме осуществляется до тех пор, пока не будет сформировано единое множество, которое и будет тем самым минимальным остовным деревом, включающим в себя все вершины графа.
В результате определяем требуемое множество вершин минимального остовного дерева графа с перечнем рёбер, которые нужны для его построения. То есть, это дерево с минимальным суммарным весом, объединяющее все вершины.
Рисунок 2. Решение задачи. Автор24 — интернет-биржа студенческих работ
