Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала

Минимальное остовное дерево (МОД)

Теорема о минимальном ребре
Алгоритм Краскала (Жадный алгоритм)
Алгоритм

ЯПД (Ярника-Прима-Дейкстры)
Нижняя граница задачи нахождения МОД

Построение и анализ алгоритмов

циклов.
Граф связный, если каждая пара различных вершин графа связана маршрутом.
Для

связного графа G = (V, E) остовным деревом
(остовом, каркасом, стягивающим деревом, скелетом)
является граф (дерево) T = (V, F), где F⊆ E.
Ребра дерева – ветви, остальные ребра графа – хорды.
В графе много остовов, а именно, число остовов nn-2.

Остовное дерево

…

Повторение с предыдущей лекции

m = n – 1 ребер
Доказательство (по индукции):
Остовное

дерево

Ti, ni

Удаляем некоторый узел и k инцидентных ребер (k∈1..n − 1 ).
Образуется лес из деревьев Ti с числом узлов ni (i ∈1..k).

весов W[v, u].
Пусть T = (V, F) – остов

графа.
Вес остова определяется как

Минимальное остовное дерево (МОД)

МОД : TM = Arg min ( W(T) )

различны. Тогда оптимальное остовное дерево графа содержит ребро с наименьшим

весом.

Доказательство (от противного): Пусть {v, u} – кратчайшее из всех ребер – не входит в МОД T.
Добавим {v, u} к T.
Образуется цикл.
Удалим из этого цикла ребро, отличное от {v, u}. Получим T* дерево с весом, меньшим чем вес T, чего не может быть, поскольку T есть МОД (противоречие!).

1. Теорема о минимальном ребре. Версия 0.

дерево графа, содержащее ребро с наименьшим весом.
Доказательство (от противного): Пусть

{v, u} – кратчайшее из всех ребер – не входит в МОД T.
Добавим {v, u} к T. Образуется цикл.
Удалим из этого цикла ребро {v’, u’ }, отличное от {v, u}. Получим T* дерево с весом, меньшим или равным, чем вес T.
Если W [v, u] = W [v’, u’ ], т.е. W(T*)=W(T), то теорема справедлива.
Если W [v, u] < W [v’, u’ ], то W(T*) < W(T), чего не может быть, поскольку T есть МОД (противоречие!).

1. Теорема о минимальном ребре. Версия 0*.

W), а {V1, V2}, есть разбиение V. В G имеется

МОД, содержащее кратчайшее из ребер, одна вершина которого принадлежит V1 , а другая V2.
Доказательство (от противного): Как и ранее, пусть кратчайшее ребро {u, v} (u∈V1 , v ∈V2 ) не входит в МОД …

u

v

u′

v′

На этом цикле есть ребро {u′, v′ }.
W [u, v] ≤ W [u′, v′ ] .
W [u, v] < W [u′, v′ ] . Тогда, удалив {u′, v′ }, получим другое ОД, содержащее T и ребро {u, v} и имеющее меньший вес, чем F. Это противоречит «противному».
W [u, v] = W [u′, v′ ]. Случай равных весов. …

V1

V2

1. Теорема о минимальном ребре. Версия 1.

2
Пусть
{(V1, T1), (V2, T2),…, (Vk, Tk) } – остовный

лес на множестве V (т. е. {V1, V2, …, Vk} есть разбиение V и (∀i ∈1..k: Ti ⊂ E)),
{v, u } – кратчайшее из всех ребер, у которых ровно один конец содержится в V1..
Тогда среди всех остовных деревьев, содержащих все ребра из множества T = Ukj=1 Tj , существует оптимальное остовное дерево, содержащее {v, u }.
Т.е. остов, содержащий T U{{v,u }}, имеет минимальный вес, среди всех остовов, содержащих T.

Замечание о ребрах с равными весами и формулировке теоремы.

,Т1)
v
u
Остальные деревья остовного леса. Узлы V \V1 .

(V, F), где F ⊃ T и {u, v} ∉

F, которое короче всех остальных ОД, содержащих T и ребро {u, v}.
Добавим к F ребро {u, v}. Образуется единственный цикл, не все вершины которого содержаться в V1, например, v ∉ V1.

Теорема о минимальном ребре

u

v

u′

v′

На этом цикле есть ребро {u′, v′ }.
W [u, v] ≤ W [u′, v′ ] .
W [u, v] < W [u′, v′ ] . Тогда, удалив {u′, v′ }, получим другое ОД, содержащее T и ребро {u, v} и имеющее меньший вес, чем F. Это противоречит «противному».
W [u, v] = W [u′, v′ ]. Случай равных весов. …

V1

V \V1

(V. Jarnik, 1930)
Крускал (J.B. Kruskal, Jr., 1956)
Прим (R.C. Prim, 1957)
Дейкстра

(E.W. Dijkstra, 1959)
Мы рассмотрим:
Алгоритм Крускала (Жадный алгоритм)
Алгоритм ЯПД (Ярника-Прима-Дейкстры)
Алгоритм Бoрувки (позже)

— алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

Открыт Джозефом Крускалом в 1956 году.»

Joseph B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48–50

весов.
2. Поочередно выбирать ребра минимального веса, не образующие циклов с

ранее выбранными.

2. Жадный алгоритм построения МОД (Kruskal, 1956)

W[1..12]: 1, 3, 4, 9, 15, 16, 17, 20, 23, 25, 26, 36

W(T)= 1+3+4+9+17+23 = 57

- множество множеств узлов (множество деревьев остовного леса)
begin {алгоритм МОД

}
Vs := { }; T:= { };
for ∀ v ∈ V do добавить {v} к Vs;
Построить очередь Q из всех ребер e ∈ E, упорядочив их по возрастанию весов;
while Card(Vs) > 1 do
begin
Выбрать из Q ребро e = {u,v} с минимальным весом;
Удалить e из Q;
If u и v принадлежат разным подмножествам W1 и W2 из Vs
then
begin Заменить W1 и W2 на W1 ∪ W2 в Vs;
T := T ∪ {e}
end
end {while}
end {алгоритма МОД };

Замечание. Ср. с примером о связности.
Найти W1∈Vs, такое, что u∈W1. То же для v и W2. Это операция НАЙТИ.
Заменить в Vs подмножества W1 и W2 на их объединение W1∪W2 - это операция ОБЪЕДИНИТЬ.

3, 4, 9, 15, 16, 17, 20, 23
Сложность (быстрый поиск

– медленное объединение)
~ m log m + n2

m) при соответствующей реализации набора непересекающихся подмножеств Vs.
Сортировка O(m

log m). Очередь с приоритетами – пирамида → O(k log m). В худшем случае O(m log m).

Базовые операции с набором непересекающихся подмножеств:
принадлежность заданной вершины к одному из подмножеств;
объединить подмножества.
(См. следующую лекцию)

Жадный алгоритм построения МОД (Kruskal, 1956)

Prim, Dijkstra; алгоритм "ближайшего соседа" )






















Жадный алгоритм
(на каждом шаге

дерево растет за счет слияния поддеревьев)

Алгоритм ЯПД
(выбор ближайшей вершины к дереву, на каждом шаге дерево вырастает на одну ветку)

из теоремы, при этом (V1, T1) – дерево, а остальные (Vi, Ti) – изолированные вершины, т.е. Vi = {vj(i)} и Ti = ∅.
Предполагаемая сложность: пусть G – полный граф, тогда на i-ом шаге при выборе «ближайшей» для всех i вершин текущего дерева необходимо просмотреть все остальные (n – i) изолированные вершины, т.е. всего i (n – i) вариантов. Суммарно по всем шагам получим

Алгоритм Ярника-Прима-Дейкстры

Можно улучшить алгоритм до O(n2).

выбор ближайшей вершины, но требует коррекции на каждом шаге.
Пусть Near[1..n]

- массив вершин, Near [v] – вершина дереваT = (Vt, Et), ближайшая к вершине v, еще не включенной в T.
Тогда на i-ом шаге находим ближайшую к дереву вершину за (n – i) сравнений. Коррекция оставшихся Near [*] требует (n – i – 1) действий, т.е. всего на i-ом шаге не более 2(n – i), а суммарно по всем шагам будет O(n2).

Дерево
T = (Vt, Et)

V \ Vt

графа G=(V,E), а D [1..n,1..n] – матрица весов
Выход: множества Vt

- вершин, Et - ветвей МОД, Wt - общий вес МОД
Рабочие: Near[1..n] - массив вершин

begin {алгоритм МОД }
{выбор произвольной вершины v0}
Vt := {v0}; Et := { } ; Wt := 0;
for ∀ v ∈(V \ Vt) do Near[v] := v0; {инициализация Near[*] }
while Card(Vt) < n do
begin
{ф1:} v:=вершина из V\Vt с минимальным значением D[v,Near[v]];
Vt := Vt +{v}; Et := Et + { {v,Near[v]} } ; Wt := Wt + D [v,Near[v]];
{коррекция массива Near[*] после включения v в T : }
for ∀ x ∈ (V \ Vt) do
if D [x,Near[x]] > D [x,v] then Near[x] := v;
end {while}
end {алгоритма МОД };

Алгоритм Ярника-Прима-Дейкстры

∀ x ∈(V \ Vt) do
if D [x,Near[x]]

min then
begin
min := D [x,Near[x]] ;
v := x
end;
{Можно наряду с Near[*] использовать рабочий массив расстояний Dist[x] = D [x,Near[x]] }

Алгоритм Ярника-Прима-Дейкстры

23+1+4+9+3+17 = 57

n(n − 1)/2.
Алгоритм ЯПД – асимптотически оптимальный.
Действительно, симметричная матрица весов

содержит n(n − 1)/2 элементов. В том числе и вес минимального ребра.
Сопоставим задачу МОД с задачей нахождения минимума из n(n − 1)/2 элементов, которая решается за n(n − 1)/2 шагов и не менее.
Пусть для заданной матрицы решили задачу МОД.
Из остовного дерева, содержащего (n − 1) ребро, за (n − 1) шаг извлекаем минимальный элемент матрицы.
Если задача МОД решается за менее, чем n(n − 1)/2 − (n − 1) шагов, то и задачу нахождения минимума из n(n − 1)/2 элементов можно решить за менее, чем n(n − 1)/2 шагов, что неверно.
Итак, нижняя граница задачи МОД: O(n2).

4. Нижняя граница задачи нахождения МОД

остовное дерево - (n – 1) ребер
OutA: число (минимум из

n(n−1)/2 чисел)

POut(A,B)
Минимум из
n-1 ребер

Алгоритм B
МОД

Нижняя граница задачи нахождения МОД

массив расстояний Dist[x] = D [x,Near[x]]. Реализуем из данных

(x, Near[x], Dist[x]) очередь с приоритетами по ключу Dist[x].
Минимальный элемент извлекается (с восстановлением пирамиды) за O (log n) действий. При помещении вершины v в остовное дерево производим коррекцию данных о вершинах, смежных с v и находящихся в очереди. Коррекция каждой такой вершины x (ребра {v, x}) требует O (log n) действий, но при этом такое ребро «возникает» и «исчезает» лишь один раз за все время. Т.о. суммарно требуется O ((n+m) log n) операций, или, что то же O (m log n).
Ср. с O (n2) (например, при m =O (n))

Реализация алгоритма Ярника-Прима-Дейкстры
для разреженных графов

для «плотных» графов (m =O(n))
Для разреженных графов (m = O(n))

= 9; m = 20)
Упрощенное представление

= 9; m = 20) 2
После двух шагов
Текущее

МОД: {a, i, c}

После четырех шагов
Текущее МОД: {a, i, c, b, h}

= 9; m = 20) 3
После четырех шагов
Текущее

МОД: {a, i, c, b, h}

После шести шагов
Текущее МОД: {a, i, c, b, h, g, e}

= 9; m = 20) 4
После восьми шагов
Результат

- МОД:
{a, i, c, b, h, g, e, f, d}
W = 1+2+4+8+7+5+6+14 = 47

После шести шагов
Текущее МОД: {a, i, c, b, h, g, e}

– вариант для разреженных графов

= 9; m = 20) 1
(x, Near[x], Dist[x])
Dist[x]

= D [x,Near[x]].

(x, Dist[x])

(b,4)

(c,2)

(d,15)

(e,13)

(f,12)

(g,10)

(h,11)

(i,1)

(b,4)

(c,2)

(d,15)

(e,13)

(f,12)

(g,10)

(h,11)

(i,1)

= 9; m = 20) 2
(c,2)
(f,12)
(h,11)
(i,1)
(e,13)
(b,4)
(d,15)
(g,10)
(f,12)
(h,8)
(d,15)
(g,9)

(e,13)
(c,2)
(b,4)
(f,12)
(g,9)
(d,15)
(h,8)
(e,13)
(c,2)
(b,4)
Шаг 1
ТМОД =

{a, i}

= 9; m = 20) 3
(f,12)
(d,14)
(h,8)
(e,13)
(g,9)
(f,12)
(g,9)
(d,15)
(h,8)
(e,13)
(c,2)
(b,4)

(b,4)
Шаг 2
ТМОД =

{a, i, c}

= 9; m = 20) 4
(f,12)
(d,14)
(h,8)
(e,13)
(g,9)
(b,4)

(f,12)
(e,13)
(g,9)
(d,14)
(h,8)
Шаг 3
ТМОД =

{a, i, c, b}

= 9; m = 20) 5
(e,13)
(f,12)
(d,14)
(g,7)
Шаг 4
ТМОД =

{a, i, c, b, h}

(f,12)

(e,13)

(g,9)

(d,14)

(h,8)

= 9; m = 20) 6
(e,5)
(d,14)
(f,6)
Шаг 5
ТМОД =

{a, i, c, b, h, g}

(e,13)

(f,12)

(d,14)

(g,7)

(f,6)

(d,14)

(e,5)

= 9; m = 20) 7
(d,14)
(f,6)
Шаг 6
ТМОД =

{a, i, c, b, h, g, e}

(f,6)

(d,14)

(e,5)

= 9; m = 20) 8
(d,14)
Шаг 7
ТМОД =

{a, i, c, b, h, g, e}

(d,14)

(f,6)

Шаг 8

ТМОД = {a, i, c, b, h, g, e, f, d}

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ

ЛЕКЦИИ