Минимальное остовное дерево
Ключевые слова и синонимы
Остовное дерево с минимальным весом; кратчайшее остовное дерево
Постановка задачи
Задача нахождения минимального остовного дерева (MST) заключается в следующем: имеется связный взвешенный неориентированный граф G = (V, E, w), необходимо найти дерево с минимальным общим весом, содержащее все вершины из V. Здесь [math]\displaystyle{ w: \mathbb{E} \Rightarrow \mathbb{R} \; }[/math] – весовая функция. Задачу часто формулируют в геометрических терминах, где V – множество точек в d-мерном пространстве, а w соответствует евклидову расстоянию. Основное различие между двумя подходами заключается в виде входных данных. В графовой формулировке входной граф имеет размер O(m + n) и состоит из перечисления n = |V| вершин и m = |E| ребер, а также весов ребер. В геометрической формулировке на входе имеется перечисление координат каждой точки (пространство O(dn)): все [math]\displaystyle{ \left ( \frac{V}{2} \right ) \; }[/math] ребер представлены неявно, веса неявно приписаны к координатам точек. В [15] обсуждается задача нахождения минимального евклидова остовного дерева.
История вопроса
Задача MST обычно рассматривается [7, 11] как одна из первых комбинаторных задач, исследовавшихся с алгоритмической точки зрения. Формальное определение было дано Борувкой в 1926 году [1] (еще до возникновения теории вычислимости, комбинаторной оптимизации и в немалой степени – теории графов), и с тех пор этот базовый алгоритм широко использовался. Задача MST способствовала исследованиям в таких сферах, как оптимизация матроидов [3], и разработке эффективных структур данных – таких как очереди с приоритетами (или кучи) и структуры непересекающихся множеств [2, 18].
Родственные задачи
Задачу MST часто сравнивают с задачей коммивояжера и поиском минимального дерева Штейнера [6]. Деревом Штейнера называется дерево, которое может охватывать любое надмножество заданных вершин; иначе говоря, к нему могут добавляться дополнительные вершины, снижающие вес минимального остовного дерева. В задаче коммивояжера необходимо найти путь (цикл) по вершинам с минимальной общей длиной. Обобщение задачи MST на ориентированные графы иногда называют задачей минимального ветвления [5]. Тем не менее, если задача MST для неориентированных и ориентированных графов разрешима за полиномиальное время, то задача коммивояжера и нахождение минимального дерева Штейнера являются NP-полными [6].
Условия оптимальности
Разрез представляет собой разбиение (V', V") вершин графа V. Ребро (u, v) пересекает разрез (V, V"), если [math]\displaystyle{ u \in V' \; }[/math] и [math]\displaystyle{ v \in V'' \; }[/math]. Последовательность [math]\displaystyle{ (v_0, v_1,..., v_{k-1}, v_0) \; }[/math] является циклом, если [math]\displaystyle{ (v_i, v_{i+1(mod k)}) \in E \; }[/math] для [math]\displaystyle{ 0 \le i \lt k \; }[/math] .
Корректность всех алгоритмов нахождения MST устанавливается при помощи двух свойств, разрезов и циклов, также известных как синее и красное правила [17].
Свойство разрезов. Ребро принадлежит к некоторому минимальному остовному дереву в том и только том случае, если это самое легкое ребро, пересекающее некоторый разрез.
Свойство циклов. Ребро не принадлежит ни к одному минимальному остовному дереву в том и только том случае, если это единственное самое тяжелое ребро в некотором цикле.
Из свойств разрезов и циклов следует, что в случае, если веса ребер уникальны, существует уникальное минимальное остовное дерево, которое мы обозначим MST(G). Уникальность всегда можно обеспечить, устраняя двусмысленность любым подходящим образом. Алгоритмы нахождения MST часто обращаются к полезному следствию свойств разрезов и циклов, называемому свойством сжимаемости. Обозначим за G\C граф, полученный из исходного графа G путем сжатия подграфа C, при котором C заменяется единичной вершиной c, а все ребра, инцидентные ровно одной вершине в C, становятся инцидентными c; в общем случае G\C может содержать более одного ребра между двумя вершинами.
Свойство сжимаемости. Если C – подграф, такой, что для всех пар ребер e и f, имеющих ровно одну конечную точку в C, существует путь [math]\displaystyle{ P \subseteq C \; }[/math], связывающий ef с каждым ребром в P, более легким, чем e или f, в таком случае С является сжимаемым. Для любого сжимаемого подграфа C верно [math]\displaystyle{ MST(G) = MST(C) \cup MST(G \backslash C) \; }[/math].
Базовый жадный алгоритм
До недавних пор все алгоритмы расчета MST можно было считать вариациями данного базового жадного алгоритма. Пусть [math]\displaystyle{ \mathcal{T} \; }[/math] изначально состоит из n тривиальных деревьев, каждое из которых содержит одну вершину графа G. Повторить следующий шаг n - 1 раз. Выбрать любой элемент [math]\displaystyle{ T \in \mathcal{T} \; }[/math] и найти ребро с минимальным весом (u, v), у которого [math]\displaystyle{ u \in T \; }[/math], а v принадлежит другому дереву, скажем, [math]\displaystyle{ T' \in \mathcal{T} \; }[/math]. Заменить T и T' в [math]\displaystyle{ \mathcal{T} \; }[/math] одним деревом [math]\displaystyle{ T \cup \{ (u, v) \} \cup T' \; }[/math]. После n - 1 итераций получаем [math]\displaystyle{ \mathcal{T} = \{ MST(G) \} \; }[/math]. Согласно свойству разрезов, каждое ребро, выбранное этим алгоритмом, содержится в MST.
Моделирование MST-алгоритмов
Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому MST-алгоритмы естественно моделировать при помощи бинарных деревьев решений, где вершины дерева решений определяются при помощи сравнения весов ребер, а потомки вершины соответствуют возможным результатам сравнения. В такой модели дерева решений тривиальная нижняя граница времени выполнения оптимального MST-алгоритма представляет собой глубину оптимального дерева решений.
Основные результаты
Основным результатом [13] является явный MST-алгоритм, доказуемо оптимальный, несмотря на то, что его асимптотическое время выполнения в настоящее время неизвестно.
Теорема 1. Существует явный детерминированный алгоритм нахождения минимального остовного дерева с временем выполнения порядка [math]\displaystyle{ D_{MST}(m, n) \; }[/math], где m – количество ребер, n – количество вершин, а [math]\displaystyle{ D_{MST}(m, n) \; }[/math] – максимальная глубина оптимального дерева решений для любого графа с n вершинами и m ребрами.
Из этого следует, что алгоритм Петти-Рамачандрана [13] является асимптотически не худшим, чем любой MST-алгоритм, выводящий решение при помощи сравнения весов ребер. Лучшая известная верхняя граница [math]\displaystyle{ D_{MST}(m, n) \; }[/math], а именно [math]\displaystyle{ O(m \alpha(m, n)) \; }[/math], была получена Шазелем [2]. Она тривиально составляет [math]\displaystyle{ \Omega(m) \; }[/math].
Вкратце опишем принцип работы алгоритма Петти-Рамачандрана. Экземпляр (m, n) представляет собой граф с m ребрами и n вершинами. Доказательство теоремы 1 выполняется при помощи процедуры декомпозиции с линейным временем выполнения, разбивающей любой экземпляр (m, n) задачи MST на экземпляры размеров [math]\displaystyle{ (m^*, n^*), (m_1, n_1), ..., (m_s, n_s) \; }[/math], где [math]\displaystyle{ m = m^* + \sum_i m_i \; }[/math], [math]\displaystyle{ n = \sum_i n_i \; }[/math], [math]\displaystyle{ n^* \le n / log \; log \; log \; n }[/math] и каждый [math]\displaystyle{ n_i \le log \; log \; log \; n }[/math]. Экземпляр (m*,n*) может быть обработан за время O(m + n) при помощи существующих MST-алгоритмов [2]. Для обработки других экземпляров алгоритм Петти-Рамачандрана выполняет поиск перебором для нахождения дерева решений минимальной глубины для каждого графа, число вершин которого не превышает log log log n. После нахождения этих деревьев решений оставшиеся экземпляры можно обработать за время [math]\displaystyle{ O(\sum_i D_{MST}(m_i, n_i)) = O(D_{MST}(m, n)) \; }[/math]. В силу ограниченного размера этих экземпляров [math]\displaystyle{ (n_i \le log \; log \; log \; n) \; }[/math] время работы алгоритма поиска перебором незначительно – o(n). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [2] (приближенной очереди с приоритетами), и расширение свойства сжимаемости.
Приближенная сжимаемость. Рассмотрим граф G', полученный из G при помощи увеличения веса некоторых ребер. Если C является сжимаемым относительно G', то [math]\displaystyle{ MST(G) = MST(MST(C) \cup MST(G \backslash C) \cup E^*) \; }[/math], где E* – множество ребер с увеличенными весами.
Второй результат исследований [13] заключается в том, что время выполнения оптимального алгоритма фактически является линейным для графов почти любой топологии, с любыми перестановками весов ребер.
Теорема 2. Пусть G равномерно выбирается случайным образом из множества всех графов, имеющих n вершин и m ребер. Тогда, независимо от весов ребер, MST(G) может быть найдено за время O(m + n) с вероятностью [math]\displaystyle{ 1 - 2^{- \Omega (m / \alpha^2)} \; }[/math], где [math]\displaystyle{ \alpha = \alpha(m, n) \; }[/math] – медленно растущая обратная функция Аккермана.
Теорему 1 можно сопоставить с результатами исследований Карджера, Клейна и Тарьяна [9], а также Шазеля [2], посвященных рандомизированной и детерминированной сложности задачи MST.
Теорема 3 [9]. Минимальный остовный лес графа с m ребрами может быть вычислен при помощи рандомизированного алгоритма за время O(m) с вероятностью [math]\displaystyle{ 1 - 2^{- \Omega (m)} \; }[/math].
Теорема 4 [2]. Минимальное остовное дерево графа может быть вычислено за время [math]\displaystyle{ O(m \alpha(m, n)) \; }[/math] при помощи детерминированного алгоритма, где [math]\displaystyle{ \alpha \; }[/math] – обратная функция Аккермана.
Применение
Борувка [1] сформулировал задачу MST в процессе решения практической проблемы электрификации сельской местности Моравии (ныне Чешская Республика) при помощи кратчайшей сети линий электропередач. MST часто используются в качестве отправной точки для эвристических аппроксимаций оптимальных алгоритмов решения задачи коммивояжера и создания дерева Штейнера, а также в других задачах построения сетей. Кроме того, MST являются компонентами других алгоритмов оптимизации графов, в частности, алгоритмов нахождения кратчайшего пути с единственным источником, предложенных Торупом [18] и Петти-Рамачандраном [14]. Также MST используются как инструмент визуализации данных, предположительно имеющих древовидную структуру; например, если матрица содержит данные о расхождениях для множества видов животных, минимальное остовное дерево соответствующего графа будет предположительно группировать близкородственные виды вместе (см. [7]). Среди других современных вариантов применения MST – моделирование физических систем [16] и сегментация изображений [8]. В [4] вы найдете много других вариантов использования алгоритма.
Открытые вопросы
Открытым остается важный вопрос определения детерминированной сложности задачи нахождения минимального остовного дерева. Согласно теореме 1, он равносилен определению сложности дерева решений задачи минимального остовного дерева.
Экспериментальные результаты
Морет и Шапиро [10] оценили эффективность жадных MST-алгоритмов, используя разные очереди с приоритетами. Они обнаружили, что лучшим является алгоритм Ярника [7] (также его авторами считаются Прим и Дейкстра, см. [3, 7, 11]) в варианте реализации с кучей для пар [12]. Катриэль, Сандерс и Трафф [9] разработали и реализовали нежадный рандомизированный MST-алгоритм на базе алгоритма Карджера и коллег [8]. Они пришли к выводу, что на относительно плотных графах он работает значительно быстрее жадных алгоритмов, протестированных Моретом и Шапиро.
См. также
Литература
1. Boruvka, O.: O jistem problemu minimalnim. Prace Moravske Pfirodovedecke Spolecnosti 3, 37-58 (1926). In Czech
2. Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028-1047 (2000) Cormen, TH., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)
3. Eppstein, D.: Geometry in action: minimum spanning trees. http://www.ics.uci.edu/~eppstein/gina/mst.html
4. Gabow, H.N., Galil, Z., Spencer, T.H., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6,109-122(1986)
5. Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to NP-completeness. Freeman, San Francisco (1979)
6. Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7(1), 43-57 (1985)
7. Ion, A., Kropatsch, W.G., Haxhimusa, Y.: Considerations regarding the minimum spanning tree pyramid segmentation method. In: Proc. 11 th Workshop Structural, Syntactic,and Statistical Pattern Recognition (SSPR). LNCS, vol. 4109, pp. 182-190. Springer, Berlin (2006)
8. Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm for finding minimum spanning trees. J. ACM 42, 321-329(1995)
9. Katriel, I., Sanders, P., Traff, J.L.: A practical minimum spanning tree algorithm using the cycle property. In: Proc. 11th Annual European Symposium on Algorithms. LNCS, vol. 2832, pp. 679- 690. Springer, Berlin (2003)
10. Moret, B.M.E., Shapiro, H.D.: An empirical assessment of algorithms for constructing a minimum spanning tree. In: DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 15, Am. Math. Soc., Providence, RI (1994)
11. Pettie, S.: On the shortest path and minimum spanning tree problems. Ph.D. thesis, The University of Texas, Austin, August 2003
12. Pettie, S.: Towards a final analysis of pairing heaps. In: Proc. 46th Annual Symposium on Foundations of Computer Science (FOCS), 2005, pp. 174-183
13. Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49( 1), 16-34 (2002)
14. Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. 34(6), 1398-1431 (2005)
15. Preparata, F.P., Shamos, M.I.: Computational geometry. Springer, New York (1985)
16. Subramaniam, S., Pope, S.B.: A mixing model for turbulent reactive flows based on euclidean minimum spanning trees. Combust. Flame 115(4),487-514 (1998)
17. Tarjan, R.E.: Data structures and network algorithms. In: CBMS-NSF Reg. Conf. Ser. Appl. Math., vol. 44. SIAM, Philadelphia (1983)
18. Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362-394 (1999)