§ 15. Остов минимального веса

Рассмотрим следующую задачу: во взвешенном связ­ном графе требуется найти остов минимального веса. Эта задача возникает при проектировании линий электропе­редачи, трубопроводов, дорог и т. п., когда требуется заданные центры соединить некоторой системой каналов связи так, чтобы любые два центра были связаны либо непосредственно соединяющим их каналом, либо через другие центры и каналы, и чтобы общая длина (или, например, стоимость) каналов связи была минимальной. В этой ситуации заданные центры можно считать верши­нами полного графа с весами ребер, равными длинам (сто­имости) соединяющих эти центры каналов. Тогда иско­мая сеть будет кратчайшим остовным подграфом полного графа. Очевидно, что этот кратчайший остовный подграф должен быть деревом. Поскольку полный граф К_n содер­жит n^n-2 различных остовных деревьев, то решение этой задачи «слепым» перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относитель­но малых п. Однако для ее решения имеются эффектив­ные алгоритмы. Опишем два из них — алгоритмы Дж. Краскала (1956 г.) и Р. Прима (1957 г.), примени­мые к произвольному связному графу.

Задача об остове минимального веса(о кратчайшем остове): связном взвешенном графе (G, w) порядка n найти остов минимального веса.

Алгоритм Краскала, решающий эту задачу, заключа­ется в следующем.

1. Строим граф t1 = О_n + е1, присоединяя к пустому графу на множестве вершин VG ребро е1 принадлежит EG минимального веса.

2. Если граф Ti уже построен и i<n— 1, то строим граф Ti+1 — Ti + e_{i+1 ,} где e_i+`1 — ребро графа G, имеющее минимальный вес среди ребер, не входящих в Ti и не со­ставляющих циклов с ребрами из Т_i.

Следующая теорема утверждает, что алгоритм Краскала всегда приводит к остову минимального веса.

Теорема 15.1. При i<n—l граф T_i+1 можно построить. Граф T_n-1 является остовом минимального веса в графе (G, w). .

Граф Ti имеет ровно i ребер и потому при i < n — 1 является несвязным. А так как граф G связен, то в нем есть по меньшей мере одно ребро, не составляющее циклов с ребрами графа Т_i. Итак, нужное ребро e_i+1 существует и граф Ti₊₁ можно построить.

Рассмотрим граф Т_n-1. Поскольку Т_n-1 является (n, n— 1)-графом без циклов, то согласно теореме 13.1 дерево. Остается доказать, что вес дерева Т_n-1 минимален. Предположим, что это не так, и среди всех остовов графа G минимального веса выберем такой остов Т, который имеет с деревом Т_n-1 максимальное число общих ребер. Пусть ei = ab — ребро дерева Т_{n-1 ,} не содержа­щееся в Т и имеющее минимальный номер среди ребер дерева Т_n-1 , не входящих в Т (напомним, что в процессе построения дерева Т_n-1 его ребра получили номера 1, 2 ,.. ..., n— 1). В дереве Т есть простая (а, b)-цепь. Присое­динив к ней ребро e_i, получим цикл. В этом цикле есть ребро е, не входящее в дерево Т_{n-1 .} Заменив в дереве Т ребро е на ei, получим новый остов Т' = Т — е + ei. Но Т — остов минимального веса, следовательно, w(T'} = = w(T) + w(ei)- w(e)>=w(T), т. е.

w(e_t)>=w(e). (1)

С другой стороны, присоединяя ребро е к Т_i-1 (при i =1 полагаем Ti-1 = 0_n), мы не получим цикла, поскольку ребра е1, e2, ..., ei-1, е входят в дерево T, и потому, если бы вес w(ei) был больше, чем w(e), мы взяли бы при построении дерева Ti ребро е вместо е_i. Из (1) теперь следует, что w(ei) = w(e), w(T')—w(T).

Итак, Т' — остов минимального веса. Число ребер, общих для деревьев Т' и Т_n-1, больше, чем число ребер, общих для Т и Т_n-1, что противоречит выбору дерева Т. Полученное противоречие и доказывает теорему.

В качестве иллюстрации рассмотрим взвешенный граф, изображенный на рис. 15.1,

Полагаем е1 ={1, 4}, е2 = {4, 5}. Среди оставшихся ребер минимальный вес име­ет, например, ребро {1, 5}. Однако оно не пригодно для построения, поскольку составляет цикл с двумя предыдущими ребрами. Можно взять е3 = {2, 3}, е4 = {2, 5}. Итак, ребра

{1, 4}, {4, 5}, {2, 3}, {2, 5} составляют остов мини­мального веса (рис. 15.1,).

Алгоритм Прима отличается от алгоритма Краскала только тем, что на каждом этапе строится не просто ацик­лический граф, но дерево. Именно:

1. Выбираем ребро е1 = аb минимального веса и стро­им дерево T₁ полагая VT1 =

= {а, 6}, ЕТ1 = {е1}.

2. Если дерево Ti порядка i +1 уже построено и i<n— 1, то среди ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в Ti, выбира­ем ребро e_i+1 минимального веса. Строим дерево Ti+1, при­соединяя к Ti ребро e_i+1 вместе с его не входящим в Т_i концом.

Для этого алгоритма также верна теорема 15.1, дока­зательство которой аналогично приведенному выше.

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

С задачей об остове минимального веса тесно связана задача Штейнера. Первоначально она формулировалась сак следующая

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

Множеству точек U можно поставить в соответствие полный граф K(U), вершинами которого будут элементы U, а вес каждого ребра будет равен расстоянию между соответствующими точками.

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

Если в предыдущей задаче в качестве расстояния меж­ду точками (x1, у1) и (x2, y2) взять величину \Х1— Х2\ +\Y1 — Y2\, то получится прямоугольная задача Штейнера. Эта задача сводится к следующей широко известной задаче.

Задача Штейнера на графах, В связном завершенном графе G с выделенным подмножеством вер шин U e VG требуется найти связный подграф Т, удовлетворяющий следующим двум условиям:

1. множество VT содержит заданное подмножество U;

2. граф Т имеет минимальный вес среди всех подграфов, удовлетворяющих условию

Очевидно, что искомый подграф является деревом. Он называется деревом Штейнера.

Очевидно также, что задача построения дерева Штейнера эквивалентна задаче нахождения остова минималь­ного веса в порожденных подграфах графа G, множества вершин которых содержат U.

Какие-либо эффективные алгоритмы, решающие зада­чу Штейнера, неизвестны.