Изменения
→Алгоритм
== Алгоритм ==
{{Теорема
|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> . Следовательно мы не достигнем предков <tex>v</tex>, а значит количество компонент связности увеличилось, поэтому ребро <tex>(u, v)</tex> является мостом.<br>
<tex> \Rightarrow</tex> <br>
}}
{{Утверждение
|statement =
<tex>ret(v)</tex> = <tex>\min(</tex> <tex>enter(v) </tex>, <tex>enter(p)</tex>, <tex>ret(u)</tex>
<tex>) </tex>, где <br> <tex>(v, p)</tex> — обратное ребро, <br> <tex>(v, u)</tex> — ребро дерева
|proof =
[[Файл:Bridges_dfs.png|300px|thumb|right|В скобах у вершины <tex>u</tex> указаны <tex>enter[u]</tex> и <tex>ret[u]</tex>. Мостами будут красные ребра]]
#<tex>enter(v) </tex> <br>По определению функции <tex>ret</tex> <br>
#<tex>enter(p)</tex>, <tex>(v, p)</tex> — обратное ребро <br><tex>p</tex> достижима из <tex>v</tex> по одному обратному ребру, значит величина <tex>ret(v)</tex> не больше <tex>enter(p)</tex> <br>
#<tex>ret(u)</tex>, <tex>u</tex> — потомок <tex>v</tex> <br>Так как вершина <tex>u</tex> — потомок <tex>v</tex>, то обратное ребро из ее поддерева является обратным ребром из поддерева <tex>v</tex> <br>
}}
=== Псевдокод ===
'''function''' dfs(v):
time = time + 1
enter[v] = time
ret[v] = time
'''for''' всех u смежных с v
'''if''' (v, u) — обратное ребро
ret[v] = min(ret[v], enter[u])
'''if''' вершина u — белая
dfs(u)
ret[v] = min(ret[v], ret[u])
'''if''' ret[u] > enter[v]
ребро (v, u) — мост
==См. также==
*[[Обход в глубину, цвета вершин]]
*[[Лемма о белых путях]]
==Источники информации==
* [http://e-maxx.ru/algo/bridge_searching MAXimal :: algo :: Поиск мостов]
* [http://en.wikipedia.org/wiki/Bridge_(graph_theory) Wikipedia — Bridge]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005| Визуализация поиска мостов]
* ''Седжвик Р.'' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]