|
|
| Строка 1: |
Строка 1: |
| − | == Основные понятия ==
| |
| | | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | Две вершины <tex>u</tex> и <tex>v</tex> [[Основные определения теории графов|графа]] <tex>G</tex> называются '''реберно двусвязными''', если между этими вершинами существуют два реберно непересекающихся пути.
| |
| − | }}
| |
| − |
| |
| − | {{Определение
| |
| − | |definition =
| |
| − | '''Компонентами реберной двусвязности''' графа называют его подграфы, множества вершин которых - классы эквивалентности реберной двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности.
| |
| − | }}
| |
| − |
| |
| − | Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]].
| |
| − |
| |
| − | == Двупроходный алгоритм ==
| |
| − |
| |
| − | Первый способ найти искомые компоненты - сначала определить критерий перехода в новую компоненту реберной двусвязности, а затем покрасить вершины графа в нужные цвета.
| |
| − |
| |
| − | Первый проход определяет для каждой вершины <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> не является обратным ребром обхода.
| |
| − |
| |
| − | Псевдокод первого прохода:
| |
| − |
| |
| − | '''обнуляем массив enter
| |
| − | текущее время := 0
| |
| − | 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))
| |
| − | ...
| |
| − | для всех вершин v графа:
| |
| − | если enter(v) = 0:
| |
| − | dfs(v, null)'''
| |
| − |
| |
| − | Определим критерий перехода к новой компоненте.
| |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Ребро <tex>uv</tex> ведет из одной компоненты реберной двусвязности в другую, если оно является частью дерева <tex>dfs</tex>, и либо <tex>u</tex> - предок <tex>v</tex> и <tex>return(v) = enter(v)</tex>, либо наоборот.
| |
| − | |proof=
| |
| − | Если ребро <tex>uv</tex> - обратное, образуется цикл, содержащий <tex>uv</tex>, поэтому <tex>uv</tex> не может являться мостом.
| |
| − | Последнее равенство означает, что из <tex>v</tex> и ее потомков нельзя подняться выше <tex>v</tex> по дереву обхода, в том числе, и в <tex>u</tex>. Таким образом, между <tex>u</tex> и <tex>v</tex> существует лишь один путь - ребро <tex>uv</tex>, - и они принадлежат разным компонентам реберной двусвязности.
| |
| − | }}
| |
| − |
| |
| − | Основываясь на этом, определим алгоритм окраски вершин графа. Путь по графу будет точно таким же, как и в первом проходе, что гарантирует постоянность дерева <tex>dfs</tex> и определенных параметров вершин: <tex>enter</tex> и <tex>return</tex>.
| |
| − |
| |
| − | Псевдокод второго прохода:
| |
| − |
| |
| − | '''обнуляем массив colors
| |
| − | максимальный цвет := 0
| |
| − | paint(v, цвет):
| |
| − | colors(v) := цвет
| |
| − | для всех вершин u, смежных v:
| |
| − | если colors(u) равен нулю (вершина не покрашена):
| |
| − | если return(u) = enter(u):
| |
| − | увеличиваем максимальный цвет
| |
| − | paint(u, максимальный цвет)
| |
| − | иначе:
| |
| − | paint(u, цвет)
| |
| − | ...
| |
| − | для всех вершин v графа:
| |
| − | если colors(v) = 0:
| |
| − | увеличиваем максимальный цвет
| |
| − | paint(v, максимальный цвет)'''
| |
| − |
| |
| − | Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
| |
| − |
| |
| − | == См. также ==
| |
| − | [[Отношение реберной двусвязности]]
| |
