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

Постановка задачи

Дан неориентированный граф [math] G [/math]. Найти все мосты в [math] G [/math] за время [math] O(|V| + |E|)[/math]

Алгоритм

Теорема:

Пусть [math] T [/math] - дерево обхода в глубину графа [math] G[/math]. Ребро [math] (u, v) [/math] является мостом тогда и только тогда, когда [math] (u, v) \in T[/math] и из вершины [math] v[/math] и любого ее потомка нет обратного ребра в вершину [math] u[/math] или предка [math] u [/math]

Доказательство:

[math]\triangleright[/math]

[math] \Leftarrow[/math] Удалим [math] (u, v)[/math] из [math] G[/math] Докажем, что мы не сможем достичь ни одного из предков [math] v [/math] (в частности [math] u [/math]). Пусть это не так, и [math] w[/math] - предпоследняя вершина на пути от [math] v[/math] до ее предка [math]x [/math]. Очевидно, [math] (w, x)[/math] не ребро дерева (в силу единственности пути в дереве). Если [math] (w, x)[/math] - обратное ребро, то это противоречит условию теоремы, т.к. [math] x[/math] - предок [math] u[/math] [math] \Rightarrow[/math] Докажем что из отрицания второго утверждения следует отрицание первое. Пусть существует удовлетворяющее условию обратное ребро [math](x, w)[/math]. Тогда [math](u, v)[/math] лежит на цикле [math]x \rightsquigarrow v \rightarrow u \rightsquigarrow w \rightarrow x[/math] и не может быть ребром.

[math]\triangleleft[/math]