Компромиссы при решении динамических графовых задач: различия между версиями

Определение 1 (Динамический алгоритм на графе). Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке:

Алгоритм на графе является полностью динамическим, если он поддерживает как вставку ребер, так и удаление, и частично динамическим, если поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. В некоторых работах исследуются варианты этой задачи, допускающие вставку или удаление более чем одного ребра за один раз либо позволяющие изменять веса ребер. В некоторых случаях обновление может заключаться во вставке или удалении вершины вместе со всеми инцидентными ей ребрами. В других исследованиях рассматриваются только определенные классы графов - например, планарные графы или ориентированные ациклические графы.

Динамическим алгоритмам на графе посвящено множество работ. В числе графовых задач, для которых разработаны эффективные динамические алгоритмы, можно упомянуть задачи о [[Связность|связности графа]], о минимальном [[Разрез|разрезе]], [[Минимальное остовное дерево|минимальном остовном дереве]], [[Полностью динамическое транзитивное замыкание|транзитивном замыкании]] и [[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами|нахождении кратчайших путей]] (см., например, [3] и ссылки в этой работе). Многие из них выполняют явное обновление свойства P после каждого обновления графа, чтобы отвечать на запросы за оптимальное время. Этот вариант подходит для случаев, когда обновлений мало, а запросов – много. В приложениях со сравнимым числом обновлений и запросов более эффективным подходом будет попытка уменьшить время обновления – возможно, ценой увеличения времени выполнения запроса. Это обычно достигается при помощи ослабления предположения о том, что свойство P следует поддерживать явным образом.

Определение 2 (Полностью динамическая задача о транзитивном замыкании). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:

Определение 3 (Полностью динамическая задача нахождения кратчайших путей между всеми парами). Задача заключается в поддержке взвешенного ориентированного графа и выполнении последовательности следующих операций в различном порядке: