Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Пример[править | править вики-текст]

Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.

Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: допустим, есть n городов, которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги. Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.

Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра — это пары городов, между которыми можно проложить прямую дорогу, а вес ребра равен стоимости строительства соответствующей дороги.

Алгоритмы[править | править вики-текст]

Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них перечислены ниже:

• Алгоритм Прима
• Алгоритм Краскала (или алгоритм Крускала)
• Алгоритм Борувки

Родственные задачи[править | править вики-текст]

На задачу о нахождении минимального остовного дерева похожа задача о дереве Штейнера. В ней задано несколько точек на плоскости и требуется проложить между ними граф путей, так, чтобы минимизировать сумму длин путей. Главное отличие от задачи о минимальном остовном дереве при этом заключается в том, что разрешается добавлять дополнительные точки ветвления с целью ещё сильнее уменьшить сумму длин рёбер. Задача о дереве Штейнера является NP-полной.

Литература[править | править вики-текст]

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 23. Минимальные остовные деревья // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её.