Extract-Min за учётное время 0(lgV), а операцию Decrease-Key - за (учётное) время 0(1). (Нас интересует именно суммарное время выполнения последовательности операций, так что амортизированный анализ тут в самый раз.) Поэтому при использовании фибоначчиевых куч для реализации очереди время работы алгоритма Прима составит О (Е + Vlg V).

Упражнения

24.2-1

Для одного и того же графа G алгоритм Крускала может давать разные результаты (если по-разному упорядочить рёбра одинакового веса). Покажите, что для каждого минимального остова Г графа G существует упорядочение рёбер графа G, при котором алгоритм Крускала даст как раз Т.

24.2-2

Граф (V, Е) задан матрицей смежности. Постройте простую реализацию алгоритма Прима, время работы которой есть 0(V2). 24.2-3

Имеется ли выигрыш при переходе от двоичных куч к фибо-наччиевым для разреженного графа G = (V, Е) для которого \Е\ = Q(V)? для плотного графе, где \Е\ = Q(V2)? При каком соотношении между \Е\ и \V\ переход к фибоначчиевым кучам приводит к асимптотческому улучшению эффективности?

24.2-4

Пусть веса рёбер графа G = (V, Е) - целые числа в интервале от 1 до \V\. Какой скорости работы алгоритма Крускала можно добиться? А если веса - целые числа от 1 до W (где W - некоторая константа)?

24.2-5

Пусть веса рёбер графа G = (V, Е) - целые числа в интервале от 1 до \V\. Какой скорости работы алгоритма Прима можно добиться? А если веса - целые числа от 1 до W (где W - некоторая константа)?

24.2-6

Укажите эффективный алгоритм для такой задачи: для данного графа G и весовой функцией w найти наилучшее покрывающее дерево, если критерием «качества» дерева считать не сумму весов, а вес самого тяжёлого ребра.

24.2-7*

Пусть известно, что веса рёбер графа - независимые случайные числа, равномерно распределенные на полуинтервале [0,1). Как это использовать для ускорения работы одного из алгоритмов (Крускала или Прима)?

24.2-8*

Пусть минимальный остов графа G уже построен. Как быстро можно найти новый минимальный остов, если добавить к графу G новую вершину и инцидентные ей рёбра?

Задачи

24-1 Второй по величине остов

Пусть G = (V, Е) - неориентированный связный граф с весовой функцией w : Е -> Ж, и пусть \Е\ \V\ (число рёбер больше минимально возможного). Упорядочим все покрывающие деревья в порядке неубывания весов; нас будет интересовать второе по величине в этом порядке. (Будем считать для простоты, что все деревья в этом списке имеют различные суммы весов.)

a.Пусть Т - минимальное покрывающее дерево графа G. Докажите, что второе по величине дерево получается из Т заменой некоторого ребра (и, v) £ Т на другое ребро (ж, у) Т.

b.Пусть Т - покрывающее дерево графа G. Для любых двух вершин и, v £ V через max[u,v] обозначим ребро максимального веса на единственном пути, соединяющем и и v в Т. Укажите алгоритм с временем работы 0(V2), который который для любого заданного Т находит max[u, v] для всех пар вершин и, v £ V.

c.Укажите эффективный алгоритм поиска второго по величине покрывающего дерева.

24-2 Минимальный остов в разреженном графе

Для очень разреженного связного графа G = (V, Е) время работы 0(Е-\-V\gV) алгоритма Прима (с фибоначчиевыми кучами) можно ещё сократить, если предварительно преобразовать граф G, уменьшив число его вершин. Описанная ниже процедура преобразования MST-Reduce получает на вход граф G с весовой функцией и возвращает «сжатую»версию G графа G, одновременно добавляя рёбра к будущему остову. Эта процедура использует массив orig[u, v]; в начальный момент оггд[и, v] = (и, v).

Идея проста: если для некоторой вершины взять кратчайшее ребро, из неё выходящее, то можно искать минимальный остов среди остовов, включающих это ребро - а эта задача сводится к задаче поиска остова для меньшего графа (с отождествлёнными вершинами). Рёбра, по которым проведена склейка, помещаются в Г, а для каждого ребра (и, v), соединяющего вершины нового графа, хранится w[u, v] - то ребро исходного графа, из которого оно произошло (если таких было несколько, то берётся кратчайшее).

\textsc{MST-Reduce> (G,T)

1{\bf for} $v\in V[G]$

2{\bf do} $mark[v] \leftarrow \textsc{false}$

3\textsc{Make-Set(v)}

4{\bf for} $u\in V[G]$

5{\bf do if} $mark[u] = \textsc{false}$

6{\bf then} выбрать $v\in Adj[u]$ с наименьшим $w[u,v]$

7\textsc{Union(u,v)}

8$T \leftarrow T\cup \{orig[u,v]\}$

9$mark[u] \leftarrow $mark[v] \leftarrow

\textsc{true}$

10$V[G] \leftarrow \{\textsc{Find-Set(v)> : v\in V[G] \}$

11$E[G] \leftarrow \emptyset$

12{\bf for} $(x,y)\in E[G]$

13{\bf do} $u \leftarrow \textsc{Find-Set(x)}$

14$v \leftarrow \textsc{Find-Set(y)}$

15{\bf if} $(u,v)\notin E[G]$

16{\bf then} $E[G] \leftarrow E[G]\cup\{(u,v)\}$

17$orig[u,v] \leftarrow orig[x,y]$

18$w[u,v] \leftarrow w[x,y]$

19{\bf else if} $w[x,y] < w[u,v]$

20{\bf then} $orig[u,v] \leftarrow orig[x,y]$

21$w[u,v] \leftarrow w[x,y]$

22построить списки смежных вершин $Adj$ для $G$

23{\bf return} $G$ и $T$

a.Пусть T - множество рёбер, возвращённое процедурой MST-Reduce, а Г - минимальный остов графа G, возвращённого этой процедурой. Докажите, что Г U {orig[x,y] : (ж, у) £ Г} - минимальный остов графа G.

b.Покажите, что \V[G]\ \V\/2.

c.Покажите, как реализовать процедуру MST-Reduce так, чтобы она исполнялась за время О(Е). (Указание. Используйте несложные структуры данных.)

d.Пусть мы подвергли граф /г-кратной обработке с помощью процедуры MST-Reduce (выход одного шага является входом следующего). Объясните, почему что общее время выполнения всех к итераций составляет О(кЕ).

e.Пусть после к применений процедуры MST-Reduce мы воспользовались алгоритмом Прима для сжатого графа. При этом можно выбрать к так, чтобы общее время работы составило O(ElglgV). Почему? Такой выбор асимптотически минимизирует общее время работы. Почему?

f.При каком соотношении \Е\ и \V\ алгоритм Прима с предварительным сжатием эффективнее алгоритма Прима без такого сжатия?

Замечания

Книга Тарьяна [188] содержит обзор задач, связанных с минимальными покрывающими деревьями, и дальнейшую информацию о них. Историю задачи о минимальном покрывающем дереве описали Грэхем и Хелл [92].

Как указывает Тарьян, впервые алгоритм построения минимального остова появился в статье Борувки (O.Boruvka). Алгоритм Крускала опубликован в его статье 1956 года [131]. Алгоритм, известный как алгоритм Прима, действительно изобретён им и описан в [163], но ранее его нашёл Ярник (V.Jarnik, 1930).