|
|
Алгоритмические задачи на графах
, а w - предок v в глубинном остовном дереве (V, T Следствие леммы 5.4: v - точка сочленения ?? уесть сын s, для которого ВЕРХ ?
N U M Из определения ВЕРХ следует, что) ВЕРХ = min{{NUM[v]} ? ВЕРХ сын v} ? {NUM[w]| (v, w) ? обратное ребро}}.
Следующий алгоритм выделения двусвязных компонент, предложенный Хопкрофтом, основан на поиске в глубину, в процессе которого все рассматриваемые ребра попадают (по одному разув стеки для каждой вершины v вычисляется значение функции ВЕРХ (по той же схеме, что и при поиске мостов. При обнаружении точки сочленения v все ребра, помещенные в S после перехода к ее сыну w, удовлетворяющему условию из п. (2) леммы 5.4, составляют очередную двусвязную компоненту C
i
. Они выталкиваются из S и помещаются в Алгоритм ДВУСВЯЗ
Вход: связный неориентированный граф G = (V, E), заданный посредством списков смежности, вершина v
0
? Выход списки ребер двусвязных компонент G.
1. NOMER := 0; i := 0; СоздатьСтек(S); T := ?;
2. FOR EACH v ? V DO {NUM[v] := 0; отметить v как "новую. FOR EACH (v, w) ? E DO mark(v.w) := 0; /* (v, w) не помещалось в S
4. ПОИСКБ(v
0
)
34
Procedure ПОИСКБ(v) 1. NOMER := NOMER + 1; NUM[v] := NOMER; ВЕРХ := NUM[v]; 2. Пометить v как "старую. FOR EACH w ? L v DO 4. { IF mark(v, w) = 0 THEN ВТОЛК(S, (v, w)); mark(v, w) := 1 END-IF; 5. IF w - "новая" THEN /* (v, w) прямое ребро := T ? (v, ОТЕЦ := v; 8. ПОИСКБ[w]; 9. IF ВЕРХ ? NUM[v] THEN /* v -точка сочленения Очередная компонента вытолкнуть из S все ребра до (v, w) включительно := i + 1; C i = ?; 11. DO {(x, y) := ВЕРХ C i := C i ? {(x, y)}; ВЫТОЛК(S)} 12. UNTIL (x, y) = (v, ВЕРХ := ВЕРХ, ВЕРХ /* (v, w) - обратное ребро ОТЕЦ 6= w ВЕРХ := ВЕРХ, NUM[w]} Теорема 5.4. Алгоритм ДВУСВЯЗ правильно находит двусвязные компоненты графа G за время Доказательство. Вначале заметим, что алгоритм для каждой вершины v ? V вычисляет значение функции ВЕРХ в соответствии с определением (*). Действительно, в стр. 1 оно получает значение NUM[v], в стр для него выбирается минимум из текущего значения и значения ВЕРХ для каждого сына w вершины v, а в стр. 20 учитывается NUM[w] для обратных ребер (v, w). Таким образом, тест в стр. 9 верно идентифицирует точки сочленения. Докажем теперь индукцией по числу k двусвязных компонент графа G, что алгоритм правильно выдает двусвязные компоненты. Базис. При k = 1 граф G является двусвязным. Точек сочленения в нем нет. Поэтому вершина v 0 корень остовного дерева имеет в нем лишь одного сына. Пусть это Тогда первым в стек помещается ребро (v 0 , и вызывается ПОИСКБ[v 1 ] . Этот вызов возвращает ВЕРХ = так как среди потомков в дереве есть вершины, связанные ребрами с v 0 . Затем в стр. 9 выясняется, что ВЕРХ = 1 ? N U M [v 0 ] = 1 , и из стека выталкиваются все ребра G, поскольку ни одно из них до этого не выталкивалось. Шаг индукции. Предположим, что алгоритм правильно выдает двусвязные компоненты для всех графов сих числом k. Рассмотрим его работу на графе G состоящем из (k + ой компоненты. Пусть v это первая вершина, для которой в процессе работы будет выполнено условие в стр. 9, те. первая выявленная точка сочленения и пусть w это тот ее сын, для котрого оно выполнилось. Так как после помещения в стек S ребра (v, w) ни одно ребро из него не выталкивалось, тов нем находятся все ребра графа, соединяющие между собой вершины, достижимые из w, а также ребра, соединяющие эти вершины с v. Других ребер там нет, так у вершин, достижимых из w, нет обратных ребер, ведущих "выше. Таким образом, в цикле в стр. 11,12 из S будут вытолкнуты все ребра компоненты двусвязности C 1 , содержащей ребро (v, w). Далее алгоритм будет работать на G также, как он работал бы на графе G 0 , полученном из G после удаления компоненты только номера вершин будут далее в G больше номеров для на число вершин в C) . Так как содержит k компонент, то по предположению индукции все его компоненты будут выданы верно. Следовательно, и все компоненты G будут выданы верно. Для оценки времени заметим, что алгоритм ДВУСВЯЗ основан на обходе в глубину, дополненном вычислением функции ВЕРХ для всех вершин и операциями со стеком S. Число операций взятия минимума при вычислении ВЕРХ не превосходит числа ребер, инцидентных. Каждое ребро графа G вталкивается в S и выталкивается из него по одному разу. Кроме того, так как G связный, то |V | ? |E| +1. Отсюда выводим, что время работы алгоритма ДВУ- СВЯЗ ограничено Пример 11. Применим алгоритм ДВУСВЯЗ к графу из примера 9, изображенному на рис. 15. Еще раз напомним его представление в виде списков смежности 6, 2 L 7 : 6, 8 L 2 : 1, 9, 10, 3 L 8 : 6, 7 L 3 : 2, 5, 4 L 9 : 2, 10, 11 L 4 : 3, 5 L 10 : 2, 9, 11 L 5 : 2, 3, 4 L 11 : 9, 10 L 6 : 1, 7, В процессе работы алгоритма ДВУСВЯЗ для всех вершин будут определены те же номера и значения функции ВЕРХ, что ив примере 9: V : 1 2 3 4 5 6 7 8 9 10 11 N U M : 1 5 9 11 10 2 3 4 6 ВЕРХ : 1 5 5 9 5 2 2 2 5 5 При этом при возврате из ПОИСКБ(7) в ПОИСКБ(6) в стр. 9 будет выполнено условие ВЕРХ[7] ? NUM[6], а стек будет иметь вид S = (1, 6)(6, 7)(7, 8)(6, 8) (дно стека - слева, а верх стека - справа. В стр. 11, 12 в первую компоненту из S будут перемещены ребра до (6, 7) включительно, те. C 1 = {(6, 7), (7, 8), (6, Затем завершится вызов ПОИСКБ(6) и будет обнаружено, что ВЕРХ ? NUM[1], после чего в попадет ребро (1, 6), а стек S опустошится. Далее последуют вызовы ПОИСКБ(2) и ПОИСКБ(9). После завершения второго из них S = (1, 2)(2, 9)(9, 10)(10, 2)(10, 11)(11, 9) ив стр. 9 обнаружится, что ВЕРХ ? В результате сформируется компонента C 3 = {(2, 9)(9, 10)(10, 2)(10, 11)(11, 9)} , а в стеке останется ребро (1, 2). Затем последует вызов ПОИСКБ(3), при завершении которого стеки выполняется условие ВЕРХ ? NUM[2]. Поэтому в стр. сформируется компонента C 4 = {(2, 3)(3, 5)(5, 2)(5, 4)(4, 3)} , а в S останется ребро (1, 2). После завершения вызова ПОИСКБ(2) выполнено условие ВЕРХ ? NUM[1] и создается последняя компонента C 5 = {(1, 2)} 5.4 Компоненты сильной связности и базы ориентированного графа Понятие сильной связности для ориентированных графов соответствует отношению взаимной достижимости вершин. Определение 18. Сильно связные компоненты ориентированных графов. Ориентированный граф G = (V, E) называется сильно связным, если для любой пары его вершин v ив имеется путь изв и путь изв. Сильно связной компонентой называется максимальный сильно связный подграф графа G. 36 Определить всесильно связные компоненты можно, используя вариант алгоритма поискав глубину ПОГ+пост, в котором в процедуре ПОИСК+пост(v) вершина v получает номер перед выходом из процедуры (те. операторы строки 6 стоят после строки 12). procedure ПОИСК+пост(v): 5. пометить v как "старую. FOR EACH w ? L v DO 7. IF вершина w "новая. THEN 9. { T := T ? {(v, w)}; 10. ПОИСК+пост(w) 11. }; 12. NUM[v] = NOMER; NOMER = NOMER + Алгоритм ПОГ+пост вызывается на первом этапе следующего алгоритма ССК, возвращающего всесильно связные компоненты исходного графа. Этот алгоритм был предложен Косерейю (R. Kosaraju) в 1978 г. Алгоритм ССК: Вход: ориентированный граф G = (V, E), заданный посредством списков смежности L v , v Выход списки вершин сильно связных компонент G. 1. Выполнить ПОГ +пост на G и для каждой вершины v определить ее номер NUM[v]; 2. Построить граф G 0 = (V, E 0 ) , "перевернув"стрелки: E 0 = {(v, w)|(w, v) ? E}; 3. W := V ; 4. WHILE W 6= ? DO 5. { выбрать w ? W с максимальным номером NUM[w]; 6. выполнить ПОИСК) на и выдать пройденные вершины V w в качестве очередной компоненты Теорема 5.5. Алгоритм ССК корректно выдает всесильно связные компоненты ориентированного графа G = (V, E) за время O(|V | + Доказательство. Доказательство правильности алгоритма ССК оставляем в качестве задачи (см. задачу 5.10). Для оценки времени его работы заметим, что пункты 1 - 3, очевидно, выполняются за время O(|V | + |E|). В строках 6 и 7 цикла WHILE каждое ребро графа рассматривается не более двух раза каждая вершина проходится (нумеруется в ПОИСК) и удаляется 1 раз. Поэтому общее время выполнения этих строк также O(|V |+|E|). Что касается определения очередной вершины с максимальным номером в строке 5, то для его эффективного выполнения достаточно при присвоении номера очередной вершине в алгоритме ПОГ +пост делать ссылку на вершину, получившую предыдущий номер. Таким образом по завершении этого алгоритма образуется список вершин в порядке убывания их номеров, который можно использовать для выбора очередной вершины в строке 5. При этом общее время выполнения этой строки не превысит O(|V Определим для ориентированного графа G = (V, E) его граф компонент G K = (V K , следующим образом V K = {C | C компонента сильной связности G}, E K = {(C 1 , C 2 ) существует такое ребро (v, u) ? E, что v ? C 1 , u ? Граф называют конденсацией графа G. Используя алгоритм ССК, конденсацию графа G можно построить за время O(|V | + |E|) ( задача Из определения непосредственно следует, что в графе нет циклов, а отношение достижимости на нем является отношением частичного порядка ? K : оно рефлексивно, антисимметрично и транзитивно. Назовем сильно связную компоненту K графа G минимальной, если она минимальна относительно порядка ?K , те. недостижима ни из какой другой компоненты G. Из этого определения следует, что K минимальна тогда и только тогда, когда в графе нет ребер, входящих в Минимальные компоненты в графе G K , очевидно, можно найти по его спискам смежности за время O(|V K | + Во многих приложениях ориентированный граф представляет собой сеть распространения некоторого ресурса продукта, товара, информации и т.п. В таких случаях естественно возникает задача поиска минимального числа таких точек (вершин, из которых этот ресурс может быть доставлен в любую точку сети. Определение 19. Пусть G = (V, E) ориентированный граф. Подмножество вершин ? называется порождающим, если из вершин W можно достичь любую вершину графа. Подмножество вершин W ? V называется базой графа, если оно является порождающим, но никакое его собственное подмножество порождающим не является. Следующая теорема связывает базы графа сего минимальными компонентами и позволяет эффективно находить все базы графа. Теорема 5.6. Пусть G = (V, E) ориентированный граф. Подмножество вершин W ? является базой G тогда и только тогда, когда оно содержит по одной вершине из каждой минимальной компоненты сильной связности G и не содержит никаких других вершин. Доказательство. Заметим вначале, что каждая вершина графа достижима из вершины, принадлежащей некоторой минимальной компоненте. Поэтому множество вершин W , содержащих по одной вершине из каждой минимальной компоненты, является порождающим а при удалении из него любой вершины перестает быть таковым, так как вершины из соответствующей минимальной компоненты становятся недостижимы. Поэтому W является базой. Обратно, если W является базой, то оно обязано включать хотя бы по одной вершине из каждой минимальной компоненты, иначе вершины такой минимальной компоненты окажутся недоступны. Никаких других вершин W содержать не может, так как каждая из них достижима из уже включенных вершин. Из этой теоремы вытекает следующая процедура построения одной или перечисления всех баз графа G. 1) Используя алгоритм ССК, найти все компоненты сильной связности G. 2) Построить конденсацию и выделить среди ее вершин все минимальные компоненты G. 3) Породить одну или все базы графа, выбирая по одной вершине из каждой минимальной компоненты. Теорема 5.7. Существует алгоритм построения базы ориентированного графа G = (V, за время O(|V | + |E|). Все базы G можно перечислить за время O(k|V | + |E|)), где k это число различных баз G. 38 Пример 12. Определим все базы ориентированного графа G, показанного на рис. 18. Будем считать, что в списках смежности вершины идут в алфавитном порядке (например, L
e
=
d, g, h
).
-
-
-
Q
Q
Q
Q
Q
Q
s
-
6
Z
Z
Z
Z
Z
}
-
+
+
-
6
H
H
H
Y
H
H
Y
r
n l
a b
c d
e f
g h
k Рис. 18: Граф Вначале ищем компоненты сильной связности с помощью алгоритма ССК. На его первом этапе после выполнения ПОГ+пост получим следующую нумерацию вершин :
a b
c d
e f
g h
k l
m n
r
N U M :
4 5
1 12 10 11 7
9 6
2 8
3 Затем строим граф G
0
= (V, см. рис. 19), обратив направления ребер в G
Q
Q
Q
Q
Q
Q
k
-
?
Z
Z
Z
Z
Z
Z
3
3
*
-
?
H
H
H
Y
H
H
H
j
r
n l
a b
c d
e f
g h
k Рис. 19: Граф G
0
= (V, На этом графе последовательно запускаем ПОИСК на вершинах с максимальными номерами, удаляя после каждого такого вызова достигнутые в нем вершины. Получаем следующие семь компонент сильной связности G:
K
1
= {r}, K
2
= {d, e, f, g}, K
3
= {h, m}, K
4
= {k}, K
5
= {b}, K
6
= {a, n, l}, K
7
= На втором этапе строим конденсацию на этих компонентах.
K
6
K
5
K
2
K
7
K
3
K
1
K
4
-
-
?
?
@
@
@
@
R
@
@
@
@
R
P
P
P
P
P
P
P
P
P
q
Рис. 20: Граф конденсации на компонентах С помощью этого графа определяем минимальные компоненты {r}, K
2
= {d, e, f, и K
5
= Наконец перечисляем все четыре базы G:
B
1
= {r, d, b}
, B
2
= {r, e, b}
, B
3
= {r, f, и B
4
= {r, g, b}
39
5.5 Задачи Задача 5.1. Пусть неориентированный граф G = (V, E) имеет k компонент связности. Доказать, что тогда ? (|V | ? k)(|V | ? k + Задача 5.2. Модифицировать алгоритм ПОГ (ПОШ) так, чтобы он определял компоненты связности графа G (например, приписывал каждой вершине v номер ее компоненты связности КОМП[v] Задача 5.3. Доказать, что построенное ПОГ множество ребер Т образует остовной лес Задача 5.4. Пусть в результате работы ПОГ ребро (v, w) оказалось обратным, те. оно принадлежит E\T . Тогда либо v предок w, либо w предок v в построенном ПОГ остовном лесу. Задача 5.5. Рассмотрите модификацию алгоритма ПОГ (ПОШ) для ориентированного графа G = (V, E), в которой L v = {w| (v, w) ? E} . Покажите, что полученный алгоритм нумерует все вершины и строит остовной лес. Задача 5.6. Пусть в результате алгоритма ПОГ на ориентированном графе G ребро (v, оказалось поперечным, теине являются потомками друг друга в T . Доказать, что тогда NUM[v] > Задача 5.7. Пусть F - это лес, построенный алгоритмом ПОГ для ориентированного графа = (V, E) . Доказать, что G - ациклический граф ?? (E \ F ) не содержит дуги (v, w), в которой вершина w является предком вершины v в F Задача 5.8. Пусть в неориентированном графе G = (V, E) длины всех ребер одинаковы и равны d. Модифицируйте алгоритм ПОШ так, чтобы он для заданной вершины v ? определил кратчайшие пути и расстояния до остальных вершин графа. Задача 5.9. Топологическая сортировка. Для ориентированного ациклического графа G = (V, E) назовем линейный порядок < на множестве вершин V топологическим, если из v < w следует, что в G нет пути изв (вообще говоря, этот порядок не единственный. Доказать, что ПОГ+пост нумерует вершины G в порядке, обратном топологическому. Задача 5.10. Доказать, что алгоритм ССК корректно выдает всесильно связные компоненты Задача 5.11. Предположим, что в алгоритме ССК из предыдущей задаче в цикле 4-7 вместо графа G 0 = (V, с перевернутыми стрелками используется исходный графа вершины рассматриваются в порядке увеличения их номеров. Будет ли такой алгоритм работать правильно? Задача 5.12. Предложите алгоритм, который по ориентированному графу G = (V, E) строит его граф сильно связных компонент (конденсацию) за время O(|V | + Задача 5.13. Определить для приведенного на рис. 21 ориентированного графа G его компоненты сильной связности, конденсацию и все базы графа Задача 5.14. Докажите, что связный неориентированный граф является деревом тогда и только тогда, когда каждое его ребро является мостом - - - - 6 Z Z Z Z Z } ? + H H H Y - - n l a b c d e f g h Рис. 21: Граф Задача 5.15. Докажите, что двусвязная компонента - это максимальный набор ребер, любые два ребра которого принадлежат общему простому циклу. Задача 5.16. Найти все мосты и двусвязные компоненты заданного неориентированного графа G = (V, E) V = {v 1 , v 2 , v 3 , v 4 , v 6 , v 7 , v 8 , v 9 , v 10 , v 11 }, E = {(v 1 , v 2 ), (v 1 , v 4 ), (v 1 , v 8 ), (v 7 , v 8 ), (v 2 , v 9 ), (v 9 , v 11 ), (v 4 , v 2 ), (v 3 , v 8 ), (v 6 , v 3 ), (v 3 , v 7 ), (v 6 , v 7 ), (v 10 , v 9 ), (v 10 , v 11 )} 6 Задачи о путях на графе Задачи о достижимости в графе одних вершин из других и о кратчайших путях между вершинами в графах с заданными длинами (весами) ребер занимают важное место в многочисленных приложениях теори графов. В этом разделе мы вначале рассмотрим алгоритмы для проверки достижимости и вычисления длин кратчайших путей между всеми парами вершина затем алгоритмы построения дерева кратчайших путей из заданной вершины до достижимых из нее вершин графа Достижимость и транзитивное замыкание графа Определение 20. Пусть G = (V, E) ориентированный граф. Граф достижимости G ? = (V, для G имеет тоже множество вершин V и следующее множество ребер E ? = {(u, v) в графе G вершина v достижима из вершины Иначе говоря, отношение является рефлексивными транзитивным замыканием отношения Пример 13. Рассмотрим следующий граф G: t t t t t t 1 2 3 4 5 Рис. 22: Граф Тогда можно проверить, что граф достижимости для G выглядит так (ребра-петли при каждой из вершин не показаны t
t t
t t
t
1 2
3 4
5 Рис. 23: Граф Каким образом по графу G можно построить граф G
?
? Один способ заключается в том,
чтобы для каждой вершины графа G определить множество достижимых из нее вершин, последовательно добавляя в него вершины, достижимые из нее путями длины 0, 1, 2 и т.д. Для этого можно использовать алгоритм поискав ширину.
Другой (алгебраический) способ основан на использовании матрицы смежности A
G
графа
G
и булевых операций. Пусть множество вершин V = {v
1
, . . . , v n
}
. Напомним, что матрица смежности A
G
это булева матрица размера n Ч n такая, что a
ij
=
1,
(v i
, v j
) ? в противном случае
Обозначим через E
|
|
|
Скачать 1.07 Mb.