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

Нижняя граница <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> на операцию.