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

Из свойств разрезов и циклов следует, что в случае, если веса ребер уникальны, существует уникальное минимальное остовное дерево, которое мы обозначим MST(G). Уникальность всегда можно обеспечить, устраняя двусмысленность любым подходящим образом. Алгоритмы нахождения MST часто обращаются к полезному следствию свойств разрезов и циклов, называемому [[свойствомсжимаемости|свойством сжимаемости]]. Обозначим за G\C граф, полученный из исходного графа G путем сжатия подграфа C, при котором C заменяется единичной вершиной c, а все ребра, инцидентные ровно одной вершине в C, становятся инцидентными c; в общем случае G\C может содержать более одного ребра между двумя вершинами.

'''Свойство сжимаемости'''. Если C – подграф, такой, что для всех пар ребер e и f, имеющих ровно одну конечную точку в C, существует путь <math>P \subseteq C \;</math>, связывающий ef с каждым ребром в P, более легким, чем e или f, в таком случае С является сжимаемым. Для любого сжимаемого подграфа C верно <math>MST(G) = MST(C) \cup MST(G \backslash C) \;</math>.

Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому 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] (приближенной очереди с приоритетами), и расширение свойства сжимаемости.

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

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