Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[158]

оставшихся вершину г с максимальным значением f[v]. Любая оставшаяся вершина и, из которой достижима г, будет иметь г своим предшественником (ни одна из отброшенных вершин не достижима из и, иначе и г была бы достижима из и и вершина и попала бы в число отброшенных). Таким образом мы найдём вторую сильно связную компоненту - в неё входят те из оставшихся вершин, из которых достижима вершина г (другими словами, те из оставшихся, которые достижимы из г в транспонированном графе).

Теперь понятен смысл строки 3 алгоритма Strongly-Connected-Components: поиск в глубину в транспонированном графе поочерёдно «отслаивает» сильно связные компоненты. Скажем то же самое более формально:

Теорема 23.17

Алгоритм Strongly-Connected-Components правильно находит сильно связные компоненты ориентированного графа. Доказательство.

В строке 3 алгоритма происходит вызов алгоритма DFS на транспонированном графе. Этот алгоритм просматривает вершины в порядке убывания параметра f[v], вычисленного в строке 1. При этом строятся деревья поиска, про которые мы хотим доказать, что они будут сильно связными компонентами.

На каждом шаге цикла рассматривается очередная (в порядке убывания параметра /) вершина v. Вершины уже построенных деревьев поиска в этот момент чёрные, а остальные вершины - белые. (Заметим, что при этом всякая вершина, достижимая в графе GT из чёрной, сама будет чёрной.)

Если очередная вершина и оказывается чёрной, то алгоритм DFS не делает ничего. Если же она белая, то вызов процедуры DFS-Visit(m) в строке 7 алгоритма DFS сделает её и все достижимые из неё в графе GT вершины чёрными. Мы должны показать, что эти вершины образуют сильно связную компоненту.

Если какая-то белая вершина v достижима из и в графе GT, то и будет предшественником v, поскольку и достижима из v в G, никакие чёрные вершины не достижимы из v в G и и имеет максимальное значение параметра / среди всех белых вершин. С другой стороны, если белая вершина v не достижима из и в графе GT, то она не может иметь и своим предшественником. Чёрные вершины также не могут иметь и своим предшественником (их предшественники найдены на предыдущих шагах). Поэтому множество белых вершин, достижимых из и в графе GT, совпадает с множеством вершин, имеющих и своим предшественником, то есть является сильно связной компонентой.

Упражнения

23.5-1

Как может изменится количество сильно связных компонент гра-


фа при добавлении к нему одного ребра? 23.5-2

Применте алгоритм Strongly-Connected-Components к графу рис. 23.6. Найдите времена завершения, вычисляемые в строке 1, и лес, создаваемый строкой 7. Считайте, что цикл в строках 5-7 алгоритма DFS перебирает вершины в алфавитном порядке и что списки смежных вершин также упорядочены по алфамиту.

23.5-3

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

23.5-4

Пусть G - ориентированный граф. Если стянуть каждую его сильно связную компоненту в точку, и после этого отождествить рёбра с одинаковыми началами и концами, получится граф компонент (component graph) GSGG = {VSGG, ESGG). Другими словами, элементами VSGG являются сильно связные компоненты С, и ESGG содержит ребро (и, v) в том и только в том случае, если в G есть ориентированное ребро, начало которого принадлежит и, а конец - v (см. пример на рис. 23.9 (с)). Докажите, что граф компонент не имеет циклов.

23.5-5

Постройте алгоритм, находящий за время 0{E-\-V) граф компонент данного ориентированного графа. (В строимом графе любые две вершины должны быть соединены не более чем одним ребром.)

23.5-6

Дан ориентированный граф G = (V, Е). Как построить как можно меньший граф G = (V, Е), который имел бы те же самые сильно связные компоненты и тот же граф компонент? Постройте эффективный алгоритм решения этой задачи.

23.5-7

Ориентированный граф называется G = (V, Е) называется полусвязным (semiconnected), если для любых двух его вершин и и v либо v достижима из и, либо и достижима из v. Придумайте эффективный алгоритм, определяющий, будет ли граф полусвязным. Каково время его работы?

Задачи

23-1 Классификация ребер при поиске в ширину Классифицируя рёбра графа по типам, мы исходили из дерева поиска в глубину. Аналогичная классификаия возможно и для дерева поиска в ширину (для рёбер, достижимых из начальной вершины).

а. Докажите следующие свойства для случая поиска в ширину в неориентированном графе:

1.Не бывает прямых и обратных рёбер.

2.Если (и, v) - ребро дерева, то d[v] = d[u] + 1.


Рис. 23.8 23.10 Точки раздела, мосты и двусвязные компоненты связного неориентированного графа (задача 23-2). Точки раздела и мосты - тёмно-серые, двусвязные компоненты - наборы рёбер в пределах одной серой области (внутри которой указано Ьсс).

3. Если (и, v) - перекрёстное ребро, то d[v] = d[u] или d[v] = d[u] + 1.

b. Докажите следующие свойства для случая поиска в ширину в ориентированном графе:

1.Не бывает прямых рёбер.

2.Если (и, v) - ребро дерева, то d[v] = d[u] + 1.

3.Если (и, v) - перекрёстное ребро, то d[v] d[u] + 1.

4.Если (и, v) - обратное ребро, то 0 d[v] < d[u]. 23-2 Точки раздела, мосты и двусвязные компоненты

Пусть G = (V, Е) - связный неориентированный граф. Точка раздела (articulation point) графа G - это вершина, при удалении которой граф G перестаёт быть связным. Мост (bridge) - это ребро с аналогичным свойством. Двусвязная компонента (bicon-nected component) - это максимальный набор рёбер, любые два ребра которого принадлежат общему простому циклу (см. пример на рис. 23.10). Точки раздела, мосты и двусвязные компоненты можно найти с помощью поиска в глубину.

Пусть Gv = (V, Ev) - дерево поиска в глубину в графе G.

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

b.Пусть v - отличная от корня вершина Gv. Докажите, что v - точка раздела G, если и только если не существует обратного ребра (u,w), для которого и - потомок v и w - предок v в Gv, отличный от w.

c.Пусть /ом?[и] - минимальное число среди d[v] и чисел d[w] для всех w, для которых имеется обратное ребро (и, w) для некоторой вершины и, являющейся потомком v. Покажите, как можно вычислить /ом? [и] для всех v £ V за время 0(V).

d.Как найти все точки раздела за время О(Е)?

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

f.Как найти все мосты графа G за время О(Е)?

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

h.Придумайте алгоритм, который за время 0(E) помечает каждое ребро е графа G некоторым целым числом Ьсс[е], при этом метки двух рёбер совпадают, если и только если рёбра принадлежат одной двусвязной компоненте.

23-3 Эйлеров цикл

Эйлеровым циклсш(Еи1ег tour) связного ориентированного гра-



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]