Полностью динамические минимальные остовные деревья

Ключевые слова и синонимы

Динамические минимальные остовные леса

Постановка задачи

Пусть G = (V, E) – неориентированный взвешенный граф. Рассматривается задача эффективной поддержки информации о минимальном остовном дереве графа G (либо минимальном остовном лесе, если G не является связным), подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен выполнять операции обновления быстрее, чем вычислять полное минимальное остовное дерево с нуля.

Алгоритм называется полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление.

Основные результаты

Алгоритм поддержки динамического минимального остовного леса основан на алгоритме динамической связности, приведенном в статье «Полностью динамическая связность». После нескольких небольших модификаций алгоритм позволяет поддерживать минимальный остовный лес взвешенного неориентированного графа в присутствии исключительно операций удаления ребер [13]. Затем может быть применена редукция из [11], позволяющая сделать алгоритм с удалением ребер полностью динамическим.

Вначале опишем декрементный алгоритм, поддерживающий минимальный остовный лес в присутствии исключительно операций удаления ребер. На протяжении последовательности операций удаления алгоритм поддерживает остовный лес F на динамически меняющемся графе G. Ребра, принадлежащие F, называются древесными ребрами; остальные ребра (из G – F) называются недревесными ребрами. Пусть e – удаляемое ребро. Если ребро e является недревесным, то минимальный остовный лес не меняется. Остается рассмотреть случай, когда ребро e является древесным ребром леса F. Пусть T – дерево леса F, содержащее e. В этом случае удаление ребра e разбивает дерево T на два поддерева – [math]\displaystyle{ T_1 \; }[/math] и [math]\displaystyle{ T_2 \; }[/math]. Для обновления минимального остовного леса необходимо найти ребро с минимальным весом, одна конечная точка которого принадлежит дереву [math]\displaystyle{ T_1 \; }[/math], а другая - дереву [math]\displaystyle{ T_2 \; }[/math]. Такое ребро называется ребром замены для e.

Для выполнения поиска ребер замены алгоритм динамической связности присваивает каждому ребру e уровень [math]\displaystyle{ \ell (e) \; }[/math] и на основе этих уровней поддерживает множество под-лесов минимального остовного дерева F: для каждого уровня i лес [math]\displaystyle{ F_i \; }[/math] является под-лесом, порожденным древесными ребрами уровня выше или равного i. Обозначив за L максимальный уровень ребра, получаем следующее:

[math]\displaystyle{ F = F_0 \supseteq F_1 \supseteq F_2 \supseteq ... \supseteq F_L. }[/math]

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

Инвариант (1): F – максимальный остовный лес графа G, если уровни ребер интерпретировать как их веса.

Инвариант (2): Число вершин каждого дерева [math]\displaystyle{ F_i }[/math] не превышает [math]\displaystyle{ n/2^i \; }[/math].

Инвариант (3): Каждый цикл C содержит недревесное ребро с максимальным весом и минимальным уровнем среди всех ребер C.

Инвариант (1) следует интерпретировать следующим образом. Пусть [math]\displaystyle{ (u, v) \; }[/math] – недревесное ребро уровня [math]\displaystyle{ \ell (u, v) \; }[/math]; пусть [math]\displaystyle{ u \cdot \cdot \cdot v \; }[/math] – уникальный путь между u и v в F (такой путь существует, поскольку F является остовным лесом графа G). Пусть e – любое ребро из пути [math]\displaystyle{ u \cdot \cdot \cdot v \; }[/math], а [math]\displaystyle{ \ell (e) \; }[/math] – уровень этого ребра. В силу инварианта (1), [math]\displaystyle{ \ell (e) \ge \ell (u, v) \; }[/math]. Поскольку это выполняется для каждого ребра пути, а по построению [math]\displaystyle{ F_{\ell(u, v)} }[/math] содержит все древесные ребра уровня более или равного [math]\displaystyle{ \ell (u, v) \; }[/math], то весь путь содержится в [math]\displaystyle{ F_{\ell(u, v)} }[/math]; иначе говоря, u и v являются связанными в [math]\displaystyle{ F_{\ell(u, v)} }[/math].

Из инварианта (2) следует, что максимальное число уровней равно [math]\displaystyle{ L \le \mathcal {b} log_2 \; n \mathcal {c} }[/math].

Инвариант (3) может использоваться для доказательства утверждения, что среди всех ребер замены ребро с минимальным весом будет находиться на максимальном уровне. Пусть [math]\displaystyle{ e_1 \; }[/math] и [math]\displaystyle{ e_2 \; }[/math] – два ребра замены с [math]\displaystyle{ w(e_1) \lt w(e_2) \; }[/math]; пусть [math]\displaystyle{ C_i \; }[/math] – цикл, порожденный [math]\displaystyle{ e_i \; }[/math] в F, i = 1, 2. Поскольку F – минимальный остовный лес, [math]\displaystyle{ e_i \; }[/math] имеет максимальный вес среди всех ребер в [math]\displaystyle{ C_i \; }[/math]. В частности, поскольку, согласно предположению, [math]\displaystyle{ w(e_1) \lt w(e_2) \; }[/math], [math]\displaystyle{ e_2 \; }[/math] также имеет максимальный вес среди ребер в цикле [math]\displaystyle{ C = (C_1 \cup C_2) \setminus (C_1 \cap C_2) }[/math]. В силу инварианта (3), ребро [math]\displaystyle{ e_2 \; }[/math] имеет минимальный уровень в C, что доказывает, что [math]\displaystyle{ \ell (e_2) \le \ell (e_1) \; }[/math]. Таким образом, рассмотрение недревесных ребер от максимального до минимального уровня является корректным.

Заметим, что вначале ребру присваивается уровень 0. Затем его уровень может быть увеличен не более [math]\displaystyle{ \mathcal {b} log_2 \; n \mathcal {c} }[/math] раз вследствие последовательности удалений ребер. Когда удаляется ребро e = (v, w) уровня [math]\displaystyle{ \ell (e) \; }[/math], алгоритм ищет ребро замены с максимально высоким уровнем, если такое существует. В силу инварианта (1) такое ребро замены имеет уровень [math]\displaystyle{ \ell \le \ell (e) \; }[/math]. Следовательно, процедура замены [math]\displaystyle{ Replace((u, w), \ell (e)) \; }[/math] вызывается с параметрами [math]\displaystyle{ e \; }[/math] и [math]\displaystyle{ \ell (e) \; }[/math]. Далее будут вкратце описаны операции, выполняемые этой процедурой.

[math]\displaystyle{ Replace((u, w), \ell (e)) \; }[/math] находит ребро замены самого высокого уровня, не превышающего [math]\displaystyle{ \ell \; }[/math], если такое существует, рассматривая ребра в порядке увеличения веса. Если на уровне [math]\displaystyle{ \ell \; }[/math] такого ребра не существует, имеет место один из двух вариантов: если [math]\displaystyle{ \ell \gt 0 \; }[/math], алгоритм рекурсивно переходит на уровень [math]\displaystyle{ \ell - 1 \; }[/math]; в противном случае [math]\displaystyle{ \ell = 0 \; }[/math], и удаление ребра (v, w) разделяет деревья v и w в графе G.

Можно показать, что функция [math]\displaystyle{ Replace \; }[/math] возвращает ребро замены с минимальным весом максимально возможного уровня, что обосновывает следующую лемму:

Лемма 1. Существует алгоритм поддержки минимального остовного леса, выполняющий только удаление ребер, который может быть инициализирован на графе с n вершинами и m ребрами и который поддерживает любую последовательность удалений ребер за полное время [math]\displaystyle{ O(m \; log^2 \; n) }[/math].

Теперь перейдем к описанию полностью динамического алгоритма, выполняющего обновления за время [math]\displaystyle{ O(log^4 \; n) }[/math]. Редукция, используемая для получения полностью динамического алгоритма, представляет собой небольшое обобщение подхода, предложенного Хенцингер и Кинг [11].

Лемма 2. Предположим, что существует алгоритм поддержки минимального остовного дерева, выполняющий только удаление ребер, который для любых значений [math]\displaystyle{ k \; }[/math] и [math]\displaystyle{ \ell \; }[/math] может быть инициализирован на графе с [math]\displaystyle{ k \; }[/math] вершинами и [math]\displaystyle{ \ell \; }[/math] ребрами и который поддерживает любую последовательность из [math]\displaystyle{ \Omega ( \ell ) \; }[/math] удалений за полное время [math]\displaystyle{ O( \ell \cdot t(k, \ell)) \; }[/math], где t – неубывающая функция. Тогда существует полностью динамический алгоритм поддержки минимального остовного дерева для графа с n вершинами, начинающий работу с нулевого числа ребер, который для m ребер поддерживает обновления за время

[math]\displaystyle{ O \Bigg( log^3 \; n + \sum_{i=1}^{3+log_2 \; m} \sum_{j=1}^i t \; \big( min \{ n, 2^j \}, 2^j \big) \Bigg) }[/math].

Описание конструкции, необходимой для доказательства леммы 2, можно найти в работах [11] и [13]. Из леммы 1 получаем [math]\displaystyle{ t(k, \ell) = O(log^2 \; k) }[/math]. Комбинируя леммы 1 и 2, получаем следующий результат:

Теорема 3. Существует полностью динамический алгоритм поддержки минимального остовного леса, который для графа с n вершинами, начиная работу с нулевого числа ребер, поддерживает минимальный остовный лес за амортизированное время [math]\displaystyle{ O(log^4 \; n) }[/math] на вставку или удаление ребра.

Нижняя граница [math]\displaystyle{ \Omega (log \; n) }[/math] для динамического минимального остовного дерева, предложенная Эппстайном и коллегами [6], использует следующее рассуждение. Пусть A – алгоритм, поддерживающий минимальное остовное дерево произвольного (мульти)графа G; такой, что функция изменения веса [math]\displaystyle{ weight(e; \Delta) \; }[/math] возвращает ребро f, заменяющее ребро e в минимальном остовном дереве, если e подлежит замене. Очевидно, что любой динамический алгоритм поддержки остовного дерева можно модифицировать так, чтобы он возвращал f. Можно использовать алгоритм A для сортировки n положительных чисел [math]\displaystyle{ x_1, x_2, ... , x_n \; }[/math] следующим образом. Построим мультиграф G, состоящий из двух вершин, связанных (n + 1) ребрами [math]\displaystyle{ e_0, e_1, ... , e_n \; }[/math], такими, что ребро [math]\displaystyle{ e_0 \; }[/math] имеет вес [math]\displaystyle{ 0 \; }[/math], а ребро [math]\displaystyle{ e_i \; }[/math] имеет вес [math]\displaystyle{ x_i \; }[/math]. Первоначальное остовное дерево будет соответствовать [math]\displaystyle{ e_0 \; }[/math]. Увеличим вес [math]\displaystyle{ e_0 \; }[/math] до [math]\displaystyle{ + \infty \; }[/math]. Ребро, которое заменит [math]\displaystyle{ e_0 \; }[/math] (положим, [math]\displaystyle{ e_i \; }[/math]), будет ребром с минимальным весом. Теперь увеличим вес [math]\displaystyle{ e_i \; }[/math] до [math]\displaystyle{ + \infty \; }[/math]; замена [math]\displaystyle{ e_i \; }[/math] будет иметь второй по счету минимальный вес. Продолжая этот процесс, получим числа в возрастающем порядке. Подобные же рассуждения можно привести для случая постоянного уменьшения весов ребер. После того, как Пол и Саймон [14] показали, что любому алгоритму сортировки требуется время [math]\displaystyle{ \Omega (n \; log \; n) }[/math] для сортировки n чисел на RAM-машине с единичной стоимостью, способной выполнять операции сложения, вычитания, умножения и сравнения с нулем, но не поддерживающей деление и поразрядные булевы операции, была сформулирована следующая теорема.

Теорема 4. Любому алгоритму на RAM-машине с единичной стоимостью, способной выполнять операции сложения, вычитания, умножения и сравнения с нулем, но не поддерживающей деление и поразрядные булевы операции, для динамической поддержки минимального остовного дерева требуется амортизированное время [math]\displaystyle{ \Omega (log \; n) }[/math] на операцию.

Применение

Минимальные остовные деревья находят применение во многих областях, включая проектирование сетей, СБИС и геометрическую оптимизацию, и в этих приложениях возникает задача динамической поддержки минимальных остовных деревьев.

Алгоритмы поддержки минимального остовного леса графа могут также использоваться для поддержки информации о связных компонентах графа. Среди других вариантов применения алгоритмов динамических минимальных остовных деревьев можно упомянуть поиск k наименьших остовных деревьев [3, 4, 5, 8, 9], выборку остовных деревьев [7] и динамическую задачу о пересечении матроидов [10]. Первые две задачи не обязательно являются динамическими; однако для их эффективного решения необходимы динамические структуры данных.

Открытые вопросы

Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами в динамической задаче минимального остовного дерева. Заметим, что это возможно для специального случая планарных графов [6].

Во-вторых, техники поддержки динамических минимальных остовных деревьев могут быть расширены на задачи 2-реберной и 2-вершинной связности, которые могут быть решены за полилогарифмическое время на одно обновление. Можно ли распространить эту технику на более высокие размерности связности? Это особенно важно, поскольку наилучшие известные границы обновления для более высоких степеней реберной и вершинной связности являются полиномиальными, и было бы очень полезно разработать полилогарифмические алгоритмы хотя бы для полностью динамических задач 3-реберной и 3-вершинной связности.

См. также

• Динамические деревья
• Полностью динамический алгоритм нахождения кратчайших путей между всеми парами
• Полностью динамическая связность
• Полностью динамическая связность высоких степеней
• Полностью динамическая связность высоких степеней в планарных графах
• Полностью динамическая проверка на планарность
• Полностью динамический алгоритм транзитивного замыкания

Литература

1. Alberts, D., Cattaneo, G., Italiano, G.F.: An empirical study of dynamic graph algorithms. ACM. J. Exp. Algorithm 2, (1997)

2. Cattaneo, G., Faruolo, P., Ferraro Petrillo, U., Italiano, G.F.: Maintaining Dynamic Minimum Spanning Trees: An Experimental Study. In: Proceeding 4th Workshop on Algorithm Engineering and Experiments (ALENEX 02), 6-8 Jan 2002. pp. 111 -125

3. Eppstein, D.: Finding the k smallest spanning trees. BIT. 32, 237-248(1992)

4. Eppstein, D.: Tree-weighted neighbors and geometric k smallest spanning trees. Int. J. Comput. Geom. Appl. 4, 229-238 (1994)

5. Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. Assoc. Comput. Mach. 44(5), 669-696 (1997)

6. Eppstein, D., Italiano, G.F.,Tamassia, R.,Tarjan,R.E., Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algorithms 13, 33-54 (1992)

7. Feder, T., Mihail, M.: Balanced matroids. In: Proceeding 24th ACM Symp. Theory of Computing, pp 26-38, Victoria, British Columbia, Canada, May 04-06 1992

8. Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees. SIAM. J. Comput. 14, 781-798 (1985)

9. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In: Proceeding 32nd Symp. Foundations of Computer Science, pp 632-641, San Juan, Puerto Rico, October 01-04 1991

10. Frederickson, G.N., Srinivas, M.A.: Algorithms and data structures for an expanded family of matroid intersection problems. SIAM. J. Comput. 18,112-138 (1989)

11. Henzinger, M.R., King, V.: Maintaining minimum spanning forests in dynamic graphs. SIAM. J. Comput. 31(2), 364-374 (2001)

12. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4),502-516(1999)

13. Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48,723-760 (2001)

14. Paul, J., Simon, W.: Decision trees and random access machines. In: Symposium Ciber Logikund Algorithmik. (1980) See also Mehlhorn, K.: Sorting and Searching, pp. 85-97. Springer, Berlin (1984)

15. Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM. J. Comput. 14,862-874 (1985)