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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(не показано 36 промежуточных версий 8 участников)
Строка 1: Строка 1:
== Постановка задачи ==
+
Дан неориентированный [[Основные определения теории графов#Граф| граф]] <tex> G </tex>. Найти все [[Мост, эквивалентные определения | мосты]] в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>
Дан неориентированный граф <tex> G </tex>. Найти все мосты в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>
 
  
 
== Алгоритм ==
 
== Алгоритм ==
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть <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> T </tex> дерево [[Обход в глубину, цвета вершин | обхода в глубину графа]] <tex> G</tex>. Ребро <tex> (u, v) </tex> является мостом тогда и только тогда, когда <tex> (u, v) \in T</tex> и из вершины <tex> v</tex> и любого ее потомка нет обратного ребра в вершину <tex> u</tex> или предка <tex> u </tex>
 
|proof=
 
|proof=
 
<tex> \Leftarrow</tex> <br>
 
<tex> \Leftarrow</tex> <br>
Удалим <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> <br>
+
Удалим <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> \Rightarrow</tex> <br>
 
<tex> \Rightarrow</tex> <br>
Докажем что из отрицания второго утверждения следует отрицание первого.
 
 
Пусть существует удовлетворяющее условию обратное ребро <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>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(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</tex> убывают, то <tex>ret(v)</tex> возвращает величину <tex>enter</tex> для ближайшей к корню вершины, достижимой из <tex>v</tex> или ее потомка, возможно используя одно обратное ребро.
 
  
 +
* <tex>enter(v)</tex> [[Использование обхода в глубину для топологической сортировки | время входа в вершину <tex>v </tex> ]] <br>
 +
* <tex>enter(x)</tex>, где <tex>x</tex> — потомок <tex>v</tex> <br>
 +
* <tex>enter(w)</tex>, где <tex>(w, x)</tex> — обратное ребро, а <tex>w</tex> — потомок <tex>v</tex> (в нестрогом смысле) <br>
 +
 +
===Лемма===
 
{{Лемма
 
{{Лемма
 +
|statement = Ребро <tex>(u, v)</tex> является мостом тогда и только тогда, когда <tex>(u, v)</tex> принадлежит дереву обхода в глубину и <tex>ret(v) > enter(u)</tex>
 +
| proof = Рассмотрим вершину <tex>v</tex> или её потомка. Из нее есть обратное ребро в предка <tex>v</tex> тогда и только тогда, когда найдется такой сын <tex>t</tex>, что <tex>ret[t] \le enter[v]</tex>. Если <tex>ret[t] = enter[v]</tex>, то найдется обратное ребро, приходящее точно в <tex>v</tex>. Если же <tex>ret[t] < enter[v]</tex>, то это означает наличие обратного ребра в какого-либо предка вершины <tex>v</tex>.
 +
 +
Таким образом, если для текущего ребра <tex>(v, t)</tex> (принадлежащего дереву поиска) выполняется <tex>ret[t] > enter[v]</tex>, то это ребро является мостом; в противном случае оно мостом не является.
 +
}}
 +
 +
 +
{{Утверждение
 
|statement =
 
|statement =
<tex>ret(v)</tex> = <tex>min: </tex> <br>
+
<tex>ret(v)</tex> = <tex>\min(</tex> <tex>enter(v) </tex>, <tex>enter(p)</tex>, <tex>ret(u)</tex>
<tex>enter(v) </tex> <br>
+
<tex>) </tex>, где <br> <tex>(v, p)</tex> — обратное ребро, <br> <tex>(v, u)</tex> ребро дерева
<tex>enter(p)</tex>, <tex>(v, p)</tex> - обратное ребро <br>
 
<tex>ret(u)</tex>, <tex>(v, u)</tex> - ребро дерева
 
 
|proof =
 
|proof =
1)<tex>enter(v) </tex> <br> <br>
+
[[Файл:Bridges_dfs.png|300px|thumb|right|В скобах у вершины <tex>u</tex> указаны <tex>enter[u]</tex> и <tex>ret[u]</tex>. Мостами будут красные ребра]]
По определению функции <tex>ret</tex> <br>
+
#<tex>enter(v) </tex> <br>По определению функции <tex>ret</tex> <br>
2)<tex>enter(p)</tex>, <tex>(v, p)</tex> - обратное ребро <br>
+
#<tex>enter(p)</tex>, <tex>(v, p)</tex> обратное ребро <br><tex>p</tex> достижима из  <tex>v</tex> по одному обратному ребру, значит величина  <tex>ret(v)</tex> не больше  <tex>enter(p)</tex> <br>
<tex>p</tex> достижима из  <tex>v</tex> по одному обратному ребру, значит величина  <tex>ret(v)</tex> не больше  <tex>enter(p)</tex> <br>
+
#<tex>ret(u)</tex>, <tex>u</tex> потомок <tex>v</tex> <br>Так как вершина <tex>u</tex> потомок <tex>v</tex>, то обратное ребро из ее поддерева является обратным ребром из поддерева <tex>v</tex> <br>
3)<tex>ret(u)</tex>, <tex>u</tex> - потомок <tex>v</tex> <br>
 
Так как вершина <tex>u</tex> - потомок <tex>v</tex>, то обратное ребро из ее поддерева является обратным ребром из поддерева <tex>v</tex> <br>
 
 
}}
 
}}
 +
 +
=== Псевдокод ===
 +
'''function''' dfs(v):
 +
  time = time + 1
 +
  enter[v] = time
 +
  ret[v] = time
 +
  '''for''' всех u смежных с v
 +
    '''if''' (v, u) — обратное ребро
 +
      ret[v] = min(ret[v], enter[u])
 +
    '''if''' вершина u — белая
 +
      dfs(u)
 +
      ret[v] = min(ret[v], ret[u])
 +
      '''if''' ret[u] > enter[v]
 +
        ребро (v, u) — мост
 +
 +
==См. также==
 +
*[[Обход в глубину, цвета вершин]]
 +
*[[Лемма о белых путях]]
 +
==Источники информации==
 +
* [http://e-maxx.ru/algo/bridge_searching  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
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обход в глубину]]

Версия 20:16, 12 декабря 2020

Дан неориентированный граф [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]v[/math], а значит количество компонент связности увеличилось, поэтому ребро [math](u, v)[/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]v [/math]
  • [math]enter(x)[/math], где [math]x[/math] — потомок [math]v[/math]
  • [math]enter(w)[/math], где [math](w, x)[/math] — обратное ребро, а [math]w[/math] — потомок [math]v[/math] (в нестрогом смысле)

Лемма

Лемма:
Ребро [math](u, v)[/math] является мостом тогда и только тогда, когда [math](u, v)[/math] принадлежит дереву обхода в глубину и [math]ret(v) \gt enter(u)[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим вершину [math]v[/math] или её потомка. Из нее есть обратное ребро в предка [math]v[/math] тогда и только тогда, когда найдется такой сын [math]t[/math], что [math]ret[t] \le enter[v][/math]. Если [math]ret[t] = enter[v][/math], то найдется обратное ребро, приходящее точно в [math]v[/math]. Если же [math]ret[t] \lt enter[v][/math], то это означает наличие обратного ребра в какого-либо предка вершины [math]v[/math].

Таким образом, если для текущего ребра [math](v, t)[/math] (принадлежащего дереву поиска) выполняется [math]ret[t] \gt enter[v][/math], то это ребро является мостом; в противном случае оно мостом не является.
[math]\triangleleft[/math]


Утверждение:
[math]ret(v)[/math] = [math]\min([/math] [math]enter(v) [/math], [math]enter(p)[/math], [math]ret(u)[/math] [math]) [/math], где
[math](v, p)[/math] — обратное ребро,
[math](v, u)[/math] — ребро дерева
[math]\triangleright[/math]
В скобах у вершины [math]u[/math] указаны [math]enter[u][/math] и [math]ret[u][/math]. Мостами будут красные ребра
  1. [math]enter(v) [/math]
    По определению функции [math]ret[/math]
  2. [math]enter(p)[/math], [math](v, p)[/math] — обратное ребро
    [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]

Псевдокод

function dfs(v):
  time = time + 1
  enter[v] = time
  ret[v] = time 
  for всех u смежных с v
    if (v, u) — обратное ребро
      ret[v] = min(ret[v], enter[u])
    if вершина u — белая
      dfs(u)
      ret[v] = min(ret[v], ret[u]) 
      if ret[u] > enter[v] 
        ребро (v, u) — мост

См. также

Источники информации