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

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

Пусть G = (V, E)  граф, w: E R  вещественная функция, ставящая, в соответствие каждому ребру e число w(e)  вес ребра e.

Пара <G, w> называется взвешенным (или нагруженным) графом. Весом любого подграфа взвешенного графа называется сумма весов его ребер.

Рассмотрим следующую задачу: проектируется сеть шоссейных дорог, связывающих 5 населённых пунктов. Известна стоимость строительства любой дороги, соединяющих два пункта. Нужно построить самую дешёвую сеть, по которой можно проехать из любого пункта в любой другой (рис. 9.3).

рис. 10.1

Данный граф является полным графом порядка 5. В этой ситуации заданные пункты можно считать вершинами с весами рёбер, равными стоимости строительства дорог, соединяющих эти пункты (указаны в кружках). Тогда искомая сеть будет остовом минимального веса этого графа. Остов связного графа является деревом. Поскольку полный помеченный граф К_n по теореме Кэли содержит n^n2 различных остовных деревьев (для графа на рис. 9.3 число остовов 5³ =125), то решение этой задачи полным перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n. Однако для её решения имеются эффективные алгоритмы. Рассмотрим два из них  алгоритмы Д. Краскала (1956 г.), и Р. Прима (1957 г.), применимые к произвольному связному графу.

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

1. Строится подграф Т1=Оn + e₁, где Оn  пустой остовный подграф в G, e₁ – ребро минимального веса.

2. Если построен подграф Т_i, содержащий i рёбер, где i<n-1 то строится ациклический подграф Т_i+1= Т_i + e_i+1, где e_i+1рёбро графа G, имеющее минимальный вес среди ребер, не входящих в Т_i и не образующий циклов с рёбрами из Т_i.

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

Теорема 10.1. При i<n1 граф Т_i+1 можно построить. Граф Т_n1 является остовом минимального веса во взвешенном графе <G,w>.

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

Рассмотрим граф Т_n-1. Поскольку Т_n1 является (n, n1)графом без циклов, то по теореме 9.1 является деревом. Докажем, что Т_n-1  остов минимального веса. Предположим противное. Среди всех остовов графа G минимального веса выберем такой остов Т, который имеет с деревом Т_n1 максимальное число общих рёбер. Пусть ei = (а,в) ребро дерева Т_n-1, не содержащееся в Т и имеющее минимальный номер среди рёбер дерева Т_n-1, не входящих в Т (в процессе построения дерева Т_n-1 его рёбра получили номера 1,2,…,n1). В дереве Т есть простая (а,в) цепь. Присоединив к ней ребро е_i , получим цикл. В этом цикле есть ребро е, не входящее в дерево Т_n-1 (иначе в Т_n-1 был бы цикл). Заменив в дереве Т ребро е на е_i, получим новый остов Т = Т – е + е_i. Но Т  остов минимального веса, следовательно, w(Т^) = w(T) + w(ei)  w(e) ≥ w(T), т.е. w(e_i) ≥ w(e) (1). С другой стороны, присоединяя ребро е к Т_i1 (при i=1 полагаем Т_i1 = О_n), мы не получим цикла, поскольку рёбра е1,е2,…, е_i-1, е входят в дерево Т, и потому, если бы вес w(ei) был больше, чем w(e), мы взяли бы при построении дерева Тi ребро е вместо e_i. Из (1) теперь следует, что w(e_i)= w(e), w(Т)= w(Т).

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

Теперь зная алгоритм, решим задачу. На каждом шаге будем строить ациклический подграф с 5 вершинами (n=5), значит будет n1 = 4 шага (рис. 9.3). На первом шаге выбираем e₁ = (1,5), на втором  e₂ = (2,4), на третьем  e₃ = (1,3)

и на четвертом  e₄ = (5,4). Рёбра (1,5), (2,4), (1,3), (4,5) составляют остов минимального веса. Вес остова Т_n1 равен:

w(Т_n-1) = 1+2+3+4 = 10. Таким образом, эта сеть дорог (рис.9.3 (4)) будет самой дешёвой и ее строительство обойдётся в 10 условных единиц.

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

1. Выбираем ребро e₁ = (a,b) минимального веса и строим дерево D₁ = e₁.

2. Если дерево D_i, содержащее i ребер порядка i + 1, уже построено , и i < n  1, то среди ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в D_i, выбираем ребро e_i+1 минимального веса и строим дерево D_{i+1 =} D_i e_i+1 (рис.9.4).

Для алгоритма Прима также верна теорема 10.1.

Теорема. Алгоритм Краскала строит минимальный остов (n,m)-графа G за время O(m×n).

Доказательство: в алгоритме Краскала n - 1 шагов; на каждом шаге разыскивается ребро минимального веса из некоторого списка ребер, содержащего не более m ребер, поэтому число операций кратно m×n.