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