某地区5个居民点之间现有道路距离见下列邻接矩阵（单位：千米）： 现需要利用现有道路铺设天然气管道。假设铺设成本完全由距离决定，

某地区5个居民点之间现有道路距离见下列邻接矩阵（单位：千米）： 现需要利用现有道路铺设天然气管道。假设铺设成本完全由距离决定，试用最小生成树规划最低成本管道铺设方案，并确定该方案下总的铺设长度。

【正确答案】：

见下列无向图G=，其中V={a,b,c,d,e}，代表5个居民点，E={|,u,v∈V}，且u 和v代表5个居民点，图G如答35-1图所示用Kruskal算法可得其最小生成树如答35-2图所示此即最低成本管道铺设方案，该方案下总的铺设长度为5+5+7+6=23千米。

【题目解析】：本题是最小生成树的应用。首先按照邻接矩阵把无向图画出来，然后用Kruskal算法找到最小生成树，最小生成树边上的距离之和就是最低成本管道铺设方案。