4511
правок
Полностью динамические минимальные остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 12:48, 19 июля 2014
, 19 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
'''Лемма 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>. | ||