Изменения
Нет описания правки
{{Теорема
|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>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> - — мост
==Источники==
