信管网试题库

2014年下半年信息系统项目管理师上午综合知识真题试题解析：

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

A、1800
B、2200
C、2000
D、2100

信管网解析：
（一）这是求最小支撑树的问题。使用破圈法求解，求解步骤如下：

所谓破圈法就是任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。
（二）也可以使用穷举法
信管网参考答案：B

2014年下半年信息系统项目管理师上午综合知识真题与解析：http://www.cnitpm.com/pm/14246.html