Изменения

* <tex>enter(xw)</tex>, где <tex>(w, x)</tex> — обратное ребро, а <tex>w</tex> — потомок <tex>v</tex> (в нестрогом смысле) <br>

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>

'''dfsfunction'''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://e-maxx.ru/algo/bridge_searching Сайт e-maxxMAXimal :: 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