Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Дискретная оптимизация_КНИГА.doc
Скачиваний:
76
Добавлен:
09.03.2016
Размер:
3.32 Mб
Скачать

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

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

Поскольку остов содержит все вершины данного графа 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={Г1=(V11),...,Гк=(Vkk)} графа G называется остовным лесом (или короче лесом) графа G, если

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

  2. Vp Vq=Ø (p,q=1,2,…,k);

  3. V=V1 V2Vk.

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

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

Пусть

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

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

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

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

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

Лемма 5Л. Пусть r={Г1=(V1,E1),..., Гk=(Vk,Ek)} — остовный лес графа G. Ребро e={v,w} — внешнее к лесу г ребро, причем vVp. wVq, 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. Лес r0 объявить растущим лесом г. (Напомним, что че­рез r0 обозначен ранее тривиальный лес, и что с(r0) = С).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. procedure СЛИТЬ(v,w,p,q);

  2. begin

  3. ИМЯ[w]:=p; u:=СЛЕД[w]; (* включили w в V' *)

  4. while ИМЯ[u] ≠ p do

  5. begin (* включаем все V" в V' *)

  6. ИМЯ[u]:=p; u:=СЛЕД[u];

  7. end;

(* сохранение структуры данных *)

  1. РАЗМЕР[p]:= PA3MEP[p]+PA3MEP[q];

  2. v':=СЛЕД[v]; w':= СЛЕД[w];

  3. СЛЕД[v]:=w'; СЛЕД[w]:= v'

  4. end.

Отметим некоторые особенности работы этой процедуры. Объединение множеств 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.

  1. begin

  2. Сформировать из Е ОЧЕРЕДЬ по возрастанию весов ребер;

  3. for vV do

  4. begin ИМЯ[v]:=v; СЛЕД[v]:=v, PA3MEP[v]:=1;

  5. end; (* построен лес r0 *)

  6. Т:=Ø;

  7. while |T|≠n-l do

  8. begin (* начинаем расширять лес *)

  9. {v,w} ОЧЕРЕДЬ; ОЧЕРЕДЬ;

  10. р:=ИМЯМ; q:=ИМЯ[w];

  11. if p≠q then (* можно расширять лес по {v,w} *)

  12. begin (* выбираем оптимальный способ слияния *)

  13. if PA3MEP[p)>PA3MEP[q] then СЛИТЬ(v,w,p,q)

  14. else СЛИТЬ(w,v.q,p);

  15. T:=T{v,w};

  16. end;

  17. end;

  18. end

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

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

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

|V, 1=1, | V2| > 2,..., | Vi | > 2i,…,n=|V| = |vk|≥2k,

отсюда n ≥ 2k, то есть 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} }. В приведенной ниже таблице показано, как формировался остов данного графа.

b) Минимальный остов графа G

а) Граф G

Рис. 5.1. Взвешенный граф и его минимальный остов

|T|

ИМЯ

T

1 2 3 4 5 6

0

1 2 3 4 5 6

Ø

1

1 1 3 4 5 6

{1,2}

2

1 1 3 3 5 6

{1,2}, {3,4}

3

1 1 3 3 5 5

{1,2}, {3,4}, {5,6}

4

1 1 1 1 5 5

{1,2}, {3,4}, {5,6}, {1,3}

7

1 1 1 1 1 1

{1,2}, {3,4}, {5,6}, {1,3}, {3,5}

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

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

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

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

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

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

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

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

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

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

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

  1. begin

  2. Зафиксировать произвольную вершину wV;

  3. F:=V\{w}; Т:=Ø;

  4. for vV do

  5. begin БЛИЖНИЙ[v]:=w; d[v]:=A[v,w];

  6. end; (* инициализация завершена *)

  7. while |T|≠n-1 do

  8. begin v:=MIN(F);

  9. T:=T{v,БЛИЖНИЙ[v]}; F:=F\{v}; (* остов T увеличен *)

  10. for uF do

  11. if d[u]>A[u,v] then

  12. begin БЛИЖНИЙ[u]:=v; d[u]:=A[u,v];

  13. end;

  14. end;

  15. end.

Теорема 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,

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

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

|T|

V*=V\F

БЛИЖНИЙ

D

Т

2 3 4 5 6

2 3 4 5 6

0

1

1 1 1 1 1

2 3 4 ∞ ∞

Ø

1

1,2

1 2 1 1

3 3 ∞ ∞

{1,2}

2

1,2,3

3 3 3

2 4 5

{1,2}, {1,3}

3

1,2,3,4

3 4

4 4

{1,2}, {1,3}, {3,4}

4

1,2,3,4,5

5

2

{1,2}, {1,3}, {3,4}, {3,5}

5

1,2,3,4,5,6

{1,2}, {1,3}, {3,4}, {3,5}, {5,6}

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

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

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

ЗАДАЧИ

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

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

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

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

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

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

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

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

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

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

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

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

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

В пункт

A

B

C

D

E

A

0

40

60

80

B

Из пункта

0

80

70

60

C

40

80

20

30

D

60

70

20

25

E

80

60

30

25