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

Описание конструкции, необходимой для доказательства леммы 2, можно найти в работах [11] и [13]. Из леммы 1 получаем t(k,l) = O(log2 k). Комбинируя леммы 1 и 2, получаем следующий результат:

Теорема 3. Существует полностью динамический алгоритм поддержки минимального остовного леса, который для графа с n вершинами, начиная работу с нулевого числа ребер, поддерживает минимальный остовный лес за амортизированное время O(log4 n) на вставку или удаление ребра.

Нижняя граница Q (log n) для динамического минимального остовного дерева, предложенная Эппстайном и коллегами [ ], использует следующее рассуждение. Пусть A – алгоритм, поддерживающий минимальное остовное дерево произвольного (мульти)графа G; такой, что функция изменения веса weight(e; Л) возвращает ребро f, заменяющее ребро e в минимальном остовном дереве, если e подлежит замене. Очевидно, что любой динамический алгоритм поддержки остовного дерева можно модифицировать так, чтобы он возвращал f. Можно использовать алгоритм A для сортировки n положительных чисел x1, x2, ... , xn следующим образом. Построимь мультиграф G, состоящий из двух вершин, связанных (n + 1) ребрами e0, e1, ... , en, такими, что ребро e0 имеет вес 0, а ребро ei имеет вес xi. Первоначальное остовное дерево будет соответствовать e0. Увеличим вес e0 на +1. Ребро, которое заменит e0 (положим, ei), будет ребром с минимальным весом. Теперь увеличим вес ei на +1; замена ei будет иметь второй по счету минимальный вес. Продолжая этот процесс, получим числа в возрастающем порядке. Подобные же рассуждения можно привести для случая постоянного уменьшения весов ребер. После того, как Пол и Саймон [ ] показали, что любому алгоритму сортировки требуется время Q(n log n) для сортировки n чисел на RAM-машине с единичной стоимостью, способной выполнять операции сложения, вычитания, умножения и сравнения с нулем, но не поддерживающей деление и поразрядные булевы операции, была сформулирована следующая теорема.