4430
правок
Полностью динамические минимальные остовные деревья: различия между версиями
Материал из WEGA
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 11:31, 19 июня 2018
, 19 июня 2018→См. также
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 7: | Строка 7: | ||
Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку ребер, так и удаление ребер. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление ребер; [[инкрементный алгоритм]] поддерживает только вставку ребер, [[декрементный алгоритм|декрементный]] – только удаление. | Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку ребер, так и удаление ребер. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление ребер; [[инкрементный алгоритм]] поддерживает только вставку ребер, [[декрементный алгоритм|декрементный]] – только удаление. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 47: | Строка 48: | ||
'''Лемма 2. Предположим, что существует алгоритм поддержки минимального остовного дерева, выполняющий только удаление ребер, который для любых значений <math>k \; </math> и <math>\ell \;</math> может быть инициализирован на графе с <math>k \; </math> вершинами и <math>\ell \;</math> ребрами и который поддерживает любую последовательность из <math>\Omega ( \ell | '''Лемма 2. Предположим, что существует алгоритм поддержки минимального остовного дерева, выполняющий только удаление ребер, который для любых значений <math>k \; </math> и <math>\ell \;</math> может быть инициализирован на графе с <math>k \; </math> вершинами и <math>\ell \;</math> ребрами и который поддерживает любую последовательность из <math>\Omega ( \ell ) \;</math> удалений за полное время <math>O( \ell \cdot t(k, \ell)) \;</math>, где t – неубывающая функция. Тогда существует полностью динамический алгоритм поддержки минимального остовного дерева для графа с n вершинами, начинающий работу с нулевого числа ребер, который для m ребер поддерживает обновления за время''' | ||
<math>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>. | <math>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 получаем t(k, | Описание конструкции, необходимой для доказательства леммы 2, можно найти в работах [11] и [13]. Из леммы 1 получаем <math>t(k, \ell) = O(log^2 \; k)</math>. Комбинируя леммы 1 и 2, получаем следующий результат: | ||
'''Теорема 3. Существует полностью динамический алгоритм поддержки минимального остовного леса, который для графа с n вершинами, начиная работу с нулевого числа ребер, поддерживает минимальный остовный лес за амортизированное время <math>O(log^4 \; n)</math> на вставку или удаление ребра.''' | |||
Нижняя граница <math>\Omega (log \; n)</math> для динамического минимального остовного дерева, предложенная Эппстайном и коллегами [6], использует следующее рассуждение. Пусть A – алгоритм, поддерживающий минимальное остовное дерево произвольного ([[мультиграф|мульти]])графа G; такой, что функция изменения веса <math>weight(e; \Delta) \; </math> возвращает ребро f, заменяющее ребро e в минимальном остовном дереве, если e подлежит замене. Очевидно, что любой динамический алгоритм поддержки остовного дерева можно модифицировать так, чтобы он возвращал f. Можно использовать алгоритм A для сортировки n положительных чисел <math>x_1, x_2, ... , x_n \; </math> следующим образом. Построим мультиграф G, состоящий из двух вершин, связанных (n + 1) ребрами <math>e_0, e_1, ... , e_n \; </math>, такими, что ребро <math>e_0 \; </math> имеет вес <math>0 \;</math>, а ребро <math>e_i \; </math> имеет вес <math>x_i \; </math>. Первоначальное остовное дерево будет соответствовать <math>e_0 \;</math>. Увеличим вес <math>e_0 \;</math> до <math>+ \infty \;</math>. Ребро, которое заменит <math>e_0 \;</math> (положим, <math>e_i \;</math>), будет ребром с минимальным весом. Теперь увеличим вес <math>e_i \;</math> до <math>+ \infty \;</math>; замена <math>e_i \;</math> будет иметь второй по счету минимальный вес. Продолжая этот процесс, получим числа в возрастающем порядке. Подобные же рассуждения можно привести для случая постоянного уменьшения весов ребер. После того, как Пол и Саймон [14] показали, что любому алгоритму сортировки требуется время <math>\Omega (n \; log \; n)</math> для сортировки n чисел на RAM-машине с единичной стоимостью, способной выполнять операции сложения, вычитания, умножения и сравнения с нулем, но не поддерживающей деление и поразрядные булевы операции, была сформулирована следующая теорема. | |||
'''Теорема 4. Любому алгоритму на RAM-машине с единичной стоимостью, способной выполнять операции сложения, вычитания, умножения и сравнения с нулем, но не поддерживающей деление и поразрядные булевы операции, для динамической поддержки минимального остовного дерева требуется амортизированное время <math>\Omega (log \; n)</math> на операцию.''' | |||
== Применение == | == Применение == | ||
| Строка 72: | Строка 74: | ||
Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами в динамической задаче минимального остовного дерева. Заметим, что это возможно для специального случая планарных графов [6]. | Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами в динамической задаче минимального остовного дерева. Заметим, что это возможно для специального случая планарных графов [6]. | ||
Во-вторых, техники поддержки динамических минимальных остовных деревьев могут быть расширены на задачи 2-реберной и 2-вершинной связности, которые могут быть решены за полилогарифмическое время на одно обновление. Можно ли распространить эту технику более высокие | Во-вторых, техники поддержки динамических минимальных остовных деревьев могут быть расширены на задачи 2-реберной и 2-вершинной связности, которые могут быть решены за полилогарифмическое время на одно обновление. Можно ли распространить эту технику на более высокие размерности связности? Это особенно важно, поскольку наилучшие известные границы обновления для более высоких степеней реберной и вершинной связности являются полиномиальными, и было бы очень полезно разработать полилогарифмические алгоритмы хотя бы для полностью динамических задач 3-реберной и 3-вершинной связности. | ||
== См. также == | == См. также == | ||
| Строка 82: | Строка 83: | ||
* ''[[Полностью динамическая связность высоких степеней в планарных графах]] | * ''[[Полностью динамическая связность высоких степеней в планарных графах]] | ||
* ''[[Полностью динамическая проверка на планарность]] | * ''[[Полностью динамическая проверка на планарность]] | ||
* ''[[Полностью | * ''[[Полностью динамический алгоритм транзитивного замыкания]] | ||
== Литература == | == Литература == | ||
