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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
Если задача такова, что в графе нет и не может быть циклов, то её можно решить при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Нужно только... [[Dynamic connectivity|читать продолжение в источнике]].
 
Если задача такова, что в графе нет и не может быть циклов, то её можно решить при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Нужно только... [[Dynamic connectivity|читать продолжение в источнике]].
  
−
Время работы для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
+
Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
 
== Обобщение задачи для произвольных графов ==
 
== Обобщение задачи для произвольных графов ==
−
написать про уровни и остовные леса
+
написать про уровни и остовные леса <tex>\mathrm{navernoe.}</tex>
 
<!-- === Псевдокод === xz -->
 
<!-- === Псевдокод === xz -->
 
<!--== Алгоритм ==
 
<!--== Алгоритм ==
Строка 55: Строка 55:
  
 
=== Частные случаи ===
 
=== Частные случаи ===
−
 
−
# Деревья. Для таких графов задачу можно решать при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за <tex>O(\log n)</tex>.
 
 
# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>.
 
# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>.
 
-->
 
-->

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


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

Если задача такова, что в графе нет и не может быть циклов, то её можно решить при помощи деревьев эйлерова обхода. Нужно только... читать продолжение в источнике.

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

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

написать про уровни и остовные леса [math]\mathrm{navernoe.}[/math]


См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_динамической_связности&oldid=63383»