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

Перейти к навигации Перейти к поиску
Строка 47: Строка 47:




'''Лемма 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. Предположим, что существует алгоритм поддержки минимального остовного дерева, выполняющий только удаление ребер, который для любых значений <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>.
Источник — http://pco.iis.nsk.su/wega/index.php/Полностью_динамические_минимальные_остовные_деревья