26
правок
Изменения
Новая страница: «==Определение== {{Определение |definition = Компонентой вершинной двусвязности графа <tex>G(V, E)</tex> н…»
==Определение==
{{Определение
|definition = Компонентой вершинной двусвязности графа <tex>G(V, E)</tex> называется подмножество ребер <tex> S \subset E </tex>, такое что любые два ребра из него лежат на вершинно простом цикле.
}}
Построение компонент вершинной двусвязности будем осуществлять с помощью обхода в глубину.
==Двупроходный алгоритм==
=Первый проход=
Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <br>
Определим для каждой вершины две величины: <tex> enter [i] </tex> - время входа поиска в глубину в вершину <tex> i </tex>, <tex> return [i] </tex> – минимальное из времен входа вершин, достижимых из <tex> i </tex> по дереву <tex> dfs </tex> и не более, чем одному обратному ребру. Ребро к родителю не является обратным ребром. <br>
'''Псевдокод:
void dfs(v, parent) {
enter[v] = return[v] = time++;
used[v] = true;
для всех вершин u смежных v:
если (u == parent):
переходим к следующей итерации
если (used[u]):
return[v] := min(return[v], enter[u]);
иначе:
dfs(u, v);
return[v] := min(return[v], return[u]);
}
void start() {
used для всех вершин заполняем false
для всех v вершин графа:
если (!used[v]):
time = 0;
dfs(v, -1);
}
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязаности.
Вершина <tex> u \ne root </tex> является точкой сочленения, если у нее <tex> \exists </tex> непосредственный сын <tex> v : return[v]\ge enter[u] </tex>. <br> Это так же значит, что ребро <tex> uv </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. <br>
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
'''Псевдокод второго прохода:
void dfs(v, c, parent) {
used[v] = true;
для всех вершин u смежных v:
если (u == parent):
переходим к следующей итерации
если (!used[u]):
если (return[u] >= enter[v]):
с2 = newColor();
col[vu] = c2;
dfs(u, c2, v);
иначе:
col[vu] = c;
dfs(u, c, v);
иначе:
если (enter[u] <= enter[v]):
col[vu] = c;
}
void start() {
c = 0;
used для всех вершин заполняем false;
для всех v вершин графа:
если (!used[v]):
dfs(v, c, -1);
}
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
{{Определение
|definition = Компонентой вершинной двусвязности графа <tex>G(V, E)</tex> называется подмножество ребер <tex> S \subset E </tex>, такое что любые два ребра из него лежат на вершинно простом цикле.
}}
Построение компонент вершинной двусвязности будем осуществлять с помощью обхода в глубину.
==Двупроходный алгоритм==
=Первый проход=
Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <br>
Определим для каждой вершины две величины: <tex> enter [i] </tex> - время входа поиска в глубину в вершину <tex> i </tex>, <tex> return [i] </tex> – минимальное из времен входа вершин, достижимых из <tex> i </tex> по дереву <tex> dfs </tex> и не более, чем одному обратному ребру. Ребро к родителю не является обратным ребром. <br>
'''Псевдокод:
void dfs(v, parent) {
enter[v] = return[v] = time++;
used[v] = true;
для всех вершин u смежных v:
если (u == parent):
переходим к следующей итерации
если (used[u]):
return[v] := min(return[v], enter[u]);
иначе:
dfs(u, v);
return[v] := min(return[v], return[u]);
}
void start() {
used для всех вершин заполняем false
для всех v вершин графа:
если (!used[v]):
time = 0;
dfs(v, -1);
}
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязаности.
Вершина <tex> u \ne root </tex> является точкой сочленения, если у нее <tex> \exists </tex> непосредственный сын <tex> v : return[v]\ge enter[u] </tex>. <br> Это так же значит, что ребро <tex> uv </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. <br>
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
'''Псевдокод второго прохода:
void dfs(v, c, parent) {
used[v] = true;
для всех вершин u смежных v:
если (u == parent):
переходим к следующей итерации
если (!used[u]):
если (return[u] >= enter[v]):
с2 = newColor();
col[vu] = c2;
dfs(u, c2, v);
иначе:
col[vu] = c;
dfs(u, c, v);
иначе:
если (enter[u] <= enter[v]):
col[vu] = c;
}
void start() {
c = 0;
used для всех вершин заполняем false;
для всех v вершин графа:
если (!used[v]):
dfs(v, c, -1);
}
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
