Районной администрацией принято решение о газификации одного из небольших сел района, имеющего 10 жилых домов.
Расположение домов указано на рис.1. Числа в кружках обозначают условный номер дома. Узел 11 является газопонижающей станцией.
Разработать такой план газификации села, чтобы общая длина трубопроводов была наименьшей.
Переводя задачу на язык теории графов, получим, что нам нужно найти остовное дерево минимального веса.
Для построения минимального остовного дерева применим алгоритм Краскала. Этот алгоритм следующий.
Из всех ребер выбираем одно с наименьшим весом. Затем из оставшихся рассматриваем наименьшее по весу ребро. Если оно не образует цикла с ранее выбранными рёбрами графа, то вводится в остов. Построение прекращается после n 1 шагов.
В графе выбираем ребро с минимальным весом. В нашем случае это ребро, соединяющее вершины 9 и 10 с весом 20. Пусть, например, вершина 9 будет корнем дерева....