要在n个居民点之间铺设煤气管道。工人们面临如下问题:(1)设计一种付出经济代价最小的解决问题的方
要在n个居民点之间铺设煤气管道。工人们面临如下问题：
(1)设计一种付出经济代价最小的解决问题的方案。
(2)给出解决该问题的具体方法。
(3)图G是一个居民点的煤气管道铺设代价网，给出它的经济代价最小的图示。
正确答案：每个居民点与其余n-1个居民点之间都可能铺设煤气管道因此在n个居民点之间最多可能铺设n(n-1)/2条煤气管道而连接n个居民点的煤气管道最少需要n-1条。也就是说只需要n-1条管道就可以把n个居民点间的煤气管道连通而要代价最小这就是求图中网的最小生成树问题即把居民点看成图的顶点把居民点之间的煤气管道看作边而把铺设管道的代价当作权付给相应的边这样便构成一个带权图即网此网的一棵最小生成树即为代价最小的铺设管道路径。(2)求网的最小生成树的方法为：将网中的边按其权值由小到大的次序顺序选取若选某边后不形成回路则将
词条内容仅供参考，如果您需要解决具体问题
（尤其在法律、医学等领域），建议您咨询相关领域专业人士。