4446
правок
Полностью динамические минимальные остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 12:43, 19 июля 2014
, 19 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
<math>Replace((u, w), \ell (e)) \; </math> находит ребро замены самого высокого уровня, не превышающего <math>\ell \;</math>, если такое существует, рассматривая ребра в порядке увеличения веса. Если на уровне <math>\ell \;</math> такого ребра не существует, имеет место один из двух вариантов: если <math>\ell > 0 \;</math>, алгоритм рекурсивно переходит на уровень <math>\ell - 1 \;</math>; в противном случае <math>\ell = 0 \;</math>, и удаление ребра (v, w) разделяет деревья v и w в графе G. | <math>Replace((u, w), \ell (e)) \; </math> находит ребро замены самого высокого уровня, не превышающего <math>\ell \;</math>, если такое существует, рассматривая ребра в порядке увеличения веса. Если на уровне <math>\ell \;</math> такого ребра не существует, имеет место один из двух вариантов: если <math>\ell > 0 \;</math>, алгоритм рекурсивно переходит на уровень <math>\ell - 1 \;</math>; в противном случае <math>\ell = 0 \;</math>, и удаление ребра (v, w) разделяет деревья v и w в графе G. | ||
Можно показать, что Replace возвращает ребро замены с минимальным весом максимально возможного уровня, что обосновывает следующую лемму: | Можно показать, что функция <math>Replace \; </math> возвращает ребро замены с минимальным весом максимально возможного уровня, что обосновывает следующую лемму: | ||
Лемма 1. Существует алгоритм поддержки минимального остовного леса, выполняющий только удаление ребер, который может быть инициализирован на графе с n вершинами и m ребрами и который поддерживает любую последовательность удалений ребер за полное время O(m | '''Лемма 1. Существует алгоритм поддержки минимального остовного леса, выполняющий только удаление ребер, который может быть инициализирован на графе с n вершинами и m ребрами и который поддерживает любую последовательность удалений ребер за полное время <math>O(m log^2 \; n)</math>. | ||
''' | |||
Теперь перейдем к описанию полностью динамического алгоритма, выполняющего обновления за время <math>O(log^4 \; n)</math>. Редукция, используемая для получения полностью динамического алгоритма, представляет собой небольшое обобщение подхода, предложенного Хенцингер и Кинг [11]. | |||
'''Лемма 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 ребер поддерживает обновления за время''' | |||
Описание конструкции, необходимой для доказательства леммы 2, можно найти в работах [11] и [13]. Из леммы 1 получаем t(k,l) = O(log2 k). Комбинируя леммы 1 и 2, получаем следующий результат: | Описание конструкции, необходимой для доказательства леммы 2, можно найти в работах [11] и [13]. Из леммы 1 получаем t(k,l) = O(log2 k). Комбинируя леммы 1 и 2, получаем следующий результат: | ||