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