4511
правок
Полностью динамическая связность высоких степеней: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамическая связность высоких степеней (посмотреть исходный код)
Версия от 22:48, 14 июля 2014
, 14 июля 2014→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве | Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку дуг, так и удаление дуг. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление дуг; [[инкрементный алгоритм]] поддерживает только вставку дуг, [[декрементный алгоритм|декрементный]] – только удаление. | ||
В полностью динамической задаче k-реберной связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке: | |||
• k-EdgeConnected(u, v): возвращает значение «истинно», если вершины u и v принадлежат к одной и той же k-реберно-связной компоненте графа, в противном случае возвращает значение «ложно». | • k-EdgeConnected(u, v): возвращает значение «истинно», если вершины u и v принадлежат к одной и той же k-реберно-связной компоненте графа, в противном случае возвращает значение «ложно». | ||