Изменения
Нет описания правки
==== Функция <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>
{{Лемма
|statement = Ребро <tex>(u, v)</tex> является ребром тогда и только тогда, когда <tex>(u, v)</tex> принадлежит дереву обхода в глубину и <tex>ret(v) > enter(u)</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> - ребро дерева<tex>) </tex>
|proof =
1)<tex>enter(v) </tex> <br>
