Минимальное порождающее дерево

Предположим заданным граф, числовые нагрузки (веса) дуг которо­го можно интерпретировать как их длины.

Выше уже отмечалось, что порождающих деревьев у графа может быть много. В рассматриваемом случае с каждым порождающим дере­вом естественно связать число, равное сумме длин всех его дуг. Ясно, что среди этих порождающих деревьев есть хотя бы одно, сумма длин всех дуг которого минимальна. Такое дерево называют минимальным по­рождающим деревом, minimum scanning tree, или минимальным остовом.

Начнем с рассмотрения двух примеров.

Пример 1. Имеется 7 городов А₁, А₂ , A₃ , А₄ , А₅ , А₆ , А₇, которые нужно связать между собой наиболее дешевой сетью дорог, если известно, что стоимость сооружения участка дороги, соединяющей города А_i и А_к (i, к = 1,..., 7 ), пропорциональна ее длине (рис. 9).

Рис. 9. Исходная сеть

Замечание. Граф наиболее дешевой соединяющей сети непременно должен быть деревом. (Если бы это было не так, то в графе нашелся хотя бы один замкнутый путь. При удалении любого из ребер этого замкнутого пути стоимость сети уменьшилась бы, а города все еще оставались соединенными.) Тем самым число ребер искомого графа в предложен­ном примере должно быть равным 6.

Поиск решения можно начать с любого узла. Пусть это будет узел А₁.

1-й шаг. Самая короткая дуга, выходящая из этого узла, — это дуга (А₁, А₂)длины 50. Соединим узлы А₁ и А₂ жирной линией, как показано на рис. 10а, и пометим узлы А₁ и А₂.

Рис. 10а

2-й шаг. Самой короткой дугой, выходящей из помеченных узлов А₁ и А₂, в еще непомеченные, является дуга (А₂, А₃).длины 40. Добавим ее к дереву, выделив жирной линией (рис. 10б)

Рис. 10б

3-й шаг. Узел А₄ расположен к тройке А₁, А₂, А₃ ближе всех других непомеченных узлов. Выделив дугу (А₃, А₄) длины 55, переведем этот узел в помеченные (рис. 10в) и пометим узел А₄.

Рис. 10в

4-й шаг. Следующим узлом будет узел А₆, расположенный к помечен­ной четверке А₁, А₂, А₃, А₄ ближе непомеченных узлов А ₅ и А₇. Выделим дугу (А₃, А₆)длины 75, соединяющую его с узлом А ₃ (рис. 10в), и пометим узел А₆.

5-й шаг. Узел А₇, ближе узла А₅ к пятерке помеченных узлов. Выделим дугу (А₆, А₇)длины 70, соединяющую его с ближайшим узлом A₆, и пометим узел А₇.

6-й шаг. Оставшийся непомеченным узел А₅ соединим с узлом А₇ ду­гой (А₅, A₇)наименьшей длины 45 и также пометим его.

Поведем итог: шесть выделенных дуг связывают все семь узлов за­данной сети. Получающееся в результате минимальное порождающее дерево имеет суммарную длину 335

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

Пример 2. Пусть, например, нужно соединить города А, В, С, D и Е. Стоимости строительства дорог, соединяющих любые два города, известны

	А	В	С	D	Е
А	—
В		—
С			—
D				—
Е					—

Сеть дорог минимальной стоимости состоит из четырех, 5—1=4, дуг и строится так. Сначала выбирается самый дешевый участок доро­ги — ВС, соединяющий города В и С (его цена равна 6).

 

 

	А	В	С	D	Е
А	—
В		—
С			-
D				-
Е					-

Затем он удлиняется на самый дешевый из выходящих из городов В и С - СЕ (его цена равна 8).

	А	В	С	D	Е
А	-
В		-
С			-
D				-
Е					-

На третьем шаге вновь выбирается самый дешевый — это ЕА (его це­на равна 7).

	А	В	С	D	Е
А	-
В		-
С			-
D				-
£					—

Последний участок дороги выбираем так, чтобы не образовалось цикла: соединим для этого город D с ближайшим к нему городом В (его цена равна 9).

	А	В	С	D	Е
А	-
В		-
С			-
D				—
Е					—

Таким образом, минимальная стоимость строительства сети равна 6+ 8 + 7 + 9 = 30 (рис. 11).

Рис. 11.

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

Опишем алгоритм, предложенный Примом [8], считая, что число вершин заданного графа п > 2. Этот алгоритм приводит к искомо­му результату за п — 1 шаг.

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

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

2-й шаг. Рассмотрим все ребра инцедентные помеченным вершинам, за исключением тех, которые соединяют между собой уже помеченные вершины, выберем ребро наи­меньшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, в которую входит это выбранное ребро. В результа­те выделенными оказываются два ребра графа, а помеченными уже три его вершины. Если других вершин в графе нет, то искомое порождающее дерево построено и поставленная задача решена. В противном случае потребу­ется новый шаг.

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

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

На каждом шаге и число выделенных ребер графа, и число помеченных вершин увеличиваются ровно на единицу. Тем самым, по­сле п — 1-го шага количество выбранных ребер станет равным п — 1 и все п вершин графа окажутся помеченными.

Первый шаг можно начинать с ребра наименьшей длины. Его легко найти путем простого перебора всех ребер графа. Если таких ребер несколько, выберем любое из них и пометим концы выбранного ребра. В результате две вершины графа окажутся помеченными. Если других вершин в графе нет, то искомое порождающее дерево построено и поставленная задача решена. В противном случае потребуется новый шаг, совпадающий со 2-м шагом алгоритма, предложенного выше [9].