69
правок
Изменения
Нет описания правки
Пусть существует удовлетворяющее условию обратное ребро <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(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> (в нестрогом смысле)
Так как на пути от вершины к корню дерева величины <tex>enter(x)</tex> убывают, то <tex>ret(v)</tex> возвращает величину<tex>enter(u)</tex> для ближайшей к корню вершины, достижимо из <tex>v</tex> или ее потомка, возмонжно используя одно обратное ребро.
