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

Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому MST-алгоритмы естественно моделировать при помощи [[бинарные деревья решений|бинарных деревьев решений]], где вершины дерева решений определяются при помощи сравнения весов ребер, а потомки вершины соответствуют возможным результатам сравнения. В такой модели дерева решений тривиальная нижняя граница '''времени''' исполнения оптимального MST-алгоритма представляет собой '''глубину''' оптимального дерева решений.

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

'''Теорема 1. Существует явный детерминированный алгоритм нахождения минимального остовного дерева с временем исполнения порядка <math>D_{MST}(m, n) \;</math>, где m – количество ребер, n – количество вершин, а <math>D_{MST}(m, n) \;</math> – максимальная глубина оптимального дерева решений для любого графа с n вершинами и m ребрами.'''

Вкратце опишем принцип работы алгоритма Петти-Рамачандрана. Экземпляр (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>. В силу ограниченного размера этих экземпляров <math>(n_i \le log \; log \; log \; n) \;</math> время работы алгоритма поиска перебором незначительно – o(n). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [2] (приближенной очереди с приоритетами), и расширение свойства сжимаемости.

Второй результат исследований [13] заключается в том, что время исполнения оптимального алгоритма фактически является линейным для графов почти любой топологии, с любыми перестановками весов ребер.