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

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

 

Во-вторых, техники поддержки динамических минимальных остовных деревьев могут быть расширены на задачи 2-реберной и 2-вершинной связности, которые могут быть решены за полилогарифмическое время на одно обновление. Можно ли распространить эту технику на более высокие размерности связности? Это особенно важно, поскольку наилучшие известные границы обновления для более высоких степеней реберной и вершинной связности являются полиномиальными, и было бы очень полезно разработать полилогарифмические алгоритмы хотя бы для полностью динамических задач 3-реберной и 3-вершинной связности.

* ''[[Полностью динамический алгоритм транзитивного замыкания]]