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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
Пусть существует удовлетворяющее условию обратное ребро <tex>(x, w)</tex>. Тогда <tex>(u, v)</tex> лежит на цикле <tex>x \rightsquigarrow v \rightarrow u \rightsquigarrow w \rightarrow x</tex> и не может быть мостом.
 
Пусть существует удовлетворяющее условию обратное ребро <tex>(x, w)</tex>. Тогда <tex>(u, v)</tex> лежит на цикле <tex>x \rightsquigarrow v \rightarrow u \rightsquigarrow w \rightarrow x</tex> и не может быть мостом.
 
}}
 
}}
 +
=== Функция <tex>ret(v)</tex> ===
 
Определим функцию <tex>ret(v)</tex>, где <tex>v \in V</tex>, как минимум из следущих величин <br>
 
Определим функцию <tex>ret(v)</tex>, где <tex>v \in V</tex>, как минимум из следущих величин <br>
 
<tex>enter(v)</tex> <br>
 
<tex>enter(v)</tex> <br>
 
<tex>enter(x)</tex>, где <tex>x</tex> - потомок <tex>v</tex> <br>
 
<tex>enter(x)</tex>, где <tex>x</tex> - потомок <tex>v</tex> <br>
 
<tex>enter(x)</tex>, где <tex>(w, x)</tex> - обратное ребро, а <tex>w</tex> - потомок <tex>v</tex> (в нестрогом смысле) <br> <br>
 
<tex>enter(x)</tex>, где <tex>(w, x)</tex> - обратное ребро, а <tex>w</tex> - потомок <tex>v</tex> (в нестрогом смысле) <br> <br>
Так как на пути от вершины к корню дерева величины <tex>enter(x)</tex> убывают, то <tex>ret(v)</tex> возвращает величину <tex>enter(u)</tex> для ближайшей к корню вершины, достижимой из <tex>v</tex> или ее потомка, возможно используя одно обратное ребро.
+
Так как на пути от вершины к корню дерева величины <tex>enter</tex> убывают, то <tex>ret(v)</tex> возвращает величину <tex>enter</tex> для ближайшей к корню вершины, достижимой из <tex>v</tex> или ее потомка, возможно используя одно обратное ребро.
 +
 
 +
{{Лемма
 +
|statement =
 +
<tex>ret(v)</tex> = <tex>min: </tex> <br>
 +
<tex>enter(v) </tex> <br>
 +
<tex>enter(p)</tex>, <tex>(v, p)</tex> - обратное ребро <br>
 +
<tex>ret(u)</tex>, <tex>u</tex> - потомок <tex>v</tex>
 +
|proof =
 +
<tex>enter(v) </tex> <br> <br>
 +
По определению функции <tex>ret</tex> <br>
 +
1)<tex>enter(p)</tex>, <tex>(v, p)</tex> - обратное ребро <br>
 +
1)<tex>p</tex> достижима из  <tex>v</tex> по одному обратному ребру, значит величина  <tex>ret(v)</tex> не больше  <tex>enter(p)</tex> <br>
 +
3)<tex>ret(u)</tex>, <tex>u</tex> - потомок <tex>v</tex> <br>
 +
Так как вершина <tex>u</tex> - потомок <tex>v</tex>, то обратное ребро из ее поддерева является обратным ребром из поддерева <tex>v</tex>
 +
}}

Версия 10:12, 8 декабря 2010

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

Дан неориентированный граф [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]

Функция [math]ret(v)[/math]

Определим функцию [math]ret(v)[/math], где [math]v \in V[/math], как минимум из следущих величин
[math]enter(v)[/math]
[math]enter(x)[/math], где [math]x[/math] - потомок [math]v[/math]
[math]enter(x)[/math], где [math](w, x)[/math] - обратное ребро, а [math]w[/math] - потомок [math]v[/math] (в нестрогом смысле)

Так как на пути от вершины к корню дерева величины [math]enter[/math] убывают, то [math]ret(v)[/math] возвращает величину [math]enter[/math] для ближайшей к корню вершины, достижимой из [math]v[/math] или ее потомка, возможно используя одно обратное ребро.

Лемма:
[math]ret(v)[/math] = [math]min: [/math]

[math]enter(v) [/math]
[math]enter(p)[/math], [math](v, p)[/math] - обратное ребро

[math]ret(u)[/math], [math]u[/math] - потомок [math]v[/math]
Доказательство:
[math]\triangleright[/math]

[math]enter(v) [/math]

По определению функции [math]ret[/math]
1)[math]enter(p)[/math], [math](v, p)[/math] - обратное ребро
1)[math]p[/math] достижима из [math]v[/math] по одному обратному ребру, значит величина [math]ret(v)[/math] не больше [math]enter(p)[/math]
3)[math]ret(u)[/math], [math]u[/math] - потомок [math]v[/math]

Так как вершина [math]u[/math] - потомок [math]v[/math], то обратное ребро из ее поддерева является обратным ребром из поддерева [math]v[/math]
[math]\triangleleft[/math]