Полностью динамический алгоритм достижимости с единственным источником: различия между версиями

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

• ''insert(u,v)'': вставка дуги (u, v) в граф;

• ''delete(u,v)'': удаление дуги (u, v) из графа;

• ''reachable(x,y)'': возвращает true, если существует ориентированный путь между вершинами x и y, и false в противном случае.

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

• ''insert(u,v)'': вставка дуги (u, v) в граф;

• ''delete(u,v)'': удаление дуги (u, v) из графа;

• ''reachable(y)'': возвращает true, если существует ориентированный путь между вершиной-источником s и вершиной y, и false в противном случае.

Еще одним простым решением является ответ на запросы путем поточечного вычисления достижимости, без необходимости сохранении явной информации о достижимости после каждой вставки или удаления. Это можно выполнить за время O(m + n) при помощи любого алгоритма обхода графа. Подобный подход позволяет давать ответы на запросы за время O(m + n) и выполнять обновления за константное время. Заметим, что при использовании обоих подходов время выполнения самой медленной операции составляет O(m + n), что для плотных графов доходит до <math>O(n^2) \;</math>.

Первым улучшением по сравнению с двумя базовыми решениями стал алгоритм Деметреску и Итальяно, которые показали, как поддерживать операции обновления за время O(n^{1,575}), а запросы о достижимости – за время O(1) [1] в ориентированном ациклическом графе. Их результат основывается на простой редукции решения для задачи с единственным источником до задачи для всех пар. Используя результат Санковски [2], можно расширить вышеприведенные границы для общего случая ориентированных графов.