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

 

Граф G называется деревом, если он является связным и не имеет циклов.

Остовом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Остовное дерево связного нагруженного графа G с минимальной суммой длин содержащихся в нем ребер, будем называть остовом минимального веса или минимальным остовным деревом (МОД).

Рассмотрим граф G = (V,X), где V ={ v₁,…,v_n }.

 

ЗАДАНИЕ 14. Найти минимальный остов графа, используя алгоритм Краскала.

А л г о р и т м К р а с к а л а

 

Данные: матрица весов С(G) графа G.

Результат: матрица весов полученного остова, величина минимального остова.

 

1. Выберем в графе G ребро х минимального веса и построим граф G ₁, присоединяя к пустому графу О_n на множестве вершин V ребро х.

2. Если граф G_к уже построен и k < n -1, то строим граф G_{к +1}, присоединяя к графу G_к ребро y, имеющее минимальный вес среди ребер, не входящих в G_к и не составляющих циклов с ребрами из G_к.

В качестве иллюстрации рассмотрим нагруженный граф, изображенный на рис. 3а). На рис. 3б) представлено МОД данного графа (в скобках указан порядок присоединения ребер к МОД). Длина полученного МОД равна 10.

1 3 5 1 5

1 2 4 4 (1) (2) (4)

(3)

4 5 2 3 3 4 2 3

а) б)

Рис. 3

 

ЗАДАНИЕ 15. Найти минимальный остов графа, используя алгоритм Прима.

 

Алгоритм Прима отличается от алгоритма Краскала только тем, что на каждом этапе строится не просто ациклический граф, а дерево.

 

А л г о р и т м П р и м а

 

Данные: матрица весов С(G) графа G.

Результат: матрица весов полученного остова, величина минимального остова.

1. Выберем в графе G ребро х = { v,w } минимального веса и построим дерево G ₁ = (V ₁, X ₁), полагая V ₁ = { v,w }, X ₁ = { х }.

2. Если дерево G_к уже построено и k < n -1, то среди ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в G_к , выбираем ребро y минимального веса. Строим дерево G_{к +1}, присоединяя к G_к ребро y вместе с его не входящим в G_к концом.

 

Поиск в графах

 

Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа, такой, что каждая вершина графа просматривается только один раз, и переход от одной вершины к другой осуществляется по ребрам графа. Остановимся на двух стандартных методах такого перебора: поиск в глубину и поиск в ширину.

Рассмотрим метод поиска в глубину в неориентированном графе G. Идея этого метода состоит в следующем. Начинаем поиск с некоторой фиксированной вершины v ₀, присвоим ей ПГ-номер: ПГ(v ₀)=1. Затем выбираем произвольную вершину w, смежную с v ₀, присваиваем ей ПГ-номер: ПГ(w)=2, и повторяем процесс уже от вершины w. Предположим, что в результате выполнения нескольких шагов этого процесса мы пришли в вершину v и пусть ПГ(v)=k. Далее действуем в зависимости от ситуации следующим образом:

1) если имеется новая, т.е. еще непросмотренная вершина u, смежная с v, то, присваивая ей ПГ-номер: ПГ(u)=k+1, продолжаем поиск, начиная с вершины u;

2) если же не существует ни одной новой, т.е. непросмотренной вершины u, смежной с v, то считаем, что вершина v просмотрена и возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс поиска дальше.

Пример.

7 1 8

5 6 2 5

9

1 3 8

3 6

7 10

2 9 10

4 4

а) б)

Рис. 4

 

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

Для графа, представленного на рис. 4 а), описанным методом были получены два корневых дерева, изображенных на рис 4б).

Рассмотрим идею поиска в ширину в неориентированном графе. Другое название этого метода – волновой.

Начинается поиск с произвольной вершины v. Ей приписывается номер 0. Вершину v считаем просмотренной и помещаем в очередь. Далее проходим все ребра { v, w }, инцидентные вершине v и ориентируем их из v в w. Всем вершинам w приписываем номер 1, считаем их просмотренными и помещаем в очередь. После этих действий вершина v удаляется из очереди.

Далее выбираем вершину u, которая находится в начале очереди. Пусть ей приписан номер k. Пройдем все ребра, соединяющие вершину u с еще непросмотренными вершинами w. Всем вершинам w присвоим номер k +1, будем считать их просмотренными и поместим в очередь в порядке их просмотра. После этого вершину u удаляем из очереди. Заканчивается поиск в ширину тогда, когда все вершины графа будут просмотрены.

Пример.

7(2)

5(1) 6(2)

 

1(0) 3(1)

2(1) 4(1)

 

Рис. 5

 

На рис 5 в скобках указаны номера вершин графа, которые были ими получены в результате поиска в ширину.

Рассмотренная методика поиска в глубину и в ширину переносится и на ориентированные графы.

Рассмотренные методы поиска в глубину и в ширину могут быть применены для нахождения путей (маршрутов) в орграфах (графах), для выделения компонент связности (компонент сильной связности) графа (орграфа), а также для решения других задач теории графов.

 

ЗАДАНИЕ 16. Выделить компоненты сильной связности орграфа, используя алгоритм поиска в глубину (в орграфе поиск необходимо вести как в прямом, так и в обратном направлении).

ЗАДАНИЕ 17. Выделить компоненты сильной связности орграфа, используя алгоритм поиска в ширину (в орграфе поиск необходимо вести как в прямом, так и в обратном направлении).