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_к концом.

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

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

Рассмотрим метод поиска в глубину в неориентированном графе 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. Выделить компоненты сильной связности орграфа, используя алгоритм поиска в ширину (в орграфе поиск необходимо вести как в прямом, так и в обратном направлении).

2. Независимые множества вершин и родственные задачи

1. Независимые множества

Во многих прикладных задачах требуется найти в конечном множестве объектов максимальную систему объектов, попарно не связанных друг с другом, или же выбрать минимальную систему объектов, связанных со всеми другими. Формулировки подобных задач на языке теории графов приводят к понятиям независимости и покрытия.

Множество вершин U графа G = (V,X) называется независимым (внутренне устойчивым), если никакие две вершины из этого множества не смежны. Другими словами, если U V и U независимо в графе G, то порожденный подграф G(U) является пустым. Очевидно, что если при этом U* U, то U* - также независимое множество.

Внутренне устойчивое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества.

Наибольшее по мощности независимое множество называется наибольшим.

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

Число вершин в наибольшем независимом множестве графа G называется числом независимости (или числом внутренней устойчивости) этого графа и обозначается (G).

2

1 3 7

5 4 6

8

Рис. 1.

Например, для графа G, изображенного на рис.1., (G)=4, множества вершин {1,2,3,7}, {1,2,3,8}, {2,3,5,7}, {2,3,5,8} являются наибольшими независимыми, а {4,7} – максимальное независимое множество, не являющееся наибольшим.

Понятие внутренней устойчивости естественным образом переносятся и на случай ориентированного графа.