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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
м (rollbackEdits.php mass rollback)
 
(не показаны 24 промежуточные версии 10 участников)
Строка 1: Строка 1:
Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>
+
{{Задача
 +
|definition=Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|).</tex>
 +
}}
  
 
== Алгоритм ==
 
== Алгоритм ==
{{Теорема
 
|statement=
 
Пусть <tex>T</tex> — дерево [[Обход в глубину, цвета вершин|обхода в глубину]], <tex>root</tex> — корень <tex>T</tex>. Вершина <tex>u \ne root</tex> — точка сочленения <tex>\Leftrightarrow \exists v \in T</tex> — сын <tex>u</tex> : из <tex>v</tex> или любого потомка вершины <tex>v</tex> нет обратного ребра в предка вершины <tex>u</tex>. <tex>root</tex> — точка сочленения <tex>\Leftrightarrow root</tex> имеет хотя бы двух сыновей в дереве поиска в глубину.
 
|proof=
 
[[Файл:Joint_point_1.png|48px |thumb|‎ | Рисунок к <tex>\Leftarrow</tex>]]
 
<tex>\Leftarrow</tex>
 
  
#Удалим <tex>u</tex> из <tex>G</tex>. Докажем, что не существует пути из <tex>v</tex> в любого предка вершины <tex>u</tex>. Пусть это не так. Тогда <tex>\exists x \in T</tex> — предок <tex>u</tex> : <tex>\exists</tex> путь из <tex>v</tex> в <tex>x</tex> в <tex>G \backslash u</tex>. Пусть <tex>w</tex> — предпоследняя вершина на этом пути, <tex>w</tex> — потомок <tex>v</tex>. <tex>(w, x)</tex> — не ребро дерева <tex>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> — обратное ребро, что противоречит условию.
+
=== Описание алгоритма ===
#Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> — точка сочленения.
+
Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из произвольной вершины графа; обозначим её через <tex>root</tex>. Заметим следующий факт:
<br clear="all">
+
 
<tex>\Rightarrow</tex>
+
* Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины <tex>v</tex>. Тогда, если текущее ребро (<tex>v</tex>,<tex>to</tex>) таково, что из вершины <tex>to</tex> и из любого её потомка в дереве обхода в глубину нет обратного ребра в вершину <tex>v</tex> или какого-либо её предка, то эта вершина является точкой сочленения. В противном случае она ей не является. (В самом деле, мы этим условием проверяем, нет ли другого пути из <tex>v</tex> в <tex>to</tex>, кроме как спуск по ребру (<tex>v</tex>,<tex>to</tex>) дерева обхода в глубину.)
#Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <tex>G'</tex> граф, состоящий из вершин, не являющихся потомками <tex>u</tex>. Удалим вершину <tex>u</tex>. Очевидно, что граф <tex>G'</tex> и все поддеревья вершины <tex>u</tex> останутся связными, кроме того из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash u</tex> — связный <tex>\Rightarrow u</tex> — не точка сочленения.
 
#Пусть <tex>root</tex> — точка сочленения и у него есть только один сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что <tex>root</tex> — точка сочленения.
 
}}
 
  
 +
Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину.
  
[[Файл:Joint_point_2.png‎|400px|thumb|Красным цветом обозначены точки сочленения<br>Синим — ребра по которым идет DFS]]
+
[[Файл:Joint_point_2_rsz.png‎|280px|thumb|left| <font color=red>Красным</font> цветом обозначены точки сочленения<br><font color=blue>Синим</font> — ребра по которым идет DFS]]
 
Пусть <tex>tin[u]</tex> — время входа поиска в глубину в вершину <tex>u</tex>. Через <tex>up[u]</tex> обозначим минимум из времени захода в саму вершину <tex>tin[u]</tex>, времен захода в каждую из вершин <tex>p</tex>, являющуюся концом некоторого обратного ребра <tex>(u,p)</tex>, а также из всех значений <tex>up[v]</tex> для каждой вершины <tex>v</tex>, являющейся непосредственным сыном <tex>u</tex> в дереве поиска.
 
Пусть <tex>tin[u]</tex> — время входа поиска в глубину в вершину <tex>u</tex>. Через <tex>up[u]</tex> обозначим минимум из времени захода в саму вершину <tex>tin[u]</tex>, времен захода в каждую из вершин <tex>p</tex>, являющуюся концом некоторого обратного ребра <tex>(u,p)</tex>, а также из всех значений <tex>up[v]</tex> для каждой вершины <tex>v</tex>, являющейся непосредственным сыном <tex>u</tex> в дереве поиска.
  
Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] < tin[u]</tex>.
+
Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] &lt; tin[u]</tex>.
  
Таким образом, если для текущей вершины <tex>v \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \ge tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является.
+
Таким образом, если для текущей вершины <tex>u \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \geqslant tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является.
  
 
<br clear="all">
 
<br clear="all">
  
== Реализация ==
+
=== Псевдокод ===
 
   
 
   
  '''function''' findCutPoints(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе </font>
+
  '''function''' findCutPoints(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе </font>
 
     visited = array[n, ''false'']
 
     visited = array[n, ''false'']
 
                      
 
                      
Строка 35: Строка 29:
 
       time = time + 1
 
       time = time + 1
 
       up[v] = tin[v] = time  
 
       up[v] = tin[v] = time  
       visited[v] = ''true''             
+
       visited[v] = ''true''
 +
      count = 0              
 
       '''for''' u: (v, u) '''in''' G   
 
       '''for''' u: (v, u) '''in''' G   
 
           '''if''' u == p
 
           '''if''' u == p
             continue
+
             '''continue'''
           '''if''' visited[u] == ''true''
+
           '''if''' visited[u]
 
             up[v] = min(up[v], tin[u])
 
             up[v] = min(up[v], tin[u])
 
           '''else'''
 
           '''else'''
 
             dfs(u, v)  
 
             dfs(u, v)  
             up[v] = min(up[v], tin[u])
+
            count = count + 1
             '''if''' up[to] >= tin[v] && p != -1 <font color=darkgreen>//если граф состоит из 2 вершин и одного ребра, то p != -1 спасёт, иначе выведет 1 точку сочленения </font>
+
             up[v] = min(up[v], up[u])
 +
             '''if''' p != -1 '''and''' up[u] >= tin[v]
 
                   v — cutpoint  
 
                   v — cutpoint  
       '''if''' v — root
+
       '''if''' p == -1 '''and''' count >= 2
 
             v — cutpoint  
 
             v — cutpoint  
 
                        
 
                        
 
     '''for''' i = 1 '''to''' n             
 
     '''for''' i = 1 '''to''' n             
       '''if''' visited[i] == ''false''               
+
       '''if''' '''not''' visited[i]            
 
           dfs(i, -1)
 
           dfs(i, -1)
 +
 +
=== Доказательство корректности ===
 +
{{Теорема
 +
|statement=
 +
Пусть <tex>T</tex> — дерево [[Обход в глубину, цвета вершин|обхода в глубину]], <tex>root</tex> — корень <tex>T</tex>.
 +
* Вершина <tex>u \ne root</tex> — точка сочленения <tex>\Leftrightarrow \exists v \in T</tex> — сын <tex>u</tex> : из <tex>v</tex> или любого потомка вершины <tex>v</tex> нет обратного ребра в предка вершины <tex>u</tex>.
 +
* <tex>root</tex> — точка сочленения <tex>\Leftrightarrow root</tex> имеет хотя бы двух сыновей в дереве поиска в глубину.
 +
|proof=
 +
[[Файл:Joint_point_1.png|48px |thumb|‎ | Рисунок к <tex>\Leftarrow</tex>]]
 +
<tex>\Leftarrow</tex>
 +
 +
#Удалим <tex>u</tex> из <tex>G</tex>. Докажем, что не существует пути из <tex>v</tex> в любого предка вершины <tex>u</tex>. Пусть это не так. Тогда <tex>\exists x \in T</tex> — предок <tex>u</tex> : <tex>\exists</tex> путь из <tex>v</tex> в <tex>x</tex> в <tex>G \backslash u</tex>. Пусть <tex>w</tex> — предпоследняя вершина на этом пути, <tex>w</tex> — потомок <tex>v</tex>. <tex>(w, x)</tex> — не ребро дерева <tex>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> — обратное ребро, что противоречит условию.
 +
#Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> — точка сочленения.
 +
 +
<tex>\Rightarrow</tex>
 +
#Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <tex>G'</tex> граф, состоящий из вершин, не являющихся потомками <tex>u</tex>. Удалим вершину <tex>u</tex>. Очевидно, что граф <tex>G'</tex> и все поддеревья вершины <tex>u</tex> останутся связными, кроме того из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash u</tex> — связный <tex>\Rightarrow u</tex> — не точка сочленения.
 +
#Пусть <tex>root</tex> — точка сочленения и у него есть только один сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что <tex>root</tex> — точка сочленения.
 +
}}
 +
 +
<br clear="all">
 +
 +
=== Асимптотика ===
 +
Оценим время работы алгоритма. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(e)} = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>. Такое же, как у [[Обход в глубину, цвета вершин|обхода в глубину]].
  
 
== См. также ==
 
== См. также ==

Текущая версия на 19:28, 4 сентября 2022

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


Алгоритм

Описание алгоритма

Запустим обход в глубину из произвольной вершины графа; обозначим её через [math]root[/math]. Заметим следующий факт:

  • Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины [math]v[/math]. Тогда, если текущее ребро ([math]v[/math],[math]to[/math]) таково, что из вершины [math]to[/math] и из любого её потомка в дереве обхода в глубину нет обратного ребра в вершину [math]v[/math] или какого-либо её предка, то эта вершина является точкой сочленения. В противном случае она ей не является. (В самом деле, мы этим условием проверяем, нет ли другого пути из [math]v[/math] в [math]to[/math], кроме как спуск по ребру ([math]v[/math],[math]to[/math]) дерева обхода в глубину.)

Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину.

Красным цветом обозначены точки сочленения
Синим — ребра по которым идет DFS

Пусть [math]tin[u][/math] — время входа поиска в глубину в вершину [math]u[/math]. Через [math]up[u][/math] обозначим минимум из времени захода в саму вершину [math]tin[u][/math], времен захода в каждую из вершин [math]p[/math], являющуюся концом некоторого обратного ребра [math](u,p)[/math], а также из всех значений [math]up[v][/math] для каждой вершины [math]v[/math], являющейся непосредственным сыном [math]u[/math] в дереве поиска.

Тогда из вершины [math]u[/math] или её потомка есть обратное ребро в её предка [math]\Leftrightarrow \exists[/math] такой сын [math]v[/math], что [math]up[v] < tin[u][/math].

Таким образом, если для текущей вершины [math]u \ne root [/math] существует непосредственный сын [math]v[/math]: [math]up[v] \geqslant tin[u][/math], то вершина [math]u[/math] является точкой сочленения, в противном случае она точкой сочленения не является.


Псевдокод

function findCutPoints(G[n]: Graph): // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе 
    visited = array[n, false]
                   
   function dfs(v: int, p: int):
      time = time + 1
      up[v] = tin[v] = time 
      visited[v] = true
      count = 0             
      for u: (v, u) in G   
         if u == p
            continue
         if visited[u]
            up[v] = min(up[v], tin[u])
         else
            dfs(u, v) 
            count = count + 1
            up[v] = min(up[v], up[u])
            if p != -1 and up[u] >= tin[v]
                 v — cutpoint 
      if p == -1 and count >= 2
            v — cutpoint 
                   	   
   for i = 1 to n             
      if not visited[i]              
         dfs(i, -1)

Доказательство корректности

Теорема:
Пусть [math]T[/math] — дерево обхода в глубину, [math]root[/math] — корень [math]T[/math].
  • Вершина [math]u \ne root[/math] — точка сочленения [math]\Leftrightarrow \exists v \in T[/math] — сын [math]u[/math] : из [math]v[/math] или любого потомка вершины [math]v[/math] нет обратного ребра в предка вершины [math]u[/math].
  • [math]root[/math] — точка сочленения [math]\Leftrightarrow root[/math] имеет хотя бы двух сыновей в дереве поиска в глубину.
Доказательство:
[math]\triangleright[/math]
Рисунок к [math]\Leftarrow[/math]

[math]\Leftarrow[/math]

  1. Удалим [math]u[/math] из [math]G[/math]. Докажем, что не существует пути из [math]v[/math] в любого предка вершины [math]u[/math]. Пусть это не так. Тогда [math]\exists x \in T[/math] — предок [math]u[/math] : [math]\exists[/math] путь из [math]v[/math] в [math]x[/math] в [math]G \backslash u[/math]. Пусть [math]w[/math] — предпоследняя вершина на этом пути, [math]w[/math] — потомок [math]v[/math]. [math](w, x)[/math] — не ребро дерева [math]T[/math](в силу единственности пути в дереве) [math]\Rightarrow (w, x)[/math] — обратное ребро, что противоречит условию.
  2. Пусть у [math]root[/math] хотя бы два сына. Тогда при удалении [math]root[/math] не существует пути между его поддеревьями, так как не существует перекрестных ребер [math]\Rightarrow root[/math] — точка сочленения.

[math]\Rightarrow[/math]

  1. Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через [math]G'[/math] граф, состоящий из вершин, не являющихся потомками [math]u[/math]. Удалим вершину [math]u[/math]. Очевидно, что граф [math]G'[/math] и все поддеревья вершины [math]u[/math] останутся связными, кроме того из каждого поддерева есть ребро в [math]G' \Rightarrow G \backslash u[/math] — связный [math]\Rightarrow u[/math] — не точка сочленения.
  2. Пусть [math]root[/math] — точка сочленения и у него есть только один сын. Тогда при удалении [math]root[/math] остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что [math]root[/math] — точка сочленения.
[math]\triangleleft[/math]


Асимптотика

Оценим время работы алгоритма. Процедура [math]\mathrm{dfs}[/math] вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие ребра [math]\{e\ |\ \mathrm{begin(e)} = v\}[/math]. Всего таких ребер для всех вершин в графе [math]O(E)[/math], следовательно, время работы алгоритма оценивается как [math]O(V+E)[/math]. Такое же, как у обхода в глубину.

См. также

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