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>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> (в нестрогом смысле) <br> <br>
Так как на пути от вершины к корню дерева величины <tex>enter(x)</tex> убывают, то <tex>ret(v)</tex> возвращает величину <tex>enter(u)</tex> для ближайшей к корню вершины, достижимой из <tex>v</tex> или ее потомка, возможно используя одно обратное ребро. {{Лемма|statement =<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>u</tex> - потомок <tex>v</tex>|proof =<tex>enter(v) </tex> <br> <br>По определению функции <tex>ret</tex> <br>1)<tex>enter(p)</tex>, <tex>(v, p)</tex> - обратное ребро <br>1)<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>}}
