Условие задачи
Районной администрацией принято решение о газификации одного из небольших сел района, имеющего 12 жилых домов. Расположение домов указано на рисунке 3. Числа в кружках обозначают условный номер дома. Узел 13 является газопонижающей станцией. На рисунке показано также возможное расположение трубопроводов и длины участков (первое число).
График к задаче.
Разработать такой план газификации села, чтобы общая длина трубопровода была наименьшей.
Ответ
Сеть трубопроводов представляет собой остовное дерево.
Построим остовное дерево алгоритмом Прима, в котором поддерживается уже обработанная часть графа (минимального остовного дерева), постепенно расширяемая за счёт ближайших вершин.
Таким образом, для нахождения минимального остовного дерева начинается с произвольной вершины и постепенно добавляются минимальные ребра, не образующие цикл, ближайшие к уже имеющимся.
Построения начинаем с ребра минимального веса (3,5).
Первый шаг алгоритма Прима.
