Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Миха.doc
Скачиваний:
2
Добавлен:
01.03.2025
Размер:
1 Мб
Скачать
☆

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

Минимальным остовным деревом называется дерево с минимальным общим весом его рёбер.

Минимум остовных деревьев графа Г = (X, U, Ф) можно найти, применяя процедуру исследования рёбер в порядке возрастания их весов. Другими словами, на каждом шаге выбирается новое ребро с наименьшим весом, не образующее циклов с уже выбранными рёбрами. Процесс продолжается до тех пор, пока не будет выбрано –1 ребро. Рассмотренная процедура называется «жадным» алгоритмом , разработана французским учёным Краскалем в 1956г., использовалась при проектировании французских электрических сетей.

Пользуясь алгоритмом Краскаля для поиска минимального остовного дерева на графе возможных соединений схемы информационной сети, можно найти схему соединений всех объектов по критерию минимума суммы всех расстояний от одного объекта до другого. Согласно алгоритму Краскаля:

- сортируем все рёбра графа (соединения между объектами в порядке возрастания расстояния между ними);

- берём ребро с минимальной стоимостью и проверяем не образует ли это ребро с ранее рассмотренными рёбрами цикла или петли;

- если не образует цикла или петли добавляем к ранее уже выбранным последующие рёбра;

- проделываем эту последовательность пока не будут соединены все вершины полного графа.

Реализация данной схемы может быть выполнена следующим образом. Для каждой вершины Х= {хь х2,.... хп} графа Г = (X,U,Ф) формируются начальные тривиальные компоненты связности:

где i=j, I=1,2,…,

Компоненты являются деревьями, объединение которых даёт начальное приближение строящегося остовного дерева Г0 = (X, ,Ф).

Включение в строящееся остовное дерево Г0 выбранного ребра на очередном шаге «жадного» алгоритма выполняется слиянием

и двух компонент , , которым принадлежит по вершине нового ребра, и включением самого ребра в объединённое множество рёбер. Процесс роста объединения

компонент к остовному дереву Г0=(Х, U0, Ф) продолжаем до тех пор, пока не будет включено – 1 ребро.

Справедливость «жадного» алгоритма является следствием следующих двух лемм.

Лемма 1. Пусть Г=(Х, U, Ф) – связный неориентированный граф и

Г =(Х, Ф) – произвольное остовное дерево для него. Тогда:

1). V Х cуществует единственная между ними цепь в Г0;

2). если к Г добавить ребро из U/U , то возникнет ровно один цикл.

Лемма 2. Пусть Г =(Х, U, Ф) – связный неориентированный граф, для каждого ребра определён вес и – компоненты связности «жадного» алгоритма, объединение которых , согласно алгоритму, растёт к остовному дереву Г0=(Х, U0, Ф), где i = 1,2,…,k и

Пусть следующим найденным для включения ребром является ребро Е =(х,у) наименьшего веса из оставшихся U и пусть Тогда найдётся остовное дерево Г для Г =(Х, U, Ф), содержащее рёбра вес которого не больше любого другого остовного дерева, содержащего ребра у U .

Используя алгоритм Краскаля, построим минимальное остовное дерево (информационную сеть, обладающую минимальной длиной).