Изменения

== Постановка задачи == Дан неориентированный [[Основные определения теории графов#Граф| граф ]] <tex> G </tex>. Найти все [[Мост, эквивалентные определения | мосты ]] в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>

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

Удалим <tex> (u, v)</tex> из <tex> G</tex> . Докажем, что мы не сможем достичь ни одного из предков <tex> v </tex> (в частности <tex> u </tex>). Докажем этот факт от противного. Пусть это не так, и <tex> w</tex> - — предпоследняя вершина на пути от <tex> v</tex> до ее предка <tex>x </tex>. Очевидно, <tex> (w, x)</tex> не ребро дерева (в силу единственности пути в дереве). Если <tex> (w, x)</tex> - — обратное ребро, то это противоречит условию теоремы, т.к. так как <tex> x</tex> - — предок <tex> u</tex> . Следовательно мы не достигнем предков <tex>v</tex>, а значит количество компонент связности увеличилось, поэтому ребро <tex>(u, v)</tex> является мостом.<br>

* <tex>enter(v)</tex> [[Использование обхода в глубину для топологической сортировки | время входа в вершину <tex>v </tex> ]] <br>* <tex>enter(x)</tex>, где <tex>x</tex> - — потомок <tex>v</tex> <br>* <tex>enter(xw)</tex>, где <tex>(w, x)</tex> - — обратное ребро, а <tex>w</tex> - — потомок <tex>v</tex> (в нестрогом смысле) <br> ===Лемма===

| 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> - мост, то это ребро является мостом; в противном случае оно мостом не является.

{{ЛеммаУтверждение

<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>— ребро дерева

[[Файл:Bridges_nvBridges_dfs.png|150px300px|thumb|right|В скобах у вершины <tex>u</tex> указаны <tex>enter[u]</tex> и <tex>ret[u]</tex>. Мостами будут красные ребра <tex>23, 59, 78</tex>]]1)#<tex>enter(v) </tex> <br>По определению функции <tex>ret</tex> <br>2)#<tex>enter(p)</tex>, <tex>(v, p)</tex> - — обратное ребро <br><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> <br>

'''dfsfunction'''dfs(<tex> v </tex>): <tex> time \leftarrow = time + 1</tex> <tex>enter[v] \leftarrow = time</tex> <tex>ret[v] \leftarrow = time </tex> '''for''' всех <tex>u</tex> смежных с <tex>v</tex> '''if'' <tex>' (v, u)</tex> - — обратное ребро <tex>ret[v] \leftarrow = min(ret[v], enter[u])</tex> '''if''' вершина <tex>u</tex> - — белая '''dfs'''(u) <tex> ret[v] \leftarrow = min(ret[v], ret[u]) </tex> '''if''' <tex>ret[u] > enter[v]</tex> ребро <tex>(v, u)</tex> - — мост==Смотри также==*[[Обход в глубину, цвета вершин|Обход в глубину]]*[[Использование обхода в глубину для поиска точек сочленения]]*[[Построение компонент вершинной двусвязности]]*[[Построение компонент реберной двусвязности]]*[http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005| Визуализация поиска мостов]

==См. также==*[[Обход в глубину, цвета вершин]]*[[Лемма о белых путях]]==Источникиинформации==# * [http://e-maxx.ru/algo/bridge_searching| Сайт e-maxx MAXimal :: algo :: Поиск мостов]# * [http://en.wikipedia.org/wiki/Bridge_(graph_theory) Wikipedia — Bridge]* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005| Свободная энциклопедия Визуализация поиска мостов]* ''Седжвик Р.'' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123- Википедия]128

==Литература==Седжвик Роберт. Фундаментальные алгоритмы на C++. Часть 5[[Категория: Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб.и структуры данных]][[Категория: ООО «ДиаСофтЮП», 2002. — С. 123-128Обход в глубину]]