Задача о динамической связности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обобщение задачи для произвольных графов)
(Обобщение задачи для произвольных графов)
Строка 9: Строка 9:
 
== Обобщение задачи для произвольных графов ==
 
== Обобщение задачи для произвольных графов ==
  
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\mathrm{\log}n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.
+
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.
  
 
Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. Граф и его остовный лес {{---}} одно и то же с точки зрения связности.
 
Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. Граф и его остовный лес {{---}} одно и то же с точки зрения связности.
Строка 31: Строка 31:
  
  
Введём функцию <tex>l(e):e{\rightarrow}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, но должно выполняться следующее свойство: <tex> \forall i </tex> размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i=\langle V, E\rangle: \{E \mid l(E) \geqslant i\}</tex>. Очевидно, что <tex>G_{\mathrm{\log}n} \subseteq G_{\mathrm{\log}n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0</tex>. Выделим в них остовные леса таким образом, что <tex>F_{\mathrm{\log}n} \subseteq F_{\mathrm{\log}n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>.
+
Введём функцию <tex>l(e):e{\rightarrow}[0;\log n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, но должно выполняться следующее свойство: <tex> \forall i </tex> размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i=\langle V, E\rangle: \{E \mid l(E) \geqslant i\}</tex>. Очевидно, что <tex>G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0</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>.
  
 
[[Файл:Another_edge.jpg|200px|thumb|right]]
 
[[Файл:Another_edge.jpg|200px|thumb|right]]
  
 
При удалении возможны случаи:
 
При удалении возможны случаи:
* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части (назовём их <tex>T(u)</tex> и <tex>T(v)</tex>), и задача решается как для дерева за <tex>O(\mathrm{\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> принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
  
Осталось проверить, является ли ребро мостом. Будем искать ребро <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)|\mathrm{\log}n)</tex>, так как в худшем случае мы проверяем каждую вершину из <tex>T(u)</tex>, а уровень ребра не превосходит <tex>\mathrm{\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)|\log n)</tex>, так как в худшем случае мы проверяем каждую вершину из <tex>T(u)</tex>, а уровень ребра не превосходит <tex>\log n</tex>.
  
Общее время удаления одного ребра не превосходит <tex>O(\mathrm{\log}^2{n}+S\cdot\mathrm{\log}n)</tex>, где <tex>S</tex> {{---}} число неудачных просмотров ребра <tex>xy</tex>, а для всех <tex>m</tex> запросов получаем <tex>O(\mathrm{\log}^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S}) \leqslant O(\mathrm{\log}^2{n} \cdot m+\mathrm{\log}n\cdot\mathrm{\log}n\cdot m) = O(2\cdot\mathrm{\log}^2{n}\cdot m)</tex>, поэтому для одного запроса будем иметь время <tex>O(\mathrm{\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>.
  
 
== См. также ==
 
== См. также ==

Версия 22:20, 12 января 2018

Задача:
Есть неориентированный граф из [math]n[/math] вершин, изначально не содержащий рёбер. Требуется обработать [math]m[/math] запросов трёх типов:
  • [math]\mathrm{add(u,v)}[/math] — добавить ребро между вершинами [math]u[/math] и [math]v[/math];
  • [math]\mathrm{remove(u,v)}[/math] — удалить ребро между вершинами [math]u[/math] и [math]v[/math];
  • [math]\mathrm{connected(u,v)}[/math] — проверить, лежат ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности.

Динамическая связность в лесах

Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — [math]O(\log n)[/math].

Обобщение задачи для произвольных графов

Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения системы непересекающихся множеств, такой запрос будет работать за [math]O(\log n)[/math]. Операция проверки сводится к проверке связности в остовном лесе и работает также за [math]O(\log n)[/math].

Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим остовные деревья, которые образуют остовный лес. Граф и его остовный лес — одно и то же с точки зрения связности.

Произвольный граф
Остовный лес в графе









Введём функцию [math]l(e):e{\rightarrow}[0;\log n][/math] и назовём её уровнем ребра [math]e[/math]. Уровни ребра можно распределить любым способом, но должно выполняться следующее свойство: [math] \forall i [/math] размер каждой компоненты связности [math]G_i[/math] не превосходит [math]\dfrac{n}{2^i}[/math]. Здесь графы [math]G_i[/math] определяются так: [math]G_i=\langle V, E\rangle: \{E \mid l(E) \geqslant i\}[/math]. Очевидно, что [math]G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0[/math]. Выделим в них остовные леса таким образом, что [math]F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0[/math], где [math]F_i[/math] — остовный лес графа [math]G_i[/math].

Another edge.jpg

При удалении возможны случаи:

  • Удаляемое ребро является мостом. В этом случае дерево распадается на две части (назовём их [math]T(u)[/math] и [math]T(v)[/math]), и задача решается как для дерева за [math]O(\log n)[/math].
  • Удаляемое ребро не является мостом. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины [math]u[/math] и [math]v[/math] лежат в разных частях). Если [math]uv[/math] принадлежало нашему лесу, то передаём эту "функцию" новому ребру.

Осталось проверить, является ли ребро мостом. Будем искать ребро [math]xy[/math] на уровне [math]l(uv)[/math], затем [math]l(uv)-1[/math], [math]l(uv)-2[/math][math]\ldots[/math]. Рассматривать будем меньшую из частей (будем считать, что [math]|T(u)|\leqslant|T(v)|[/math], в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что [math]uv[/math] не мост. Иначе увеличиваем уровень ребра, чтобы заново к нему не обращаться или уменьшаем уровень и повторяем процедуру. Суммарная сложность сканирования рёбер будет [math]O(|T(u)|\log n)[/math], так как в худшем случае мы проверяем каждую вершину из [math]T(u)[/math], а уровень ребра не превосходит [math]\log n[/math].

Общее время удаления одного ребра не превосходит [math]O(\log^2{n}+S\cdot\log n)[/math], где [math]S[/math] — число неудачных просмотров ребра [math]xy[/math], а для всех [math]m[/math] запросов получаем [math]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)[/math], поэтому для одного запроса будем иметь время [math]O(\log^2{n})[/math].

См. также

Источники информации