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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
  
 
Первый проход определяет для каждой вершины <tex>v</tex> две величины: <tex>enter(v)</tex> - время входа поиска в глубину в вершину, <tex>return(v)</tex> - минимальное из времен входа вершин, достижимых из <tex>v</tex> по [[Обход в глубину, цвета вершин|дереву <tex>dfs</tex>]] и не более, чем одному обратному ребру. <tex>return(v)</tex> находится как <tex>min(enter(v), return(u), enter(w))</tex> для всех <tex>u</tex> - сыновей <tex>v</tex> в дереве <tex>dfs</tex>, <tex>w</tex> - соседей <tex>v</tex> по обратным ребрам. Важно, что ребро к родителю дерева <tex>dfs</tex> не является обратным ребром обхода.
 
Первый проход определяет для каждой вершины <tex>v</tex> две величины: <tex>enter(v)</tex> - время входа поиска в глубину в вершину, <tex>return(v)</tex> - минимальное из времен входа вершин, достижимых из <tex>v</tex> по [[Обход в глубину, цвета вершин|дереву <tex>dfs</tex>]] и не более, чем одному обратному ребру. <tex>return(v)</tex> находится как <tex>min(enter(v), return(u), enter(w))</tex> для всех <tex>u</tex> - сыновей <tex>v</tex> в дереве <tex>dfs</tex>, <tex>w</tex> - соседей <tex>v</tex> по обратным ребрам. Важно, что ребро к родителю дерева <tex>dfs</tex> не является обратным ребром обхода.
−
 
−
Псевдокод первого прохода:
 
−
 
−
  '''void dfs(v, родитель):
 
−
    увеличиваем текущее время
 
−
    enter(v) := текущее время   
 
−
    return(v) := enter(v)
 
−
    для всех вершин u, смежных v:
 
−
      если enter(u) равен нулю (вершина не посещена):
 
−
        dfs(u, v)
 
−
        return(v) := min(return(v), return(u))
 
−
      иначе если u не родитель:
 
−
        return(v) := min(return(v), enter(u))
 
−
  ...
 
−
  обнуляем массив enter
 
−
  текущее время := 0
 
−
  для всех вершин v графа:
 
−
    если enter(v) = 0:
 
−
      dfs(v, null)'''
 
  
 
Определим критерий перехода к новой компоненте.
 
Определим критерий перехода к новой компоненте.
Строка 61: Строка 42:
 
== Однопроходный алгоритм ==
 
== Однопроходный алгоритм ==
  
−
Можно также искать компоненты реберной двусвязности путем конкатенации циклов. Воспользуемся тем, что реберная двусвязность является отношением эквивалентности на вершинах графа; тогда, если у двух циклов существует хоть одна общая вершина, все вершины, располагающиеся на этих циклах, принадлежат одной компоненте. Более того, две вершины <tex>u</tex> и <tex>v</tex> лежат в одной компоненте реберной двусвязности тогда и только тогда, когда существует последовательность простых циклов <tex>c_1 c_2 ... c_n</tex>, причем <tex>u \in c_1</tex>, <tex>v \in c_n</tex>, и <tex>c_i</tex> имеет с <tex>c_{i + 1}</tex> хотя бы одну общую вершину для всех <tex>i \in {1 ... n - 1}</tex>. Действительно, если зафиксировать один путь от <tex>u</tex> до <tex>v</tex>, а затем искать точки пересечения второго, не имеющего одинаковых ребер с первым, пути с ним, то получится последовательность циклов, точками сочленения между которыми будут как раз точки пересечения путей. И наоборот, последовательность простых циклов легко превратить в два реберно непересекающихся пути.
+
Можно найти компоненты реберной двусвязности за один проход используя стек.
−
 
+
−
Совокупность компонент реберной двусвязности будем хранить как систему непересекающихся множеств вершин.
+
Алгоритм, если мы посетили вершину, то добавляем её в стек. Так же как раньше <tex>ret[v]</tex> и <tex>enter[v]</tex>. Теперь определим, когда надо окрасить компоненту.
−
 
+
Если мы возвращаясь обратно оказались в вершине, которая является вершиной моста, то все вершины, находящиеся, до текущей в стеке, принадлежат этой компоненте. Это следует из того, что [[Граф компонент реберной двусвязности | граф блоков и мостов, является деревом]]. По свойству обхода в ширину, мы окажемся в висячей вершине, покрасим её, то есть эту компоненту покрасим. Её можно выкинут и рассматривать оставшийся граф. Действуя по аналогии мы всегда выкидываем компоненту реберной двусвязности следовательно, если мы вернулись в вершину, которая была концом нашего моста, то все вершины лежащие до нашей в стеке, принадлежат данной компоненте.  
 
Псевдокод:
 
Псевдокод:
  
−
   '''int dfs(v, родитель): (возвращает 0, если у v и ее потомков нет обратных ребер, и представителя множества, содержащего цикл с v, в обратном случае)
+
   '''void paint(int v):
−
    seen(v) = true
+
     maxcolor++;
−
    value = 0, result = 0
+
       while (пока вершина стека не вершина <tex>v</tex> и стек не пустой)
−
     для всех вершин u, смежных v:
+
         извлекаем вершину стека и красим её;
−
       если не seen(u):
+
−
        value = dfs(u, v)
+
    
−
        если value > 0:
 
−
          color(v) = value
 
−
          result = value
 
−
         иначе если u не родитель:
 
−
          color(v) = color(u)
 
−
          result = color(v)
 
−
    return result
 
−
  ...
 
−
  обнуляем массив seen
 
−
  нумеруем вершины графа натуральными числами от 1 до мощности множества вершин графа
 
−
  для всех вершин v графа:
 
−
    color(v) = номер вершины (номер цвета соответствует номеру вершины-представителя в множестве)
 
−
   для всех вершин v графа:
 
−
    если не seen(v):
 
−
      dfs(v, null)'''
 
  
−
Осталось лишь сопоставить всем вершинам отдельно взятой компоненты единственного представителя.
+
   '''void dfs(вершина v, предок вершины p):
−
 
+
    добавляем вершину в в стек;
−
Псевдокод:
+
    state[v] = 1;
−
 
+
    ret[v] = enter[v] = ++time;
−
   '''int relax(v): (возвращает нового представителя)
+
    для всех  вершин u смежных v:
−
    если color(v) не равен номеру v:
+
      если (u == parent):
−
      color(v) = relax(color(v))
+
        переходим к следующей итерации
−
    return color(v)
+
      если (state[u] = 1):
−
  ...
+
          ret[v] = min(ret[v], enter[u]);
−
  для всех вершин v графа:
+
        иначе:
−
     relax(v)
+
          если (state[u] = 0):
 +
            dfs(u, v);
 +
            ret[v] = min(ret[v], ret[u]);
 +
            если (enter[v] < ret[u]):  
 +
            paint(u);
 +
     state[v] = 2;
 +
  
 
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
 
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
  
−
Время работы dfs <tex> O(|V| + |E|)</tex>. А время восстановления <tex> O(|V|)</tex>, так как [[Анализ реализации с ранговой эвристикой | снм]].
+
Время работы dfs <tex> O(|V| + |E|)</tex>. Покраска за <tex> O(|V|) </tex>.
 
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
 
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
  

Версия 07:27, 9 ноября 2011

Основные понятия

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

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

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

Первый проход определяет для каждой вершины [math]v[/math] две величины: [math]enter(v)[/math] - время входа поиска в глубину в вершину, [math]return(v)[/math] - минимальное из времен входа вершин, достижимых из [math]v[/math] по дереву [math]dfs[/math] и не более, чем одному обратному ребру. [math]return(v)[/math] находится как [math]min(enter(v), return(u), enter(w))[/math] для всех [math]u[/math] - сыновей [math]v[/math] в дереве [math]dfs[/math], [math]w[/math] - соседей [math]v[/math] по обратным ребрам. Важно, что ребро к родителю дерева [math]dfs[/math] не является обратным ребром обхода.

Определим критерий перехода к новой компоненте. Воспользуемся ранее доказанной леммой.

Основываясь на этом, определим алгоритм окраски вершин графа. Перешли по мосту, следовательно началась новая компонента.

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

 void paint(v, цвет):
   colors(v) := цвет
   для всех вершин u, смежных v:
     если colors(u) равен нулю (вершина не покрашена):
       если return(u) = enter(u):
         увеличиваем максимальный цвет
         paint(u, максимальный цвет)
       иначе:
         paint(u, цвет)
 ...
 обнуляем массив colors
 максимальный цвет := 0
 для всех вершин v графа:
   если colors(v) = 0:
     увеличиваем максимальный цвет
     paint(v, максимальный цвет)

Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.

Время работы алгоритма будет время работы двух запусков dfs, то есть 2 * [math] O(|V| + |E|)[/math], что есть [math] O(|V| + |E|)[/math].

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

Можно найти компоненты реберной двусвязности за один проход используя стек.

Алгоритм, если мы посетили вершину, то добавляем её в стек. Так же как раньше [math]ret[v][/math] и [math]enter[v][/math]. Теперь определим, когда надо окрасить компоненту. Если мы возвращаясь обратно оказались в вершине, которая является вершиной моста, то все вершины, находящиеся, до текущей в стеке, принадлежат этой компоненте. Это следует из того, что граф блоков и мостов, является деревом. По свойству обхода в ширину, мы окажемся в висячей вершине, покрасим её, то есть эту компоненту покрасим. Её можно выкинут и рассматривать оставшийся граф. Действуя по аналогии мы всегда выкидываем компоненту реберной двусвязности следовательно, если мы вернулись в вершину, которая была концом нашего моста, то все вершины лежащие до нашей в стеке, принадлежат данной компоненте. Псевдокод: 

 void paint(int v):
   maxcolor++;
     while (пока вершина стека не вершина [math]v[/math] и стек не пустой)
       извлекаем вершину стека и красим её; 



 void dfs(вершина v, предок вершины p):
   добавляем вершину в в стек;
   state[v] = 1;
   ret[v] = enter[v] = ++time;
   для всех  вершин u смежных v:
     если (u == parent): 
       переходим к следующей итерации
      	если (state[u] = 1):
         ret[v] = min(ret[v], enter[u]);
       иначе:
         если (state[u] = 0):
           dfs(u, v);
           ret[v] = min(ret[v], ret[u]);
           если (enter[v] < ret[u]): 
           paint(u);	
   state[v] = 2;

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

Время работы dfs [math] O(|V| + |E|)[/math]. Покраска за [math] O(|V|) [/math]. Итоговое время работы алгоритма [math] O(|V| + |E|)[/math].

См. также

Литература

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Построение_компонент_рёберной_двусвязности&oldid=12917»