Минимальное остовное дерево
Задача о минимальном остовном дереве (В англоязычной литературе — «Minimum Spanning Tree»), заключается в следующем:
Задан связный неориентированный граф G=(V,E), где V — множество вершин, |V|=n, E — множество ребер между ними, и весовая функция
Иными словами, есть n вершин
Чему равен наименьший возможный вес остовного дерева?
Т.е., требуется найти минимально возможное значение суммы
Для решения этой задачи можно применять:
- алгоритм Прима ;
- алгоритм Краскала (Kruskal).
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.