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

Перейти к навигации Перейти к поиску
Строка 36: Строка 36:


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




Теорема 1. Существует явный детерминированный алгоритм нахождения минимального остовного дерева с временем исполнения порядка DMST(m, n), где m – количество ребер, n – количество вершин, а DMST(m, n) – максимальная глубина оптимального дерева решений для любого графа с n вершинами и m ребрами.
'''Теорема 1. Существует явный детерминированный алгоритм нахождения минимального остовного дерева с временем исполнения порядка <math>D_{MST}(m, n) \;</math>, где m – количество ребер, n – количество вершин, а <math>D_{MST}(m, n) \;</math> – максимальная глубина оптимального дерева решений для любого графа с 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). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [ ] (приближенной очереди с приоритетами), и расширение свойства сжимаемости.
 
Из этого следует, что алгоритм Петти-Рамачандрана [14] является асимптотически не худшим, чем ''любой'' MST-алгоритм, выводящий решение при помощи сравнения весов ребер. Лучшая известная верхняя граница <math>D_{MST}(m, n) \;</math>, а именно <math>O(m \alpha(m, n)) \;</math>, была получена Шазелем [2]. Она тривиально составляет <math>\Omega(m) \;</math>.
 
Вкратце опишем принцип работы алгоритма Петти-Рамачандрана. Экземпляр (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). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [ ] (приближенной очереди с приоритетами), и расширение свойства сжимаемости.


Приближенная сжимаемость. Рассмотрим граф G0, полученный из G при помощи увеличения веса некоторых ребер. Если C является сжимаемым относительно G0, то MST(G) = MST(MST(C) [ MST(G n C) [ £*), где E* – множество ребер с увеличенными весами.
Приближенная сжимаемость. Рассмотрим граф G0, полученный из G при помощи увеличения веса некоторых ребер. Если C является сжимаемым относительно G0, то MST(G) = MST(MST(C) [ MST(G n C) [ £*), где E* – множество ребер с увеличенными весами.
Строка 56: Строка 59:


Теорема 4 [2]. Минимальное остовное дерево графа может быть вычислено за время O(ma(m, n)) при помощи детерминированного алгоритма, где a  – обратная функция Аккермана.
Теорема 4 [2]. Минимальное остовное дерево графа может быть вычислено за время O(ma(m, n)) при помощи детерминированного алгоритма, где a  – обратная функция Аккермана.


== Применение ==
== Применение ==
Источник — http://pco.iis.nsk.su/wega/index.php/Минимальное_остовное_дерево