4622
правки
Минимальное остовное дерево: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 22: | Строка 22: | ||
Из свойств разрезов и циклов следует, что в случае, если веса ребер уникальны, существует уникальное минимальное остовное дерево, которое мы обозначим MST(G). Уникальность всегда можно обеспечить, устраняя двусмысленность любым подходящим образом. Алгоритмы нахождения MST часто обращаются к полезному следствию свойств разрезов и циклов, называемому [[ | Из свойств разрезов и циклов следует, что в случае, если веса ребер уникальны, существует уникальное минимальное остовное дерево, которое мы обозначим 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>. | ||
== Базовый жадный алгоритм == | == Базовый жадный алгоритм == | ||
| Строка 43: | Строка 43: | ||
Из этого следует, что алгоритм Петти-Рамачандрана [13] является асимптотически не худшим, чем ''любой'' MST-алгоритм, выводящий решение при помощи сравнения весов ребер. Лучшая известная верхняя граница <math>D_{MST}(m, n) \;</math>, а именно <math>O(m \alpha(m, n)) \;</math>, была получена Шазелем [2]. Она тривиально составляет <math>\Omega(m) \;</math>. | Из этого следует, что алгоритм Петти-Рамачандрана [13] является асимптотически не худшим, чем ''любой'' 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 на экземпляры размеров <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] (приближенной очереди с приоритетами), и расширение свойства | Вкратце опишем принцип работы алгоритма Петти-Рамачандрана. Экземпляр (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* – множество ребер с увеличенными весами. | ||
| Строка 111: | Строка 111: | ||
18. Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362-394 (1999) | 18. Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362-394 (1999) | ||
[[Категория: Совместное определение связанных терминов]] | |||
