Просмотр исходного текста страницы Использование обхода в глубину для поиска мостов

== Постановка задачи == 
Дан неориентированный граф <tex> G </tex>. Найти все мосты в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>

== Алгоритм ==
{{Теорема
|statement=
Пусть <tex> T </tex> - дерево обхода в глубину графа <tex> G</tex>. Ребро <tex> (u, v) </tex> является мостом тогда и только тогда, когда <tex> (u, v) \in T</tex> и из вершины <tex> v</tex> и любого ее потомка нет обратного ребра в вершину <tex> u</tex> или предка <tex> u </tex>
|proof=
<tex> \Leftarrow</tex> <br>
Удалим <tex> (u, v)</tex> из <tex> G</tex> Докажем, что мы не сможем достичь ни одного из предков <tex> v </tex> (в частности <tex> u </tex>). Пусть это не так, и <tex> w</tex> - предпоследняя вершина на пути от <tex> v</tex> до ее предка <tex>x </tex>. Очевидно, <tex> (w, x)</tex> не ребро дерева (в силу единственности пути в дереве). Если <tex> (w, x)</tex> - обратное ребро, то это противоречит условию теоремы, т.к. <tex> x</tex> - предок <tex> u</tex> <br>
<tex> \Rightarrow</tex> <br>
Докажем что из отрицания второго утверждения следует отрицание первого.
Пусть существует удовлетворяющее условию обратное ребро <tex>(x, w)</tex>. Тогда <tex>(u, v)</tex> лежит на цикле <tex>x \rightsquigarrow v \rightarrow u \rightsquigarrow w \rightarrow x</tex> и не может быть мостом.
}}
==== Функция <tex>ret(v)</tex> ====
Определим функцию <tex>ret(v)</tex>, где <tex>v \in V</tex>, как минимум из следущих величин <br>

* <tex>enter(v)</tex> <br>
* <tex>enter(x)</tex>, где <tex>x</tex> - потомок <tex>v</tex> <br>
* <tex>enter(x)</tex>, где <tex>(w, x)</tex> - обратное ребро, а <tex>w</tex> - потомок <tex>v</tex> (в нестрогом смысле) <br>
 
{{Лемма
|statement = Ребро <tex>(u, v)</tex> является мостом тогда и только тогда, когда <tex>(u, v)</tex> принадлежит дереву обхода в глубину и <tex>ret(v) > enter(u)</tex>
| proof = 
Так как на пути от вершины к корню дерева величины <tex>enter</tex> убывают, то <tex>ret(v)</tex> возвращает величину <tex>enter</tex> для ближайшей к корню вершины, достижимой из <tex>v</tex> или ее потомка, возможно используя одно обратное ребро. Следовательно, из вершины <tex>v</tex> или ее потомков существует обратное ребро потомка <tex>u</tex> или саму <tex>u</tex> тогда и только тогда, когда <tex>ret(v) <= enter(u)</tex>. По доказанной теореме, отсутствие такого ребра эквивалентно тому что <tex>(u, v)</tex> - мост.
}}


{{Лемма
|statement =
<tex>ret(v)</tex> = <tex>min(</tex> <br>
* <tex>enter(v) </tex> <br>
* <tex>enter(p)</tex>, <tex>(v, p),</tex> - обратное ребро <br>
* <tex>ret(u)</tex>, <tex>(v, u)</tex> - ребро дерева
<tex>) </tex>
|proof =
[[Файл:Bridges_nv.png|150px|thumb|right|В скобах у вершины <tex>u</tex> указаны <tex>enter[u]</tex> и <tex>ret[u]</tex>. Мостами будут ребра <tex>23, 59, 78</tex>]]
1)<tex>enter(v) </tex> <br>
По определению функции <tex>ret</tex> <br>
2)<tex>enter(p)</tex>, <tex>(v, p)</tex> - обратное ребро <br>
<tex>p</tex> достижима из  <tex>v</tex> по одному обратному ребру, значит величина  <tex>ret(v)</tex> не больше  <tex>enter(p)</tex> <br>
3)<tex>ret(u)</tex>, <tex>u</tex> - потомок <tex>v</tex> <br>
Так как вершина <tex>u</tex> - потомок <tex>v</tex>, то обратное ребро из ее поддерева является обратным ребром из поддерева <tex>v</tex> <br>
}}

=== Псевдокод ===
 '''dfs'''(<tex> v </tex>)
   <tex> time \leftarrow time + 1</tex>
   <tex>enter[v] \leftarrow time</tex>
   <tex>ret[v] \leftarrow time </tex>
   '''for''' всех <tex>u</tex> смежных с <tex>v</tex>
     ''if'' <tex>(v, u)</tex> - обратное ребро
       <tex>ret[v] \leftarrow min(ret[v], enter[u])</tex>
     '''if''' вершина <tex>u</tex> - белая
       '''dfs'''(u)
       <tex> ret[v] \leftarrow min(ret[v], ret[u]) </tex>
       '''if''' <tex>ret[u] > enter[v]</tex> 
         ребро <tex>(v, u)</tex> - мост

==Смотри также==
*[[Обход в глубину, цвета вершин|Обход в глубину]]
*[[Использование обхода в глубину для поиска точек сочленения]]
*[[Построение компонент вершинной двусвязности]]
*[[Построение компонент реберной двусвязности]]
*[http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005| Визуализация поиска мостов]

==Источники==
# [http://e-maxx.ru/algo/bridge_searching| Сайт e-maxx]
# [http://en.wikipedia.org/wiki/Bridge_(graph_theory)| Свободная энциклопедия - Википедия]

==Литература==
Седжвик Роберт. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128