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

Перейти к навигации Перейти к поиску
Строка 43: Строка 43:
Из этого следует, что алгоритм Петти-Рамачандрана [14] является асимптотически не худшим, чем ''любой'' MST-алгоритм, выводящий решение при помощи сравнения весов ребер. Лучшая известная верхняя граница <math>D_{MST}(m, n) \;</math>, а именно <math>O(m \alpha(m, n)) \;</math>, была получена Шазелем [2]. Она тривиально составляет <math>\Omega(m) \;</math>.
Из этого следует, что алгоритм Петти-Рамачандрана [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). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [ ] (приближенной очереди с приоритетами), и расширение свойства сжимаемости.
Вкратце опишем принцип работы алгоритма Петти-Рамачандрана. Экземпляр (m, n) представляет собой граф с m ребрами и n вершинами. Доказательство теоремы 1 выполняется при помощи процедуры [[декомпозиция|декомпозиции]] с линейным временем исполнения, разбивающей любой экземпляр (m, n) задачи MST на экземпляры размеров <math>(m^*, n^*), (m_1, n_1), ..., (m_s, n_s) \;</math>, где <math>m = m^* + \sum_i m_i \;</math>, <math>n = \sum_i n_i \;</math>, <math>n^* \le n / log \; log \; log \; n</math> и каждый <math>n_i \le log \; log \; log \; n</math>. Экземпляр (m*,n*) может быть обработан за время O(m + n) при помощи существующих MST-алгоритмов [2]. Для обработки других экземпляров алгоритм Петти-Рамачандрана выполняет поиск перебором для нахождения дерева решений минимальной глубины для '''каждого''' графа, число вершин которого не превышает log log log n. После нахождения этих деревьев решения оставшиеся экземпляры можно обработать за время <math>O(\sum_i D_{MST}(m_i, n_i)) = O(D_{MST}(m, n)) \;</math>. В силу ограниченного размера этих экземпляров (ni < log log log n) время работы алгоритма поиска перебором незначительно – o(n). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [2] (приближенной очереди с приоритетами), и расширение свойства сжимаемости.


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


Второй результат исследований [ ] заключается в том, что время исполнения оптимального алгоритма фактически является линейным для графов почти любой топологии, с любыми перестановками весов ребер.
'''Приближенная сжимаемость'''. Рассмотрим граф G', полученный из G при помощи увеличения веса некоторых ребер. Если C является сжимаемым относительно G', то <math>MST(G) = MST(MST(C) \cup MST(G \backslash C) \cup E^*) \;</math>, где E* – множество ребер с увеличенными весами.
 
 
Второй результат исследований [14] заключается в том, что время исполнения оптимального алгоритма фактически является линейным для графов почти любой топологии, с любыми перестановками весов ребер.




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