2. 计算机
  3. 煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

admin2016-05-11  65
问题 煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为(   )米。
选项 A、1800
B、2200
C、2000
D、2100
答案B
解析 这是求最小支撑树的问题，可使用破圈法求解。所谓破圈法就是任取一个圈，从圈中去掉一条权值最大的边(如果有两条或两条以上的边都是权值最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。
求解步骤如下：(红线表示该条路径删除)
    (1)先找出一个中心点，圈1，因为圈1与所有点都有联系，则删除从圈1出发的两点距离最长的9，可得：

(2)再删除剩下来的两点距离最长的8，可得：

(3)再删除剩下来的两点距离最长的7，可得：

(4)再删除圈1与圈4之间的距离5，因为圈1，圈4，圈5之间不需要重复连接，可得：

(5)同第(4)步，两个活动不需要重复连接，见过观察删除圈3与圈2之间的6，可得：

最后把剩余的连线的距离加起来22千米，即2200米。
转载请注明原文地址:https://kaotiyun.com/show/baGZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

信息系统项目管理师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)