Задача о динамической связности — различия между версиями
(→Обобщение задачи для произвольных графов) |
(→Обобщение задачи для произвольных графов) |
||
| Строка 9: | Строка 9: | ||
== Обобщение задачи для произвольных графов == | == Обобщение задачи для произвольных графов == | ||
| − | Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. | + | Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. |
| + | Попробуем выполнить операцию удаления ребра.--- Для этого ----> | ||
| − | + | [[Файл:Graph.jpg|550px|thumb|left|Граф]] [[Файл:Spanforest.jpg|550px|thumb|right|Остовный лес в графе]] | |
| − | |||
| Строка 31: | Строка 31: | ||
| − | + | ===connected(u,v)=== | |
| + | Граф и его остовный лес {{---}} одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex>.<!--Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.--> | ||
| − | Очевидно, что <tex>G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0</tex>. Выделим в | + | ===add(u,v)=== |
| + | Для того чтобы разобраться с поведением графа при добавлении и удалении ребра, введём функцию <tex>l(e):E{\rightarrow}[0;\log n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, но для всех <tex> i </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i=\langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}</tex>. | ||
| + | |||
| + | Очевидно, что <tex>G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0 = G</tex>. Выделим в графах остовные леса таким образом, что <tex>F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>. | ||
| + | |||
| + | Новому ребру всегда удобно дать уровень <tex>0</tex>. В этом случае изменится только <tex>G_0</tex>, так как в остальные подграфы <tex>G_i</tex> рёбра нулевого уровня не входят. Затем нам нужно проверить, были ли эти вершины в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и в остовный лес. | ||
| + | |||
| + | ===remove(u,v)=== | ||
[[Файл:Another_edge.jpg|200px|thumb|right]] | [[Файл:Another_edge.jpg|200px|thumb|right]] | ||
| − | При удалении возможны случаи: | + | |
| + | <!----При удалении возможны случаи: | ||
* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части (назовём их <tex>T(u)</tex> и <tex>T(v)</tex>), и задача решается как для дерева за <tex>O(\log n)</tex>. | * '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части (назовём их <tex>T(u)</tex> и <tex>T(v)</tex>), и задача решается как для дерева за <tex>O(\log n)</tex>. | ||
* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях). Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру. | * '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях). Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру. | ||
| Строка 43: | Строка 52: | ||
Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(uv)</tex>, затем <tex>l(uv)-1</tex>, <tex>l(uv)-2</tex><tex>\ldots</tex>. Рассматривать будем меньшую из частей (будем считать, что <tex>|T(u)|\leqslant|T(v)|</tex>, в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что <tex>uv</tex> не мост. Иначе увеличиваем уровень ребра, чтобы заново к нему не обращаться или уменьшаем уровень и повторяем процедуру. Суммарная сложность сканирования рёбер будет <tex>O(|T(u)|\cdot\log n)</tex>, так как в худшем случае мы проверяем каждую вершину из <tex>T(u)</tex>, а уровень ребра не превосходит <tex>\log n</tex>. | Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(uv)</tex>, затем <tex>l(uv)-1</tex>, <tex>l(uv)-2</tex><tex>\ldots</tex>. Рассматривать будем меньшую из частей (будем считать, что <tex>|T(u)|\leqslant|T(v)|</tex>, в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что <tex>uv</tex> не мост. Иначе увеличиваем уровень ребра, чтобы заново к нему не обращаться или уменьшаем уровень и повторяем процедуру. Суммарная сложность сканирования рёбер будет <tex>O(|T(u)|\cdot\log n)</tex>, так как в худшем случае мы проверяем каждую вершину из <tex>T(u)</tex>, а уровень ребра не превосходит <tex>\log n</tex>. | ||
| − | Общее время удаления одного ребра не превосходит <tex>O(\log^2{n}+S\cdot\log n)</tex>, где <tex>S</tex> {{---}} число неудачных просмотров ребра <tex>xy</tex>, а для всех <tex>m</tex> запросов получаем <tex>O(\log^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S}) \leqslant O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m) = O(2\cdot\log^2{n}\cdot m)</tex>, поэтому для одного запроса будем иметь время <tex>O(\log^2{n})</tex>. | + | Общее время удаления одного ребра не превосходит <tex>O(\log^2{n}+S\cdot\log n)</tex>, где <tex>S</tex> {{---}} число неудачных просмотров ребра <tex>xy</tex>, а для всех <tex>m</tex> запросов получаем <tex>O(\log^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S}) \leqslant O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m) = O(2\cdot\log^2{n}\cdot m)</tex>, поэтому для одного запроса будем иметь время <tex>O(\log^2{n})</tex>.---------> |
== См. также == | == См. также == | ||
Версия 20:07, 13 января 2018
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
Содержание
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — .
Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим остовные деревья, которые образуют остовный лес. Попробуем выполнить операцию удаления ребра.--- Для этого ---->
connected(u,v)
Граф и его остовный лес — одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за .
add(u,v)
Для того чтобы разобраться с поведением графа при добавлении и удалении ребра, введём функцию и назовём её уровнем ребра . Уровни ребра можно распределить любым способом, но для всех должно выполняться следующее свойство: размер каждой компоненты связности не превосходит . Здесь графы определяются так: .
Очевидно, что . Выделим в графах остовные леса таким образом, что , где — остовный лес графа .
Новому ребру всегда удобно дать уровень . В этом случае изменится только , так как в остальные подграфы рёбра нулевого уровня не входят. Затем нам нужно проверить, были ли эти вершины в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и в остовный лес.
remove(u,v)
