69
правок
Изменения
Нет описания правки
<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>
}}
