4640
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 13:51, 12 июля 2014
, 12 июля 2014→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача заключается в эффективной поддержке информации о связности в динамически меняющемся графе. Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется полностью динамическим, если он поддерживает как вставку дуг, так и удаление дуг. Частично динамический алгоритм поддерживает либо вставку, либо удаление дуг; инкрементный алгоритм поддерживает только вставку дуг, декрементный – только удаление. | Задача заключается в эффективной поддержке информации о связности в динамически меняющемся графе. Динамический алгоритм на графе поддерживает заданное свойство <math>\mathcal{P}</math> графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве <math>\mathcal{P}</math>, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку дуг, так и удаление дуг. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление дуг; [[инкрементный алгоритм]] поддерживает только вставку дуг, [[декрементный алгоритм|декрементный]] – только удаление. | ||
В задаче полностью динамической связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке: | В задаче полностью динамической связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке: | ||
'''Connected(u, v)''': возвращает значение «истинно», если вершины u и v принадлежат к одной и той же связной компоненте графа, в противном случае возвращает значение «ложно». | |||
'''Insert(x, y)''': вставляет новую дугу между вершинами x и y. | |||
'''Delete'''(x, y): удаляет дугу между вершинами x и y. | |||
== Основные результаты == | == Основные результаты == | ||
