Изменения

Перейти к: навигация, поиск
Нет описания правки
<tex>ret(u)</tex>, <tex>u</tex> - потомок <tex>v</tex>
|proof =
1)<tex>enter(v) </tex> <br> <br>
По определению функции <tex>ret</tex> <br>
12)<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> <br>
}}
69
правок

Навигация