首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
要在n个居民点之间铺设煤气管道。工人们面临如下问题: (1)设计一种付出经济代价最小的解决问题的方案。 (2)给出解决该问题的具体方法。 (3)图G是一个居民点的煤气管道铺设代价网,给出它的经济代价最小的图示。
要在n个居民点之间铺设煤气管道。工人们面临如下问题: (1)设计一种付出经济代价最小的解决问题的方案。 (2)给出解决该问题的具体方法。 (3)图G是一个居民点的煤气管道铺设代价网,给出它的经济代价最小的图示。
admin
2009-07-15
66
问题
要在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
笔试
原NCRE全国计算机四级
NCRE全国计算机四级
相关试题推荐
在浮点表示格式中,数的精度是由_________的位数决定的。
参见下面的网络拓扑结构图,一个路由器、一个集线器和一个交换机共与10台PC相连,下列说法中正确的是(21)。
在一台安装好TCP/IP协议的PC上,当网络连接不可用时,为了测试编写好的网络程序,通常使用的目的主机IP地址为_____________。
无线局域网新标准IEEE802.11n提供的最高数据速率可达到__________________。
以下关于发送电子邮件的操作中,说法正确的是_____________。
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。【说明】函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。【函数】voidQuickSort(intA[],ints,intt){
Windows系统安装时生成的Documents and Settings、Winnt和System32文件夹是不能随意更改的,因为它们是(16)。在Windows文件系统中,(17)是一个合法的文件名;(18)不是合法的可执行文件的扩展名。
对于顺序存储的队列,存储空间大小为n,头指针为F,尾指针为R。若在逻辑上看一个环,则队列中元素的个数为(47)。
某银行信贷额度关系credit-in(C_no,C_name,limit,Credit_balance)中的4个属性分别表示用户号、用户姓名、信贷额度和累计消费额。该关系的(60)属性可以作为主键。下表为关系credit-in的一个具体实例。查
WhichUNIXcommandcreatesasymboliclinknamedmyfileinthecurrentdirectorytothefile/etc/hosts?()
随机试题
下列结构中,属于膝关节囊内韧带的是()
患者,男,14岁。恒牙牙合,上下牙弓I度拥挤,上下前牙前突,前牙覆牙合覆盖基本正常,磨牙中性关系,FH﹣MP39°,侧面型凸在骨骼分型上,患者最有可能为
鼻咽部横断面CT扫描的体位与基线是
下列哪一项不是公共场所经常性卫生监督内容
首选用于治疗泌尿系疾病水肿与伤阴并见者的方剂是
下列不属于货币市场的特征的是()。
下列属于绩效反馈面谈实施阶段内容的是()。
各种学堂一律改称学校,监督、堂长一律改称校长,这是在()《普通教育暂行办法》中作出的规定。
某企业2008年12月31日的资产负债表(简表)如下:该企业2008年的营业收入净额为6000元,营业净利率为10%,股利支付率为50%。预计2009年营业收入净额比上年增长25%,为此需要增加固定资产200元,增加无形资产10
设函数f(x)在区间I上有定义,若实数x0∈I,且满足f(x0)=x0,则称x0为f(x)在区间I上的一个不动点,设函数f(x)=3x2+,则称f(x)在区间(0,+∞)上是否有不动点?若有,求出所有的不动点;若没有,说明理由。
最新回复
(
0
)