要在n个居民点之间铺设煤气管道。工人们面临如下问题： (1)设计一种付出经济代价最小的解决问题的方案。 (2)给出解决该问题的具体方法。 (3)图G是一个居民点的煤气管道铺设代价网，给出它的经济代价最小的图示。

admin2009-07-15 91

问题要在n个居民点之间铺设煤气管道。工人们面临如下问题：
(1)设计一种付出经济代价最小的解决问题的方案。
(2)给出解决该问题的具体方法。
(3)图G是一个居民点的煤气管道铺设代价网，给出它的经济代价最小的图示。

选项

答案每个居民点与其余n-1个居民点之间都可能铺设煤气管道，因此，在n个居民点之间，最多可能铺设n(n-1)/2条煤气管道，而连接n个居民点的煤气管道最少需要n-1条。也就是说，只需要n-1条管道就可以把n个居民点间的煤气管道连通，而要代价最小，这就是求图中网的最小生成树问题，即把居民点看成图的顶点，把居民点之间的煤气管道看作边，而把铺设管道的代价当作权付给相应的边，这样便构成一个带权图，即网，此网的一棵最小生成树即为代价最小的铺设管道路径。 (2)求网的最小生成树的方法为：将网中的边按其权值由小到大的次序顺序选取，若选某边后不形成回路，则将其保留为最小生成树的一条边，若选某条边后形成回路，则将其舍弃，以后不再考虑，如此依次进行，直到选够(n-1)条边即得到此网的一棵最小生成树。(注：按此法生成的最小生成树不惟一) (3)图G的最小生成树为： [*]

解析

转载请注明原文地址:https://www.kaotiyun.com/show/2RNZ777K

最新回复(0)

要在n个居民点之间铺设煤气管道。工人们面临如下问题： (1)设计一种付出经济代价最小的解决问题的方案。 (2)给出解决该问题的具体方法。 (3)图G是一个居民点的煤气管道铺设代价网，给出它的经济代价最小的图示。

笔试

原NCRE全国计算机四级

NCRE全国计算机四级

TCP/IP协议簇包含多个协议，它们之间必须满足特定的封装关系，下面的选项中正确的是______。

关于SNMP协议，下面的论述中不正确的是(49)。

按照VLAN中继协议的规定，交换机运行在__________________模式时可以进行VLAN配置，但是配置信息不会传播到其他交换机。

以下关于CPU的叙述中，正确的是_________。

下列选项中，防范网络监听最有效的方法是______。

IPv4分组首部中第一个字段为_________。

CPU执行指令时，先要根据程序计数器将指令从内存读取并送入_________，然后译码并执行。

阅读以下说明和c函数，将应填入(n)处的字句写在答题纸的对应栏内。【说明1】函数Counter(intn，intw[])的功能是计算整数n的二进制表示形式中1的个数，同时用数组w记录该二进制数中1所在位置的权。例如，十进制数22的二进制表示

A______systemplacedbetweenthecompanynetworkandtheoutsideworldmaylimitoutsideaccesstotheinternalnetwork.

下列关于定期预算和滚动预算的说法中，正确的有()。

试述马克思主义政党在社会主义事业中的地位和作用。

为制止侵权行为，权利人在起诉前向人民法院申请保全证据。保全方法正确的有()。

全国人大及其常委会授权国务院制定的税收暂行条例属于税收法律，全国人大授权地方人大制定的税法为税收部门规章。()

下列关于我国各类基金销售方式的特点，说法错误的是()。

关于需要层次理论在管理上的应用的说法，错误的是()。

下列关于伦理的说法正确的是：()。

征收土地的，按照被征收土地的原用途给予补偿。征收耕地的补偿费用包括()。

下列叙述中正确的是()。