152
правки
Изменения
→Лемма
{{Лемма
|statement = Ребро <tex>(u, v)</tex> является мостом тогда и только тогда, когда <tex>(u, v)</tex> принадлежит дереву обхода в глубину и <tex>ret(v) > enter(u)</tex>
| proof = Так как на пути от вершины к корню дерева величины Рассмотрим вершину <tex>enterv</tex> убывают, то или её потомка. Из них есть обратное ребро обратное в в предка <tex>ret(v)</tex> возвращает величину , тогда и только тогда, когда найдется такой сын <tex>entert</tex> для ближайшей к корню вершины, достижимой из что <tex>ret[t] \le enter[v]</tex> или ее потомка, возможно используя одно обратное ребро. СледовательноТак как, из вершины если <tex>ret[t] = enter[v]</tex> или ее потомков существует , то это означает, что найдётся обратное ребро потомка , приходящее точно в <tex>uv</tex> или саму . Если же <tex>uret[t] < enter[v]</tex> тогда и только тогда, когда то это означает наличие обратного ребра в какого-либо предка вершины <tex>ret(v) <= enter(u)</tex>. По доказанной теореме Таким образом, отсутствие такого если для текущего ребра эквивалентно тому что <tex>(uv, t)</tex> (принадлежащего дереву поиска) выполняется <tex>ret[t] > enter[v)]</tex> - мост, то это ребро является мостом; в противном случае оно мостом не является.
}}
