Задача о минимальном остове

Остовом связного неориентированного графа G={V,E) назы­вается подграф G'=(V',T) графа G, который является деревом и содержит все вершины данного графа G, то есть V-V, T E.

Поскольку остов содержит все вершины данного графа G, то в дальнейшем остов будем отождествлять с множеством его ребер Т. Из теоремы 2.1 следует, что |Т|=n-1, где n=|V|.

Задача построения остова данного графа G фактически рас­сматривалась ранее в главе 4. Действительно, ребра, соответст­вующие дугам как ПВГ-дерева, так и ПВШ-дерева, строящихся алгоритмами ПОИСК В ГЛУБИНУ и ПОИСК В ШИРИНУ, яв­ляются остовами графа G. Далее, поскольку оба алгоритма поис­ка имеют сложность O(n+m), и для связных графов справедливо неравенство m ≥ n-1, где n=|V|, m=|E|, то сложность поиска в связном графе есть О(m). Таким образом справедлива

Теорема 5.1.Остов связного неориентированного графа мо­жет быть построен за время О(m).

Однако, нас в этой главе будет интересовать другая, более сложная задача о построении остова.

Напомним, что граф G=(V,E) называется взвешенным, если задана функция с:E→R; иначе говоря, каждому ребру е графа G приписано число с(е). Число с(е) называется весом или стоимо­стью ребра е, а взвешенный граф обозначается так: G=(V,E,c).

Пусть Т — остов графа G. Число с(Т) = ∑{с(е) : е Т} назовем весом остова Т (или стоимостью остова Т). Остов Т назовем минимальным остовом графа G, если для любого остова Т графа G справедливо неравенство с(Т)<с(Т').

Задача о минимальном остове формулируется следующим образом: в данном связном неориентированном взвешенном гра­фе G построить минимальный остов.

Эта задача имеет широкое практическое применение. Предпо­ложим, например, что требуется построить сеть подачи нефти с места добычи на k перерабатывающих предприятий. Тогда ми­нимальный остов графа, вершины которого соответствуют пунк­там переработки и пункту добычи, а веса ребер — затратам на сооружение нефтепровода между соответствующими пунктами, даст наиболее экономичный способ сооружения распределитель­ной сети.

Аналогичным образом сводится к задаче о минимальном ос­тове, задача проектирования линий связи между некоторым цен­тральным пунктом и периферийными пунктами.

Пусть G=(V,E,c) — заданный граф. Семейство подграфов r={Г₁=(V₁,Е₁),...,Г_к=(V_k,Е_k)} графа G называется остовным лесом (или короче лесом) графа G, если

1. каждое Г_р (р=1,2,...,k) является деревом;

2. V_p V_q=Ø (p,q=1,2,…,k);

3. V=V₁ V₂ … V_k.

Иначе говоря, лес состоит из вершинно-непересекающихся деревьев. Для заданного леса r, через Е_r обозначим множество ребер графа G, входящих хотя бы в одно из деревьев этого леса. Пусть Г_р — дерево леса. Ребра графа G, соединяющие вершины дерева Г_р с вершинами, не входящими в Г_р, будем называть внешними к дереву Г_р. Ребра графа G, внешние по отношению к какому-либо дереву леса r, будем называть внешними к лесу r. Понятно, что внешнее к лесу ребро является внешним к двум де­ревьям этого леса.

Пусть e={v,w} — внешнее к лесу r ребро, причем v V_p, w V_q, p≠q. Расширением r(e) леса r по ребру е назовем лес, полученный из r слиянием двух деревьев Г_р и Г_q в одно. Точнее, из леса r уда­ляем деревья Г_р и Г_q, а вместо них добавляем новое дерево (V_p V_q,E_p E_q {е}). Ясно, что в лесе r(е) деревьев на единицу меньше, но ребер в Е,_(е) на единицу больше (а именно, на ребро е).

Пусть

c(r) = min{c(T): T E_r, Т — остов графа G},

то есть с(r) равно минимуму весов всех остовов графа G, содер­жащих все ребра заданного леса r. Положим

C=min{c(T) : Т — остов графа G}.

Легко видеть, что для любого леса г справедливо неравенство с(r) ≥ С. Заметим, что если в качестве леса r выбрать тривиальный лес { ({V₁ },Ø),...,({v_n},Ø) }, то есть лес, в котором каждое дерево состоит ровно из одной единственной вершины, то справедливо равенство с(r)=С. Этот тривиальный лес обозначим через r₀.

Оба алгоритма решения задачи о минимальном остове, кото­рые будут здесь изложены, основаны на следующем утвержде­нии.

Лемма 5Л.Пусть r={Г₁=(V₁,E₁),..., Г_k=(V_k,E_k)} — остовный лес графа G. Ребро e={v,w} — внешнее к лесу г ребро, причем v V_p. w V_q, p≠q и для ребра е справедливо хотя бы одно из равенств:

а) либо с(е) = min{c(e*): е* —- внешнее к Г_р},

б) либо с(е) = min{c(e*): е* — внешнее к Г_q,}.

Тогда справедливо равенство с(r(е)) = с(r).

Справедливость неравенства с(r(е)) ≥ с(r) очевидна, ибо вся­кий остов, содержащий все ребра леса r(е), содержит и все ребра леса r. Докажем обратное неравенство.

Достаточно доказать, что для каждого остова Т, содержащего Е, (то есть все ребра леса r), найдется остов Т*, содержащий Е_r(е), (то есть все ребра леса r(е)) такой, что с(Т*)< с(Т).

Пусть Т — остов графа G, Т Е_г и е Т. Будем для определен­ности считать, что для ребра е справедливо первое из равенств, о которых говорится в условиях леммы. То есть с(е) = min{c(e*) : е* — внешнее к Г_р}. Добавим ребро е к остову Т. По теореме 2.1 образуется ровно один цикл. Этот цикл обязательно содержит ребро e*=(v*,w*), внешнее к дереву Г_р. По предположению, справедливо неравенство с(е) ≤ с(е*).

Заменим в остове Т ребро е* на ребро е. Полученный остов обозначим Т*. Так как удаленное ребро являлось внешним к лесу r, то справедливо включение Т* Е_r, и, следовательно, Т* Е_r(e). Кроме того. с(Т*)≤с(Т), так как с(е) < с(е*). Тем самым неравен­ство с(r(е)) < с(r) доказано, i

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

Дадим неформальную запись этих алгоритмов.

Жадный алгоритм.

1. Лес r₀ объявить растущим лесом г. (Напомним, что че­рез r₀ обозначен ранее тривиальный лес, и что с(r₀) = С).

2. Пусть r — текущий растущий лес. Выбрать ребро е ми­нимального веса среди всех внешних к r ребер. Провести расширение леса r по ребру е. Новый лес объявить расту­щим.

3. Осуществлять пункт 2 до тех пор, пока текущий лес не сольется в одно дерево.

В силу леммы 5.1 для каждого текущего леса r справедливо равенство с(r)=С, так как для выбираемого ребра в пункте 2 алго­ритма справедливы оба равенства а) и б) леммы 5.1. Справедли­вость равенства с(r)=С для последнего леса, состоящего из одно­го единственного дерева означает, что алгоритм завершает свою работу построением минимального остова исходного графа.

Поедающий алгоритм

1. Лес r₀ объявить растущим лесом r. В лесе r₀ выбрать произвольное дерево (то есть вершину), которое объявить растущим деревом Г.

2. Пусть Г — растущее дерево текущего леса г. Выбрать ребро е, минимальное по весу среди всех ребер, внешних к дереву Г. Провести расширение r по ребру е. В новом лесс дерево, содержащее ребро е, объявить растущим.

3. Повторять пункт 2 до тех пор, пока растущее дерево не станет остовом (иначе говоря, до тех пор, пока оно не по­глотит все остальные вершины).

Корректность поедающего алгоритма также следует из леммы 5.1. Отметим только, что здесь, в отличии от жадного алгоритма, каждый раз выполняется, вообще говоря, лишь одно из равенств а) или б) в лемме 5.1.

Перейдем к формальным описаниям изложенных способов построения минимального остова. Начнем с жадного алгоритма. Этот алгоритм впервые появился в работе Борувки, опублико­ванной в 1926 году. Однако, эта работа была практически забыта. Появление, а затем и широкое распространение компьютеров стимулировало интерес математиков к построению алгоритмов решения дискретных задач. В результате, в 1956 году Краскл вновь открыл жадный алгоритм. С тех пор во многих книгах (например, в [4], [6], [7]) этот жадный алгоритм называют алго­ритмом Краскла. Мы будем называть его алгоритмом Борувки- Краскла.

Одной из основных операций в алгоритме Борувки-Краскла является операция слияния деревьев. Для эффективной организа­ции этого процесса будем использовать три одномерных массива — ИМЯ, СЛЕД, РАЗМЕР, каждый длины n.

Будем считать, что в каждом дереве Г*=(У*,Е*), строящегося леса г выделена вершина v V*, и для всех остальных вершин w V* справедливо равенство ИМЯ[w]= v. Тем самым вершины разных деревьев имеют разные имена.

Вообще говоря, одного массива ИМЯ вполне достаточно для описания множества вершин некоторого дерева, однако если ог­раничиваться только этим массивом, то для определения всех вершин данного дерева, входящего в лес, пришлось бы просмот­реть весь массив ИМЯ. Просмотра всего массива ИМЯ можно избежать, используя массив СЛЕД, который задает «кольцевую» структуру на множествах вершин деревьев, следующим образом. Считаем, что множество вершин V* дерева Г*=(V*,Е*) упорядо­чено произвольным образом: V*={v₁,...,v_s}. Будем считать, что СЛЕД[v_к]=v_к+1 для всех k=l,...,s-l, и СЛЕД[v_s]=v₁ т.е. СЛЕД[v] дает следующую вершину множества V*, при этом первая вер­шина следует за последней.

Наконец, PA3MEP[v] указывает количество вершин в дереве с именем v.

Опишем теперь процедуру слияния двух деревьев Г'- (V',E') и Г"=( V",Е") по ребру {v,w}, где v V', w V". Считаем, что опре­делены массивы ИМЯ, СЛЕД, РАЗМЕР и р=ИМЯ[v], q=ИМЯ[w], причем p≠q.

Отметим некоторые особенности работы этой процедуры. Объединение множеств V' и V" состоит в сущности в смене име­ни у всех вершин множества V" (цикл 4-7). Отсюда следует не­симметричность процедуры, а именно, сложность выполнения процедуры СЛИТЬ(v,w,p,q) равна O(|V"|), a СЛИТЬ(w,v,q,p) — O(|V'|).

Строки 8-10 предназначены для сохранения структуры дан­ных. В них происходит формирование одного коль­цевого списка описания множества V' V" из двух списков. Для этого достаточно исправить всего лишь две ссылки СЛЕД[v] и СЛЕД[w], и установить длину для нового кольца, получившего имя р. Множество с именем q исчезает.

Теперь у нас все готово для формализованного описания жад­ного алгоритма. Предполагается, что граф задан либо списками, либо массивом, либо матрицей смежностей. Отметим, что усло­вие в строке 13 обеспечивает эффективность выполнения проце­дуры СЛИТЬ, так как имена меняются у того множества, которое содержит меньше элементов.

АЛГОРИТМ 5.1. БОРУВКА-КРАСКЛ

Данные: связный взвешенный граф G=(V,E,c).

Результат: Т — минимальный остов графа G.

Теорема 5.2.Вычислительная сложность алгоритма Борувки- Краскла равна O(mlogm).

Сложность формирования очереди в строке 2 есть O(mlogm) (см.гл.З). Цикл в строках 7-17 проработает в худшем случае m раз, ибо в этом случае нужно просматривать все ребра. Однако увеличение Т будет проходить ровно (n-1) раз, и каждое увеличе­ние Т соответствует вызову процедуры СЛИТЬ. Слияние деревь­ев заключается в изменении переменной ИМЯ[v] для всех вер­шин v одного из деревьев.

Каждая вершина v V может менять ИМЯ[v] не более раз, ибо при каждом слиянии размер нового множества вершин не менее чем в два раза больше размера изменяемого множества (см. строки 13-14). Действительно, пусть вершина v меняет имя к раз. Обозначим через V₁,V₂,...,V_k=V последовательно множества вершин тех деревьев растущего леса в которые попадала вершина v. Тогда справедлива следующая цепочка равенств и нера­венств:

|V, 1=1, | V₂| > 2,..., | V_i | > 2ⁱ,…,n=|V| = |v_k|≥2^k,

отсюда n ≥ 2^k, то есть k ≤ logn.

Значит, затраты на слияние равны O(nlogn), так как в графе n вершин. Итого, сложность цикла 7-17 есть 0(m+nlogn). Оконча­тельно, сложность алгоритма 5.1 равна

O(mlogm) + 0(m+nlogn)=0(mlogm),

ибо связность графа G влечет, что m ≥ n-l. □

На рис.5.1 изображен связный взвешенный неориентирован­ный граф G. Числа, стоящие рядом с ребрами, означают их веса. Минимальный остов получен в предположении, что ребра упоря­дочены в соответствии с их весами следующим образом: ОЧЕ­РЕДЬ = { {1,2},{3,4},{5,6},{1,3},{2,4},{ 1,4},{3,5},{4,6},{3,6} }. В приведенной ниже таблице показано, как формировался остов данного графа.

Перейдем к рассмотрению поедающего алгоритма. История его появления во многом схожа с историей предыдущего алго­ритма. Впервые он появился в работе Ярника, опубликованной в 1930 году, затем переоткрыт Примом в 1957 году и, независимо, Дейкстрой в 1959 году. При этом Дейкстра предложил довольно эффективную реализацию этого алгоритма — метод расстановки специальных меток, который мы здесь будем использовать. В литературе поедающий алгоритм чаще всего называют алгорит­мом Прима, реже — алгоритмом Прима-Дейкстры. Справедливее называть его алгоритмом Ярника-Прима-Дейкстры. что мы и бу­дем делать.

Для ребра e={v,w} вместо c({v,w}) будем писать c(v,w). На­помним, что в поедающем алгоритме остовной лес расширяется путем поглощения одним и тем же деревом ближайшей к нему вершины графа. А именно, если V* — множество вершин расту­щего дерева, то каждый раз ищется вершина v, не входящая в V*. для которой существует вершина w из V* так, что выполняется условие

c(v,w) = min{c(u,u') : u V*, u' V*}.

Понятно, что эффективность этого алгоритма зависит от того, насколько быстро будет осуществляться поиск ближайшей к рас­тущему дереву вершины. Эффективный выбор ближайшей вер­шины можно осуществить с помощью двух массивов: БЛИЖ­НИЙ и массива меток d. Пусть V* — множество вершин расту­щего дерева. Через d[v] обозначим расстояние от v до множества V*, то есть

d[v] = min{c(v,u) : u V*}.

Значением БЛИЖНИИ[v] является та самая вершина w из V*, для которой этот минимум реализуется. Таким образом, всегда выполняется равенство

d[v] = с(v,БЛИЖНИЙ[v]).

Через F будем обозначать множество вершин, не входящих в растущее дерево. Будем считать, что если {v,w} E, то c(v,w)=+∞. Через MIN(F) обозначим функцию, значением которой является вершина v F, имеющая минимальное значение метки d. Иначе говоря, вершина MIN(F) ближе всего расположена к растущему дереву с множеством вершин V\F.

АЛГОРИТМ 5.2. ЯРНИК-ПРИМ-ДЕЙКСТРА

Данные: связный неориентированный взвешенный граф G=(V,E,c). заданный матрицей весов А[1..n].

Результат: Т — минимальный остов графа G.

Теорема 5.3.Алгоритм Ярника-Прима-Дейкстры имеет сложность O(n)

Каждый проход цикла 7-14 завершается добавлением новой вершины в растущее дерево, или, что то же самое, уменьшением на единицу числа вершин в множестве F. Отметим, что цикл 7-14 работает n-1 раз. Пусть растущее дерево содержит k вершин, то­гда в F ровно n-k вершин. Следовательно, число операций, тре­буемых для выбора вершины MIN(F), пропорционально n-k (строка 8). В строках 10-13 осуществляется пересчет меток для n-k-1 вершины, то есть число операций в цикле 10-13 пропорцио­нально n-k-1, или, что то же самое, пропорционально n-k. Окон­чательно, число операций в алгоритме 5.2 пропорционально сум­ме

S=n+(n-1 )+(n-2)+... +1,

которая имеет порядок n², что доказывает теорему.

Проиллюстрируем работу алгоритма 5.2 на графе, изображен­ном ранее на рис.5.1. Здесь в качестве вершины w выбрана вер­шина с номером 1.

В результате получим тот же остов Т, что и на рис.5.1. Здесь неявно предполагалось, что функция MIN(F) при наличии не­скольких претендентов выбирает тот, у которого номер меньше. Например, в третьей строке таблицы вершине 3 отдано предпоч­тение перед вершиной 4. Аналогичная ситуация в предпоследней строке.

Постройте остов этого графа G в предположении, что функция MIN(F) отдает предпочтение вершинам с большими номерами.

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

ЗАДАЧИ

1. Пусть во взвешенном графе G множество вершин V раз­бито на два непересекающихся подмножества V₁ и V₂, е — ребро минимального веса среди всех ребер, соединяющих вершины множеств V₁ и V₂. Докажите, что любой минимальный остов графа G содержит ребро, соединяющее V₁ и V₂, того же веса, что и у ребра е (Это утверждение иногда называют леммой Прима. По сути дела, это перефразировка леммы 5.1).

2. Предложите алгоритм построения остова максимального веса.

3. Исследовать min-max задачу построения остова. А имен­но. весом остова Т графа G считаем число с(Т)=mах{с(е) : е Т}. Требуется найти остов минимального веса. Аналогично, сформу­лируйте и исследуйте max-min задачу построения остова.

4. Пусть в связном неориентированном графе G=(V,E) ребра разделяются на два класса: класс "плохих" и класс "хороших" ребер. Предложите алгоритм сложности О(m), строящий остов такого графа с минимально возможным количеством "плохих" ребер.

5. Пусть М — множество точек на плоскости. Рассмотрим граф, вершинами которого являются точки множества М, все они считаются смежными, а веса ребер равны расстоянию между со­ответствующими точками. Минимальный остов этого графа на­зывается минимальным связывающим деревом (МСД) множества М. Предложите алгоритм построения МСД множества М слож­ности O(nlogn), где n=|М|.

Докажите, что степень вершины в МСД не более 6, если рас­сматривается евклидова метрика, и не более 8, если рассматрива­ется прямоугольная метрика: d(x,y)= |x₁—у₁|+|х₂—у₂|.

6. Рассмотрим следующий алгоритм построения минималь­ного остова графа G=(V,E,c).

1) Лес r₀ объявить растущим лесом r.

2) Пусть r — текущий лес. Просмотреть все множество Е и зафиксировать по одному внешнему ребру мини­мального веса для каждого дерева из леса r (ребро — внешнее для дерева, если ровно один его конец принад­лежит этому дереву).

3) Добавить выбранные ребра к лесу r. Выделить ком­поненты связности нового графа, полученный лес объя­вить растущим.

4) Повторять 2 и 3, пока лес не сольется в одно дерево.

Предложите реализацию этого алгоритма сложности 0(mlogn).

7. Транспортное управление планирует строительство дорог, которые должны соединить пять населенных пунктов. Все эти пункты должны быть соединены друг с другом либо непосредст­венно, либо дорогой, проходящей через другой пункт. Затраты (в млн. руб.) на строительство приводятся в таблице. Число ноль означает, что соответствующая дорога уже имеется. Какие доро­ги следует построить?

В пункт

	A	B	C	D	E
A	—
B		—
C			—
D				—
E					—

Глава VI

Пути в сетях

Напомним, что ориентированный взвешенный граф G=(V,E,c) называется сетью. Сеть может быть представлена в компьютере матрицей весов дуг, массивами смежностей СЛЕД или ПРЕДШ, или списками СЛЕД[v] или ПРЕДШ[v]. При этом записи в спи­сках смежностей состоят из грех компонент: поля имени узла, поля веса соответствующей дуги и поля ссылки на следующую запись.

Пусть р: v=v₀,v₁,...,v_k=w — путь в сети G от узла v до узла w (v-w-путь); положим

c(p)⁼c(v₀, v₁)+...+c(v_k-1, v_k).

Число с(р) назовем длиной пути р. Наименьшую из длин v-w-путей назовем расстоянием от v до w, а тот v-w-путь, длина которого равна расстоянию от v до w, — кратчайшим v-w-путем. Ясно, что расстояние от v до w может отличаться от расстояния от w до V.

Задача о кратчайшем пути (ЗКП) между фиксированными узлами: в заданной сети G с двумя выделенными узлами s и t найти кратчайший s-t-путь.

Отметим сразу, что ЗКП можно рассматривать и в неориенти­рованных взвешенных графах, заменив каждое ребро {v,w} графа двумя дугами (v,w) и (w,v) и считая, что c(v,w)=c(w,v)=c({v,w}).

Далее, если в невзвешенном графе положить вес каждого реб­ра равным единице, то получим данное ранее определение длины пути (см.гл.2 и гл.4) как числа ребер. С этой точки зрения рас­смотренная в гл.4 задача построения кратчайшего по числу ребер пути есть частный случай сформулированной только что задачи.

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

Можно дать много практических интерпретаций ЗКП. Одна из таких была дана в главе первой, где была рассмотрена задача на­хождения самого короткого пути между городами. Другая, менее очевидная ситуация возникает в задаче выбора самого надежного пути передачи информации в некоторой информационной сети.

Пусть имеется информационная сеть, связывающая n пунктов связи, и для каждого канала (v,w) передачи информации от пунк­та связи v к пункту w известна вероятность P(v,w) его безаварий­ной работы. Предположим, что аварии каналов не зависят друг от друга. Тогда вероятность исправности пути q: s=v₀,v₁,...,v_k=t пе­редачи информации от s до t равна

P(q) = П{P(v_i-1,v₁) : i=l,2,...,k}.

Самым надежным путем передачи информации от s к t естест­венно считать тот путь q, для которого значение P(q) максималь­но.

Рассмотрим сеть G*. узлы которой соответствуют пунктам связи, а дуги — каналам передачи информации, и для дуги (v,w) полагаем c(v,w) = -logP(v,w). Пусть в этой сети для узлов s и t решена ЗКП, то есть найден кратчайший s-t-путь q: s=v_o,v₁,…,v_k=t. Иначе говоря, c(q) = ∑{c(v_i-1,v₁):i=l,2,...,k}→min среди всех s-t-путей, то есть ∑{-logP(v_i-1,v₁):i=l,2,...,k}→min.

Тогда log(П{P(v_i-1,v₁):i=l,2,...,k})→max.Отсюда следует, что для кратчайшего s-t-пути q вероятность правильного прохожде­ния сигнала максимальна среди всех s-t-путей. Таким образом, кратчайший s-t-путь в сети G* определяет самый надежный путь передачи информации в информационной сети.