Изменения

Перейти к: навигация, поиск

Использование обхода в глубину для поиска мостов

Нет изменений в размере, 22:07, 24 декабря 2015
Лемма
{{Утверждение
|statement =
<tex>ret(v)</tex> = <tex>\min(</tex> <br>* <tex>enter(v) </tex> <br>* , <tex>enter(p)</tex>, <tex>ret(v, pu)</tex> — обратное ребро <br>* <tex>ret(u)</tex>, где <br> <tex>(v, up)</tex> — обратное ребро дерева, <br> <tex>(v, u) </tex>— ребро дерева
|proof =
[[Файл:Bridges_dfs.png|300px|thumb|right|В скобах у вершины <tex>u</tex> указаны <tex>enter[u]</tex> и <tex>ret[u]</tex>. Мостами будут красные ребра]]
Анонимный участник

Навигация