Изменения
→Алгоритм
<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>
Пусть существует удовлетворяющее условию обратное ребро <tex>(x, w)</tex>. Тогда <tex>(u, v)</tex> лежит на цикле <tex>x \rightsquigarrow v \rightarrow u \rightsquigarrow w \rightarrow x</tex> и не может быть мостом.
* <tex>enter(v)</tex> [[Использование обхода в глубину для топологической сортировки | время входа в вершину <tex>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>v</tex> или её потомка. Из них нее есть обратное ребро обратное в в предка <tex>v</tex>, тогда и только тогда, когда найдется такой сын <tex>t</tex>, что <tex>ret[t] \le enter[v]</tex>. Так как, если Если <tex>ret[t] = enter[v]</tex>, то это означает, что найдётся найдется обратное ребро, приходящее точно в <tex>v</tex>. Если же <tex>ret[t] < enter[v]</tex>, то это означает наличие обратного ребра в какого-либо предка вершины <tex>v</tex>.
Таким образом, если для текущего ребра <tex>(v, t)</tex> (принадлежащего дереву поиска) выполняется <tex>ret[t] > enter[v]</tex>, то это ребро является мостом; в противном случае оно мостом не является.
<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 =
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>
}}
