2022-01-07
96
Покрывающее дерево – это дерево, содержащее все вершины сети. Минимальное покрывающее дерево предполагает, что все вершины сети соединены между собой путями наименьшей длины.
Задача 3.8. Сельскохозяйственное предприятие планирует газифицировать свои населенные пункты. Структура планируемой газовой сети и расстояние между центральной усадьбой сельскохозяйственного предприятия и населенными пунктами приведены на рис. 3.9, а – в. Требуется спланировать наиболее экономичную газовую сеть, используя алгоритм построения минимального покрывающего дерева.
На основании приведенной информации задачи 3.8, применив алгоритм построения покрывающего дерева, необходимо:
1) разбить все вершины сети на два множества: Е1 – множество, содержащее любую выбранную вершину сети (чаще всего вершину с номером 1), и 
– множество, содержащее все другие вершины сети, за исключением выбранной;
2) среди вершин множества Е1 выбрать ту вершину из множества , которая соединена самой короткой дугой или ребром с вершиной из множества Е1;
3) выбранную на предыдущем этапе вершину добавить в множество Е1, образовав множество вершин Е2, и отнять из множества , образовав множество вершин 
;
4) самую короткую дугу или ребро, соединяющую вершины двух множеств, выделить жирной линией;
5) алгоритм продолжить выполнять с пункта 2 до тех пор, пока множество 
не будет содержать ни одного элемента;
6) рассчитать длину газовой сети сельскохозяйственного предприятия.
 |
а
б
в
Рис. 3.9. Газовая сеть
