АЛГОРИТМЫ НА ГРАФАХ

1. МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО

Определение 1. Остовным деревом(покрывающим деревом, остовом, скелетом)

связного неориентированного графа

G=(V,E) называется его подграф, содержащий все

вершины G и являющийся деревом.

Определение 2. Пусть G =(V,E) - граф из определения 1, с: E -->R -

функция стоимости, заданная на его ребрах, S=(V,T) -

остовное дерево для G. Стоимость S - это сумма стои-

мостей ребер из T. S назовем минимальным остовным

деревом, если оно имеет наименьшую стоимость срели

всех остовных деревьев G.

ЛЕММА 1. Пусть S=(V,T) - остовное дерево для G. Тогда

(а) для любых двух вершин v1 и v2 из V путь межлу v1 и v2

в S единственный;

(б) если к S добавить любое ребро из E - T, то возникнет

ровно один цикл.

ЛЕММА 2. Пусть {(V₁, T₁), (V₂,T₂),...,(V_k,T_k)} - произвольный

остовной лес для G, k > 1, T= U T_i (1<=i<=k). Пусть e=(v, w) -

ребро наименьшей стоимости в E - T такое, что v из V₁, а w не

из V₁. Тогда существует остовное дерево, содержащее все ребра

из T и e, стоимость которого не больше стоимости любого остовного

дерева для G, содержащего Т.

"Жадный" алгоритм построения минимального остовного дерева

(алгоритм Крускала, 1956)

Вход: G=(V,E)- связный неориентированный граф,

c(e) - функция стоимости ребер.

Выход: T - множество ребер минимального остовного дерева.

Структуры данных: Q - очередь с приоритетами для ребер,

VS - набор непересекающихся подмножеств вершин G, элементы VS -

множества вершин остовных деревьев в текущем остовном лесу.

АЛГОРИТМ МИНОД

begin

1. T := {}; VS := {};

2. создать очередь с приоритетами Q из всех ребер из E;

3. for v из V do добавить {v} к VS;

4. while |VS| > 1 do begin

5. (v,w) := MIN(Q); УДАЛИТЬ(Q, (v,w));

6. W1 := НАЙТИ(v); W2:= НАЙТИ(w);

7. if W1 <> W2 then

8. begin ОБЪЕДИНИТЬ(W1, W2, W1); добавить (v, w) к T end

end end

ТЕОРЕМА 1. Алгоритм МИНОД строит минимальное остовное дерево

для связного графа G=(V,E). Если в цикле в строках 4 - 8 рас-

сматривается d ребер, то затрачивается время O(d*log₂e), где

e = |E|. В худшем случае алгоритм МИНОД занимает время O(e*log₂e).

2. АЛГОРИТМЫ ОБХОДА ГРАФОВ

2.1. Поиск в глубину на неориентированном графе

Вход: G=(V, E) - неорграф, представленный списками смежностей

L[v] для v из V.

Выход: NUM[v] - массив с номерами вершин и разбиение E на два

множеста: древесных ребер Т и обратных ребер B = E - T.

АЛГОРИТМ ПОГ

begin

1. T := {}; NOMER := 1;

2. for v из V do NUM[v] := 0;

3. for v из V do пометить v как "новую";

4. while существует "новая" v в V

do ПОИСК(v)

end;

procedure ПОИСК(v):

begin

5. пометить v как "старую";

6. NUM[v] := NOMER; NOMER := NOMER + 1;

7. for w из L[v] do

8. if вершина w "новая" then

9. begin добавить (v, w) к T;

10. ПОИСК(w)

end end

ТЕОРЕМА 2. Алгоритм ПОГ обходит (нумерует) все вершины графа

G=(V,E) за время O(MAX(|V|, |E|)).

2.2. Поиск в ширину на неориентированном графе

Алгоритм поиска в ширину ПОШ отличается от алгоритма ПОГ только

процедурой ПОИСК.

procedure ПОИСКШ(v):

begin

5. создать пустую очередь Q;

6. ДОБАВИТЬ(Q, v); пометить v как "старую";

7. while не пуста Q do

8. begin w := НАЧАЛО(Q);

9. NUM[w] := NOMER; NOMER := NOMER + 1;

10. for u из L[w] do

11. if u - "новая" вершина then

12. begin ДОБАВИТЬ(Q, u); пометить u как "старую" end

end end

ТЕОРЕМА 3. Алгоритм ПОШ обходит (нумерует) все вершины графа

G=(V,E) за время O(MAX(|V|, |E|)).

ЗАДАЧИ

1. Модифицировать алгоритм ПОГ (ПОШ) так, чтобы он определял

компоненты связности графа G (например, приписывал каждой вер-

шине v номер ее компоненты связности КОМП[v] ).

2. Доказать, что построенное ПОГ множество ребер Т образует

остовной лес G.

3. Пусть в результате работы ПОГ ребро (v,w) оказалось обратным,

т.е. оно принадлежит E - T. Тогда либо v - предок w, либо w -

предок v в постоенном ПОГ остовном лесу.

4. Рассмотритете модификацию алгоритма ПОГ (ПОШ) для ориентирован-

ного графа G=(V, E), в которой L[v] = {w |(v, w) из E}. Покажите,

что полученный алгоритм нумерует все вершины и строит остовной лес.

5. Пусть в результате алгоритма ПОГ на ориентированном графе G ребро

(v, w) оказалось поперечным, т.е. v и w не являются потомками друг

друга в Т. Доказать, что тогда NUM[v] > NUM[w].

Двусвязные компоненты

Определение. Неориентированный граф G =(V,E) называется двусвязным, если для любых трех его попарно различных вершин w, v и a существует путь между w и v, не проходящий через a.

Вершина v называется точкой сочленения (точка раздела) графа G, если для некоторой пары различных вершин x и y (не совпадающих с v) всякий путь между x и y проходит через v.

Следствие. Связный граф является двусвязным тогда и только тогда, когда в нем нет точек сочленения.

Определение. Максимальный двусвязный подграф графа G называется его двусвязной компонентой.

Задача 6. Докажите, что двусвязная компонента – это максимальный набор ребер, любые два ребра которого принадлежат общему простому циклу.

Лемма 1. Пусть G_i =(V_i,E_i) (i=1,...,k) – двусвязные компоненты графа G =(V,E). Тогда

1) граф G_i двусвязен (i=1,...,k):

2) для любой пары i ¹ j |V_i Ç V_j| = 1;

3) a – точка сочленения G ó для некоторых i и j aÎ V_i Ç V_j.

Лемма 2. Пусть G = (V,E) – связный неориентированный граф, а

S = (V, T) – глубинное остовное дерево. Вершина a является точкой сочленения G ó

1) a – корень дерева S и он имеет более одного сына

или

2) a – не корень и у него есть сын s такой, что между ним и его потомками и предками a нет обратных ребер.

Пусть NUM[v] – номер, присвоенный v алгоритмом ПОГ. Определим функцию НИЖ[v] = min {{NUM[v]}È {NUM[w] | существует такое обратное ребро (x,w), что x – потомок v, а w – предок v в глубинном остовном дереве (V,T)}}.

Следствие леммы 2: v – точка сочленения ó у v есть сын s, для которого НИЖ[s] ³ NUM[v].

Из определения НИЖ следует, что

НИЖ[v]= min{{NUM[v]} È {НИЖ[s] | s – сын v}È {NUM[w] |(v,w) – обратное ребро}}.

Алгоритм ДВУСВЯЗ

Вход: связный неориентированный граф G=(V,E)

Выход: списки ребер двусвязных компонент G

Begin i := 0; СоздатьСтек(S); T :={};

For v Î V do {NUM[v}:=0; отметить v как «новую»}

ПОИСКБ(v0)

End

Procedure ПОИСКБ(v)

Begin i := i+1; NUM[v] := i; НИЖ[v]:=i;

Пометить v как «старый»;

For w Î L[v] do

If (v,w) нет в S then ВТОЛК(S, (v,w));

If w – “новый” then

{ T := T È (v,w) /* прямое ребро

ОТЕЦ[w] := v;

ПОИСКБ[w];

If НИЖ[w] >= NUM[v] then /* v –точка сочленения

Вытолкнуть из S все ребра, включая (v,w)

End_if

НИЖ[v]:= min{НИЖ[v], НИЖ[w]}

}

else /* (v,w) – обратное ребро

if ОТЕЦ[v] ¹ w then

НИЖ[v]:= min{ НИЖ[v],NUM[w]}

End

Теорема. Алгоритм ДВУСВЯЗ правильно находит двусвязные компоненты графа G за время O(|E|).

Задача 7. Ребро называется мостом, если при его удалении граф перестает быть связным.

А) Докажите, что ребро графа G является мостом тогда и только тогда, когда оно не входит ни в какой простой цикл.

Б) Постройте алгоритм нахождения всех мостов графа за время

O(|E|).