首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
要在n个居民点之间铺设煤气管道。工人们面临如下问题: (1)设计一种付出经济代价最小的解决问题的方案。 (2)给出解决该问题的具体方法。 (3)图G是一个居民点的煤气管道铺设代价网,给出它的经济代价最小的图示。
要在n个居民点之间铺设煤气管道。工人们面临如下问题: (1)设计一种付出经济代价最小的解决问题的方案。 (2)给出解决该问题的具体方法。 (3)图G是一个居民点的煤气管道铺设代价网,给出它的经济代价最小的图示。
admin
2009-07-15
46
问题
要在n个居民点之间铺设煤气管道。工人们面临如下问题:
(1)设计一种付出经济代价最小的解决问题的方案。
(2)给出解决该问题的具体方法。
(3)图G是一个居民点的煤气管道铺设代价网,给出它的经济代价最小的图示。
选项
答案
每个居民点与其余n-1个居民点之间都可能铺设煤气管道,因此,在n个居民点之间,最多可能铺设n(n-1)/2条煤气管道,而连接n个居民点的煤气管道最少需要n-1条。也就是说,只需要n-1条管道就可以把n个居民点间的煤气管道连通,而要代价最小,这就是求图中网的最小生成树问题,即把居民点看成图的顶点,把居民点之间的煤气管道看作边,而把铺设管道的代价当作权付给相应的边,这样便构成一个带权图,即网,此网的一棵最小生成树即为代价最小的铺设管道路径。 (2)求网的最小生成树的方法为:将网中的边按其权值由小到大的次序顺序选取,若选某边后不形成回路,则将其保留为最小生成树的一条边,若选某条边后形成回路,则将其舍弃,以后不再考虑,如此依次进行,直到选够(n-1)条边即得到此网的一棵最小生成树。(注:按此法生成的最小生成树不惟一) (3)图G的最小生成树为: [*]
解析
转载请注明原文地址:https://jikaoti.com/ti/8fE7FFFM
0
笔试
原NCRE全国计算机四级
NCRE全国计算机四级
相关试题推荐
以下木马程序的描述中,正确的是________。
通过(11)关系运算,可以从表1和表2获得表3。
在Windows的命令窗口输入命令C:\>routeprint10.*这个命令的作用是_____________。
电子邮件应用程序利用POP3协议(47)。
Flash动画中使用(12)作为基本的图形存储形式。
请将图6-13流程图中(1)~(5)空缺处的内容补充完整。其中,(1)空缺处按“循环变量名:循环初值,增量,循环终值”格式描述。待修改的【C程序】中存在3个错误,请指出各个错误所在的行号,并给出相应的修改意见。
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。【说明】设串s和串t采用顺序存储结构,编写函数实现串s和串t的比较操作,要求比较结果包括大于、小于和等于3种情况。【函数】intStrCompare(SSt
假设某计算机有IMB的内存,并按字节编址,为了能存取其中的内容,其地址寄存器至少需要(9)位。为使4B组成的字能从存储器中一次读出,要求存放在存储器中的字边界对齐,一个字的地址码应(10)。若存储周期为200ns,且每个周期访问4B,则该存储器按bit存储
虚拟存储器的作用是允许(4),它通常使用(5)作为主要组成部分。虚拟存储器的调度方法与(6)基本类似,即把经常要访问的数据驻留在高速存储器中。因为使用了虚拟存储器,指令执行时(7)。在虚拟存储系统中常使用柜联存储器进行管理,它是(8)寻址的。
In C language, there are several methods of communicating data between functions, one of which is by(51)。
随机试题
电动式动力转向系统利用电动机作为_______,根据车速和转向参数等,由电子控制单元完成助力控制。电动式动力转向系统通常由扭矩传感器、车速传感器、电子控制单元(ECU)、电动机和电磁离合器等组成。
下列选项中,符合液的功能的有()(2011年第126题)
下列选项中,不属于生理性带下范畴的是
混凝土回弹仪在出/人检测室时,需完成()工作。
港口建筑物地基土为超同结土,其自重应力至先期固结压力段应按()计算沉降量。
遥感物探,是指在距离相当遥远的位置上,用各种传感器探知地面物体辐射(或反射)的电磁波信息,以查明地质的或地学的各种情况的方法。根据上述定义,下列属于遥感物探的是()。
A:CouldyougetmeExtension6459,please?B:______.
简述债权人的代位权成立的条件。
NewYorkersdoit.Parisiansdoit.Fashiontypes,Swedesandarchitectsdoit.Infact,nameanystylishtribeandyou’llfind
•Readthearticlebelowaboutasuccessfulprintingfirm.•Choosethebestwordtofilleachgap,fromA,B,CorDontheoppos
最新回复
(
0
)