Эта задача возникает при проектировании линий электропередач, трубопроводов, дорог и т.д., когда требуется заданные центры соединить некоторой системой каналов связи таким образом, чтобы любые два центра были связаны непосредственно или через другие каналы, и чтобы общая длина (стоимость) каналов связи была минимальной.
Остовом графа называется связный подграф без циклов, содержащий все вершины исходного графа. Подграф содержит часть или все ребра исходного графа. Задача о минимальном остове формулируется следующим образом: во взвешенном связном графе найти остов минимального веса. Рассмотрим алгоритм Краскала решения этой задачи. В алгоритме используются два правила:
1. Первое ребро остова – ребро минимального веса в исходном графе.
2. Если граф Ti уже построен (i<n-1), то новый граф Ti+1 получается из графа Ti присоединением ребра ei+1 , имеющего минимальный вес среди ребер, не входящих в Ti, и не составляющего циклов с ребрами из Ti.
Пример 4.13. Найти минимальный остов во взвешенном графе.
Построение остова начнем с ребра (v1, v3). Порядок присоединения ребер к остову:
(v1, v3), (v2, v5), (v1, v2), (v4, v5).
Вес остова W=1+2+1+4=8.
