Минимальное остовное дерево

Задача о минимальном остовном дереве (В англоязычной литературе — «Minimum Spanning Tree»), заключается в следующем:

Задан связный неориентированный граф G=(V,E), где V — множество вершин, |V|=n, E — множество ребер между ними, и весовая функция .

Иными словами, есть n вершин и положительные целые веса дуг между ними. (Можно вводить веса на ребрах, как ).

Чему равен наименьший возможный вес остовного дерева? Т.е., требуется найти минимально возможное значение суммы где минимум берется по всем остовным деревьям на n вершинах, т. е. по всем множествам T из (n-1) дуг, связывающим все n вершин в единую сеть.

Для решения этой задачи можно применять:

• алгоритм Прима ;
• алгоритм Краскала (Kruskal).

---

Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.