На этом шаге мы рассмотрим задачу о минимальном остове.
Пусть G = (V, Е) - связный обыкновенный граф. Напомним, что его остовом называется остовный подграф, являющийся деревом. Остов (n, m)-графа легко найти поиском в глубину или поиском в ширину. Поскольку оба поиска имеют сложность O(m + n) и в связном графе m > n-1, остов связного (n, m)-графа можно найти за время O(m).
Граф G = (V, Е) называется взвешенным, если задана функция с: Е → R. Это означает, что каждому ребру е такого графа поставлено в соответствие число c(e), называемое весом или стоимостью ребра е. Иными словами, взвешенный граф - это тройка (V, Е, с). Для произвольного ненулевого подграфа Н его весом c(Н) будет называться сумма весов всех ребер подграфа Н.
Остов Т взвешенного графа G назовем минимальным остовом, если для любого остова Т' выполнено неравенство c(Т) ≤ c(Т').
Этот шаг посвящен решению следующей задачи: в данном связном графе найти минимальный остов (задача о минимальном остове).
Пусть G - связный граф. Ациклический остовный подграф F из G будем называть остовным лесом графа G. В том случае, когда остовный лес графа G связен, он является остовом графа G. Ребро е = uv называется внешним к остовному лесу F, если его концы лежат в разных компонентах связности леса F. Если Н - некоторая компонента связности остовного леса F, то через Ext(H) будет обозначаться множество всех внешних ребер, каждое из которых инцидентно некоторой вершине из Н. Ясно, что Ext(H) является сечением графа G.
Предположим, что F - остовный лес связного взвешенного графа G. Будем говорить, что F продолжаем до минимального остова, если существует такой минимальный остов Т, что F ≤ Т.
- Лемма 1.
- Пусть остовный лес F продолжаем до минимального остова и Н - одна из компонент связности леса F. Если е - ребро минимального веса из Ext(H), то остовный лес F+e продолжаем до минимального остова.
- Доказательство.
- Пусть Т - такой минимальный остов графа G, что F ≤ Т и
е ∉ Т. Подграф Т + е содержит единственный цикл С.
Любое сечение и любой цикл имеют четное число общих ребер. Поскольку ребро е является общим для сечения Ext(H) и цикла C,
найдется еще одно ребро f, общее для Ext(H) и С. В силу выбора ребра е имеем c(f) > c(е). Ясно, что
Т' = Т + е - f является остовом графа G и F + е ⊆ Т'. Кроме того,
c(T')= c(T) + c(E) - c(f) ≤ c(T)
учитывая, что Т - минимальный остов, получаем c(Т') = c(Т). Таким образом, Т' - минимальный остов, содержащий лес F + е, т.е. F + е продолжаем до минимального остова.
Лемма 1 позволяет сконструировать два алгоритма построения минимального остова во взвешенном (n, m)-графе G. Пусть F0 - остовный лес, являющийся нулевым графом. Ясно, что лес F0 можно продолжить до остова. Оба алгоритма строят последовательность
F0, F1, ..., Fn-1 (2)
состоящую из остовных лесов, причем Fi = Fi-1 + ei, где еi - ребро, внешнее к остовному лесу Fi-1, 1 ≤ i ≤ n-1. Иногда указанную последовательность называют растущим лесом. Последовательность (2) строится таким образом, чтобы для каждого i, 1 ≤ i ≤ n-1, остовный лес Fi можно было продолжить до минимального остова. Ясно, что тогда Fn-1 является минимальным остовом.
При переходе от Fi-1 к Fi (т.е. при выборе ребра еi) возможны две стратегии.
Стратегия 1. В качестве еi выбираем ребро минимального веса среди всех ребер, внешних к остовному лесу Fi-1.
Пусть Н - одна из двух компонент связности леса Fi-1, содержащая концевую вершину ребра еi. Если Fi-1 продолжаем до минимального остова, то в силу леммы 1 лес Fi = Fi-1 + еi обладает тем же свойством.
Стратегия 2. Здесь предполагается, что каждый остовный лес Fi (1≤ i) из последовательности (2) имеет лишь одну неодноэлементную компоненту связности Нi. Удобно считать, что H0 состоит из некоторой заранее выбранной вершины графа G. Таким образом, по существу, речь идет о построении последовательности
H0, H1, ..., Hn-1 (3)
состоящей из поддеревьев графа G, причем Hi = Hi-1 + ei, где еi ∈ Ext(Hi-1). Иногда указанную последовательность называют растущим деревом.
Последовательность (3) строится следующим образом.
В качестве H0 берем произвольную вершину графа G. Пусть при некотором i, где i < n-1, дерево Hi уже построено. В качестве ci+1 выбираем ребро минимального веса из множества Ext(Hi) и полагаем Hi+1= Hi+ ei+1.
Стратегия 1 реализуется алгоритмом Борувки-Краскала. Этот алгоритм впервые был изложен в работе О.Борувки в 1926 году. Однако данная работа была практически забыта. Появление, а затем и широкое распространение компьютеров стимулировало интерес математиков к построению алгоритмов решения дискретных задач. В результате в 1956 году этот алгоритм был переоткрыт Краскалом.
Отметим, что алгоритм Борувки - Краскала является частным примером жадного алгоритма.
Одной из основных операций в алгоритме Борувки - Краскала является операция слияния деревьев. Для эффективной организации этого процесса будем использовать три одномерных массива - name, next, size, каждый длины n. Пусть F - произвольный член последовательности (2). Массив name обладает следующим свойством: name[u] = name[w] тогда и только тогда, когда вершины u и w лежат в одной компоненте связности леса F. С помощью массива next задается кольцевой список на множестве вершин каждой компоненты связности леса F. Если v = name[w], то size[u] равно числу вершин в компоненте связности остовного леса F, содержащей вершину w.
Опишем процедуру Merge(v, w, p, q), предназначенную для слияния двух деревьев H1 = (V1, E1) и H2 = (V2, E2) по ребру vw, внешнему к остовному лесу F. Предполагается, что v ∈ V1, w ∈ V2, p = name[v], q = name[w].
1. procedure Merge(v, w, p, q); 2. begin 3. name[w]:= p; u:= next[w]; 4. while name[u] ≠ p do 5. begin 6. name[u]:= p; u:= next[u]; 7. end; 8. size[p]:= size[p] + size[g]; 9. x:= next[v]; у:= next[w]; 10. next[v]:= у; next[w]:= х; 11. end;
Отметим некоторые особенности работы этой процедуры. Объединение состоит, по существу, в смене значений name[w] для всех w ∈ V2 (цикл 4-7). Отсюда следует несимметричность процедуры, а именно, сложности выполнения процедур Merge(v,w,p,q) и Merge(w,v,q,p) равны O(|V1|) и O(|V2|) соответственно. Строки 8-10 нужны для сохранения структур данных. В них происходит формирование одного кольцевого списка для элементов объединения V1 ∪ V2. Для этого достаточно исправить значения двух элементов next[v] и next[w] и установить size[p] равным числу элементов в множестве V1 ∪ V2.
Теперь можно дать формальное описание алгоритма Борувки-Краскала. Предполагается, что очередь Q содержит ребра графа. Ради простоты предполагается, что очередь Q организована при помощи массива длины m. В алгоритме используется процедура Sort(Q); эта процедура сортирует очередь Q по возрастанию весов ребер. Процедура Sort(Q) реализует пирамидальную сортировку, поэтому ее сложность равна O(m log m) = O(m log n), поскольку m ≤ n2.
Алгоритм 1 (Борувка, Краскал).
Вход: связный взвешенный граф G = (V, Е, с).
Выход: минимальный остов Т графа G.
1. begin 2. Sort(Q); 3. for v ∈ V do 4. begin 5. name[v]:= v; next[v]:= v; size[v]:= 1; 6. end; 7. T:=0; 8. while |T| ≠ n-1 do 9. begin 10. vw <= Q; p:= name[v]; q:= name[w]; 11. if p ≠ q then 12. begin 13. if size[p] > size[q] then 14. Merge(w, v, q, p) 15. else Merge(v, w, p, q); 16. T:=T ∪ {vw} 17. end 18. end 19. end.
Прокомментируем работу алгоритма 1. Цикл в строках 3 - 6 формирует остовный лес F0. В строке 11 проверяется принадлежность вершин v и w различным деревьям. Слияние деревьев происходит в строках 13 -15.
Для данной вершины v обозначим через r(v) число изменений значения name[v] при работе алгоритма 1.
- Лемма 2.
- Для любой вершины v связного взвешенного G = (V, Е, с) выполнено неравенство r(v) < log |V|.
- Теорема 1.
- Вычислительная сложность алгоритма Борувки - Краскала для связного взвешенного (n, m)-графа равна O(m log n).
- Доказательство.
- Цикл в строках 8-18 проработает в худшем случае m раз. Оценим число операций, необходимых для однократного
выполнения тела цикла. Заметим, что присваивание в строке 16 выполняется ровно m-1 раз. Ясно, что столько
же раз будет выполнена процедура Merge. Из леммы 2 следует, что количество операций, выполненных при
всех вызовах процедуры Merge, не превосходит
Отсюда сложность цикла 8-18 равна O(m + n log n) = O(m log m) = O(m log n), поскольку в связном графе выполнены неравенства n-1 < m < n2.
Осталось заметить, что процедура Sort также требует O(m log m) операций.
На рисунке 1а) изображен связный граф G. Числа, стоящие рядом с ребрами, означают веса ребер. Предполагается, что процедура Sort упорядочивает ребра следующим образом: v1v2, v3v4, v5v6, v1v3, v2v4, v1v4, v3v5, v4v6, v3v6. Минимальный остов показан на рисунке 1б).
Рис.1. Связный граф и минимальный остов
В приведенной ниже таблице указан порядок, в котором строился остов данного графа.
| |T| | Name | T |
|---|---|---|
| 0 | v1, v2, v3, v4, v5, v6 | ∅ |
| 1 | v1, v1, v3, v4, v5, v6 | v1v2 |
| 2 | v1, v1, v1, v4, v5, v6 | v1v2, v3v4 |
| 3 | v1, v1, v1, v1, v5, v6 | v1v2, v3v4, v5v6 |
| 4 | v1, v1, v1, v1, v1, v6 | v1v2, v3v4, v5v6, v1v3 |
| 5 | v1, v1, v1, v1, v1, v1 | v1v2, v3v4, v5v6, v1v3, v3v5 |
На следующем шаге мы рассмотрим алгоритм Ярника - Прима - Дейкстры.
