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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обобщение задачи для произвольных графов)
(Обобщение задачи для произвольных графов)
Строка 31: Строка 31:
  
  
Введём функцию <tex>l(e):e{\rightarrow}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра''. Будем рассматривать графы <tex>G_i={e|l(e) \geqslant i}<\tex>
+
Введём функцию <tex>l(e):e{\rightarrow}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра'' <tex>e<\tex>. Будем рассматривать графы <tex>G_i=<tex>\langle V, E\rangle</tex>{E|l(E) \geqslant i}<\tex>
  
 
<!--При выполнении операции add  что-то хорошее, а с удалением не всё так просто.-->
 
<!--При выполнении операции add  что-то хорошее, а с удалением не всё так просто.-->

Версия 23:46, 7 января 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]l(e):e{\rightarrow}[0;\mathrm{\log} n][/math] и назовём её уровнем ребра [math]e\lt \tex\gt . Будем рассматривать графы \lt tex\gt G_i=\lt tex\gt \langle V, E\rangle[/math]{E|l(E) \geqslant i}<\tex>


См. также

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