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

admin2009-07-15 68

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

选项

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

解析

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

最新回复(0)

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

笔试

原NCRE全国计算机四级

NCRE全国计算机四级

在windows系统中，将指针移向特定图表时，会看到该图表的名称或某个设置的状态。例如，执行________图表将显示计算机当前音量级别。

下面选项中，(56)不能实现安全邮件传输。

Windows命令行输入()命令后得到下图所示的结果。

在Windows的cmd命令行窗口中，输入__________________命令将会得到如下图所示的结果。

显示结果为如下超链接的HTML语句是(45)。

下图是在Linux系统中用ls命令查看文件信息的输出结果，可以判断命令行输入的完整命令是(42)，当前目录的下级目录是(43)，当前目录中的可执行文件是(44)，当前用户是(45)。

若程序中使用的变量未设置初始值，则(13)。

In　which　phase　of　the　software　engineering　process　is　the　Software　Requirements　Specification　developed?(68).

某硬盘中共有9个盘片，16个记录面，每个记录面上有2100个磁道，每个磁道分为64个扇区，每扇区为512字节，则该硬盘的存储容量为(18)MB，磁道的位密度随着磁道从内向外而(19)。

技术市场

龟鹿二仙膏除温肾化补精外，又能()。

用事故发生的频率和事故后果的严重程度来判断安全风险的等级时，若事故发生的频率极小，事故后果的严重程度为重大损失(严重伤害)，则安全风险所属的等级为()。

根据会计准则和相关规定，企业发生亏损时，应由企业自行弥补，弥补亏损的渠道有()。

为了加强对会计电算化的管理，财政部于1994年7月1日以后发布了《会计电算化管理办法》、《商品化会计核算软件评审规则》、《会计核算软件基本功能规范》和()。

甲打算抢银行，请乙帮他开车，并许诺事成之后一人一半。乙假意答应后，去公安机关告发了甲，甲的行为属于()

()罗杰斯将自我分为理想自我和现实自我。

【B1】【B10】

Shestudiedhardatschoolwhenshewasyoung,________contributestohersuccessinhercareer.

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

笔试

原NCRE全国计算机四级

NCRE全国计算机四级

在windows系统中，将指针移向特定图表时，会看到该图表的名称或某个设置的状态。例如，执行________图表将显示计算机当前音量级别。

下面选项中，(56)不能实现安全邮件传输。

Windows命令行输入()命令后得到下图所示的结果。

在Windows的cmd命令行窗口中，输入__________________命令将会得到如下图所示的结果。

显示结果为如下超链接的HTML语句是(45)。

下图是在Linux系统中用ls命令查看文件信息的输出结果，可以判断命令行输入的完整命令是(42)，当前目录的下级目录是(43)，当前目录中的可执行文件是(44)，当前用户是(45)。

若程序中使用的变量未设置初始值，则(13)。

In which phase of the software engineering process is the Software Requirements Specification developed?(68).

某硬盘中共有9个盘片，16个记录面，每个记录面上有2100个磁道，每个磁道分为64个扇区，每扇区为512字节，则该硬盘的存储容量为(18)MB，磁道的位密度随着磁道从内向外而(19)。

技术市场

龟鹿二仙膏除温肾化补精外，又能()。

用事故发生的频率和事故后果的严重程度来判断安全风险的等级时，若事故发生的频率极小，事故后果的严重程度为重大损失(严重伤害)，则安全风险所属的等级为()。

根据会计准则和相关规定，企业发生亏损时，应由企业自行弥补，弥补亏损的渠道有()。

为了加强对会计电算化的管理，财政部于1994年7月1日以后发布了《会计电算化管理办法》、《商品化会计核算软件评审规则》、《会计核算软件基本功能规范》和()。

甲打算抢银行，请乙帮他开车，并许诺事成之后一人一半。乙假意答应后，去公安机关告发了甲，甲的行为属于()

()罗杰斯将自我分为理想自我和现实自我。

【B1】【B10】

Shestudiedhardatschoolwhenshewasyoung,________contributestohersuccessinhercareer.

In　which　phase　of　the　software　engineering　process　is　the　Software　Requirements　Specification　developed?(68).