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

Борувка [1] сформулировал задачу MST в процессе решения практической проблемы электрификации сельской местности Моравии (ныне Чешская Республика) при помощи кратчайшей сети линий электропередач. MST часто используются в качестве отправной точки для эвристических аппроксимаций оптимальных алгоритмов решения задачи коммивояжера и создания дерева Штейнера, а также в других задачах построения сетей. Кроме того, MST являются компонентами других алгоритмов оптимизации графов, в частности, алгоритмов нахождения кратчайшего пути с единственным источником, предложенных Торупом [ ] и Петти-Рамачандраном [15]. Также MST используются как инструмент визуализации данных, предположительно имеющих древовидную структуру; например, если матрица содержит данные о расхождениях для множества видов животных, минимальное остовное дерево соответствующего графа будет предположительно группировать близкородственные виды вместе (см. [ ]). Среди других современных вариантов применения MST – моделирование физических систем [17] и сегментация изображений [8]. В [4] вы найдете много других вариантов использования алгоритма.