Построение компонент вершинной двусвязности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Двупроходный алгоритм)
Строка 7: Строка 7:
 
'''Второй проход
 
'''Второй проход
 
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.
 
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.
Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u : return[u] \ge enter[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. <br>
+
Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u : return[u] \geqslant enter[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. <br>
 
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
 
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
'''Псевдокод второго прохода:
+
=== Псевдокод второго прохода ===
 
{| width = 100%
 
{| width = 100%
 
|-
 
|-
 
|  
 
|  
   dfs(<tex>v, c, parent</tex>)
+
   <tex>dfs</tex>(<tex>v</tex>, color, parent):
       для всех  вершин u смежных v:
+
       '''for''' <tex> u \in V : (v, u) \in E</tex>:
             если (<tex>u</tex> родитель)
+
             '''if''' <tex>u</tex> == parent
                 переходим к следующей итерации
+
                 continue
             если (<tex>u</tex> не посещена)
+
             '''if''' '''not''' visited[<tex>u</tex>]
                 если (<tex>return[u] >= enter[v]</tex>)
+
                 '''if''' return[<tex>u</tex>] <tex>\geqslant</tex> enter[<tex>v</tex>]
                     <tex>c2 \leftarrow</tex> новый цвет
+
                     newColor <tex>\leftarrow</tex> maxColor++
                     <tex>col[vu] \leftarrow c2</tex>
+
                     col[<tex>vu</tex>] <tex>\leftarrow</tex> newColor
                     dfs(<tex>u, c2, v</tex>)
+
                     <tex>dfs</tex>(<tex>u</tex>, newColor, <tex>v</tex>)
                 иначе
+
                 '''else'''
                     <tex>col[vu] \leftarrow c</tex>
+
                     col[<tex>vu</tex>] <tex>\leftarrow</tex> color
                     dfs(<tex>u, c, v</tex>)
+
                     <tex>dfs</tex>(<tex>u</tex>, color, <tex>v</tex>)
             иначе:
+
             '''else'''
                 если (<tex>enter[u] <= enter[v]</tex>)
+
                 '''if''' enter[<tex>u</tex>] <tex>\leqslant</tex> enter[<tex>v</tex>]
                     <tex>col[vu] \leftarrow c</tex>        
+
                     col[<tex>vu</tex>] <tex>\leftarrow</tex> color
     start()
+
     ...
        для всех v вершин графа:
+
    '''for''' <tex> v \in V</tex>:
            если (<tex>v</tex> не посещена)
+
        '''if''' '''not''' visited[<tex>v</tex>]
                dfs(<tex>v, -1, -1</tex>)
+
            <tex>dfs</tex>(<tex>v</tex>, -1, -1)
 
|width = "310px" |[[Файл:Vertex_doubleconnection_1.png‎‎|thumb|center|400px|Компоненты обозначены разным цветом]]
 
|width = "310px" |[[Файл:Vertex_doubleconnection_1.png‎‎|thumb|center|400px|Компоненты обозначены разным цветом]]
 
|}
 
|}

Версия 20:36, 9 ноября 2015

Двупроходный алгоритм

Найти компоненты вершинной двусвязности неориентированного графа можно с помощью обхода в глубину.

Первый проход Используем первый проход, чтобы найти точки сочленения.

Второй проход Точка сочленения принадлежит как минимум двум компонентам вершинной двусвязности. Вершина [math] v \ne root [/math] является точкой сочленения, если у нее есть сын [math] u : return[u] \geqslant enter[v] [/math].
Это также значит, что ребро [math] vu [/math] содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину [math] v [/math] , используя поиск в глубину.
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.

Псевдокод второго прохода

  [math]dfs[/math]([math]v[/math], color, parent):
      for [math] u \in V : (v, u) \in E[/math]:
           if [math]u[/math] == parent
               continue
           if not visited[[math]u[/math]]
               if return[[math]u[/math]] [math]\geqslant[/math] enter[[math]v[/math]]
                   newColor [math]\leftarrow[/math] maxColor++
                   col[[math]vu[/math]] [math]\leftarrow[/math] newColor
                   [math]dfs[/math]([math]u[/math], newColor, [math]v[/math])
               else
                   col[[math]vu[/math]] [math]\leftarrow[/math] color
                   [math]dfs[/math]([math]u[/math], color, [math]v[/math])
           else
               if enter[[math]u[/math]] [math]\leqslant[/math] enter[[math]v[/math]]
                   col[[math]vu[/math]] [math]\leftarrow[/math] color
   ...
   for [math] v \in V[/math]:
       if not visited[[math]v[/math]]
           [math]dfs[/math]([math]v[/math], -1, -1)
Компоненты обозначены разным цветом


Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
В алгоритме выполняется два прохода [math]dfs[/math], каждый из которых работает [math]O(V + E)[/math]. Значит время работы алгоритма [math]O(V + E)[/math].

Однопроходный алгоритм

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

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

Предположим, что граф содержит точку сочленения [math] i' \in V [/math] , за которой следует один или несколько блоков. Вершины из этих блоков образуют подмножество [math] V' \subset V [/math]. В таком случае:

  1. Все вершины [math] V' [/math] являются потомками [math] i' [/math] в дереве обхода;
  2. Все вершины [math] V' [/math] будут пройдены в течение периода серого состояния [math] i' [/math];
  3. В [math] G [/math] не может быть обратных дуг из [math] V' [/math] в [math] V \setminus V' [/math].

Значит все дуги [math] V' [/math] будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.
Псевдокод:

   dfs([math]v, parent[/math])
       [math]enter[v] \leftarrow return[v] \leftarrow time[/math]++
       для всех  вершин [math]u[/math] смежных [math]v[/math]:
           если ([math]u[/math] родитель) 
               переходим к следующей итерации
           если ([math]u[/math] не посещена)
               добавить в стек ребро[math]vu[/math]
               dfs([math]u, v[/math])
               если ([math]return[u] \gt = enter[v][/math])
                   [math]c \leftarrow [/math] новый цвет
                   пока (ребро [math]vu[/math] не равно вершине стека)
                       [math]color[/math][вершина стека] [math] \leftarrow c[/math]
                       извлечь вершину стека
                   [math]color[vu] \leftarrow c[/math]
                   извлечь вершину стека
               если ([math]return[u] \lt  return[v][/math])
                   [math]return[v] \leftarrow return[u][/math]
           иначе
               если ([math]enter[u] \lt  enter[v][/math]) 
                    добавить в стек ребро [math]vu[/math]
               если ([math]return[v] \gt  enter[u][/math])
                   [math]return[v] \leftarrow return[u][/math]
   start()
       для всех [math]v[/math] вершин графа:
           если ([math]v[/math] не посещена)
               [math]time \leftarrow 0[/math]
               dfs([math]v[/math], -1)


Во время алгоритма совершается один проход [math]dfs[/math], который работает за [math]O(V + E)[/math]. Внутри него совершается еще цикл, который суммарно выполняет [math]O(E)[/math] операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма [math]O(V + E) + O(E) = O(V + E)[/math]

Литература

  • В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007