Задача о динамической связности — различия между версиями
(→Обобщение задачи для произвольных графов) |
(→Обобщение задачи для произвольных графов) |
||
| Строка 35: | Строка 35: | ||
Введём функцию <tex>l(e):e{\rightarrow}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Будем рассматривать графы <tex>G_i=\langle V, E\rangle: {E|l(E) \geqslant i}</tex>. Очевидно, что <tex>G_{\mathrm{\log}n} \subseteq G_{\mathrm{\log}n-1} \subseteq ... \subseteq G_1 \subseteq G_0</tex>. Выделим в них остовные леса таким образом, чтобы <tex>F_{\mathrm{\log}n} \subseteq F_{\mathrm{\log}n-1} \subseteq ... \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>. | Введём функцию <tex>l(e):e{\rightarrow}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Будем рассматривать графы <tex>G_i=\langle V, E\rangle: {E|l(E) \geqslant i}</tex>. Очевидно, что <tex>G_{\mathrm{\log}n} \subseteq G_{\mathrm{\log}n-1} \subseteq ... \subseteq G_1 \subseteq G_0</tex>. Выделим в них остовные леса таким образом, чтобы <tex>F_{\mathrm{\log}n} \subseteq F_{\mathrm{\log}n-1} \subseteq ... \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>. | ||
| − | < | + | При удалении возможны случаи: |
| − | <!-- | + | * '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части, и задача решается как для дерева за <tex>O(\mathrm{\log}n)</tex>. |
| + | * '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях. Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру. | ||
| + | |||
| + | Осталось узнать, как проверить, является ли ребро мостом. | ||
| + | |||
| + | <!-- я лошара) --> | ||
<!--== Алгоритм == | <!--== Алгоритм == | ||
=== Время работы === // i think i'll tell it | === Время работы === // i think i'll tell it | ||
Версия 00:38, 8 января 2018
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.
Содержание
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — .
Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения системы непересекающихся множеств, такой запрос будет работать за .
Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим остовные деревья, которые образуют остовный лес. Граф и его остовный лес — одно и то же с точки зрения связности.
Введём функцию и назовём её уровнем ребра . Будем рассматривать графы . Очевидно, что . Выделим в них остовные леса таким образом, чтобы , где — остовный лес графа .
При удалении возможны случаи:
- Удаляемое ребро является мостом. В этом случае дерево распадается на две части, и задача решается как для дерева за .
- Удаляемое ребро не является мостом. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины и лежат в разных частях. Если принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
Осталось узнать, как проверить, является ли ребро мостом.
