69
правок
Изменения
Нет описания правки
Пусть существует удовлетворяющее условию обратное ребро <tex>(x, w)</tex>. Тогда <tex>(u, v)</tex> лежит на цикле <tex>x \rightsquigarrow v \rightarrow u \rightsquigarrow w \rightarrow x</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>
<tex>enter(x)</tex>, где <tex>(w, x)</tex> - обратное ребро, а <tex>w</tex> - потомок <tex>v</tex> (в нестрогом смысле)
