26
правок
Изменения
Нет описания правки
Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <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++;
для всех v вершин графа:
если (!used[v]):
dfs(v, max(c), -1);
}
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
==Однопроходный алгоритм==
Предположим, что граф содержит точку сочленения <tex> i' \in V </tex> , за которой следует один или несколько блоков, содержащих вершины <tex> V' \subset V </tex>. В таком случае: <br>
1) Все вершины <tex> V' </tex> являются потомками <tex> i' </tex> в дереве обхода;
2) Все вершины <tex> V' </tex> будут пройдены в течение периода серого состояния <tex> i' </tex>.
При этом в <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>. Воспользуемся этим.
Заведем стек, в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека.
Псевдокод:
void dfs(v, parent) {
enter[v] = return[v] = time++;
used[v] = true;
для всех вершин u смежных v:
если (u == parent):
переходим к следующей итерации
если (!used[u]):
stack <- (vu);
dfs(u, v);
если (return[u] >= enter[v]):
develop(v); // обработка найденной точки сочленения и удаление дуг очередного блока
если (return[u] < return[v]):
return[v] = return[u];
иначе:
если (return[v] > enter[u]):
return[v] = return[u];
}
void start() {
used для всех вершин заполняем false
для всех v вершин графа:
если (!used[v]):
time = 0;
dfs(v, -1);
}
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
== См. также ==
[[Использование обхода в глубину для поиска точек сочленения]]
[[Построение компонент реберной двусвязности]]
==Литература==
* В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
