Изменения

Удалим <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>v \in 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>ret(v)</tex> = <tex>min(</tex> <br>

<tex>) </tex>

|proof =

1)<tex>enter(v) </tex> <br>

По определению функции <tex>ret</tex> <br>

==Литература==

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