Минимальное остовное дерево: различия между версиями

Основным результатом [ ] является явный MST-алгоритм, доказуемо оптимальный, несмотря на то, что его асимптотическое время исполнения в настоящее время неизвестно.

Теорема 1. Существует явный детерминированный алгоритм нахождения минимального остовного дерева с временем исполнения порядка DMST(m, n), где m – количество ребер, n – количество вершин, а DMST(m, n) – максимальная глубина оптимального дерева решений для любого графа с n вершинами и m ребрами.

Из этого следует, что алгоритм Петти-Рамачандрана [14] является асимптотически не худшим, чем любой MST-алгоритм, выводящий решение при помощи сравнения весов ребер. Лучшая известная верхняя граница DMST(m, n), а именно O(ma(m, n)), была получена Шазелем [ ]. Она тривиально составляет Q(rn). Вкратце опишем принцип работы алгоритма Петти-Рамачандрана. Экземпляр (m, n) представляет собой граф с m ребрами и n вершинами. Доказательство теоремы 1 выполняется при помощи процедуры декомпозиции с линейным временем исполнения, разбивающей любой экземпляр (m, n) задачи MST на экземпляры размеров (m*, n*), (mi, ni), ..., (ms, ns), где m = m* + Pi mi, n = Pi ni, n* — n/logloglog n и каждый ni <logloglogn. Экземпляр (m*,n*) может быть обработан за время O(m + n) при помощи существующих MST-алгоритмов [2]. Для обработки других экземпляров алгоритм Петти-Рамачандрана выполняет поиск перебором для нахождения дерева решений минимальной глубины для каждого графа, число вершин которого не превышает log log log n. После нахождения этих деревьев решения оставшиеся экземпляры можно обработать за время O(Pi DMST(mi; ni)) = O(DMST(m; n)). В силу ограниченного размера этих экземпляров (ni < log log log n) время работы алгоритма поиска перебором незначительно – o(n). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [ ] (приближенной очереди с приоритетами), и расширение свойства сжимаемости.