Нижняя граница для динамической связности: различия между версиями

Нижняя граница теоремы 1 соответствует ntq ■ lg(2ntu/ntq) = Q{n\gn); следовательно, tqlg(tu/tq) = £2(lgn). Заметим, что из этой нижней границы следует maxf tu; tq g = Q (lg n). Лучшая известная верхняя граница (с использованием амортизации и рандомизации) равна O(lg n(lglg n)3) [ ]. Известно, что для любого tu = £?(lg n(lglg n)3) компромиссная нижняя граница является строгой. Отметим, что граф в нижней границе всегда является несвязным объединением путей. Из этого следует оптимальность нижних границ для двух важных частных случаев: динамических деревьев [8] и динамической связности в планарных графах [2].