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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обобщение задачи для произвольных графов)
(Обобщение задачи для произвольных графов)
Строка 34: Строка 34:
  
 
Введём функцию <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>.
 +
 +
[[Файл:Another_edge.png|200px|right]]
  
 
При удалении возможны случаи:
 
При удалении возможны случаи:
Строка 39: Строка 41:
 
* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях. Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
 
* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях. Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
  
Осталось проверить, является ли ребро мостом.
+
Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(xy) \ leqslant l(uv)</tex>.
 +
 
  
 
<!-- я лошара) -->
 
<!-- я лошара) -->

Версия 00:51, 8 января 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] в одной компоненте связности.

В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.

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

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

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

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

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

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









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

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

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

Осталось проверить, является ли ребро мостом. Будем искать ребро [math]xy[/math] на уровне [math]l(xy) \ leqslant l(uv)[/math].


См. также

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