现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)； i=1； while(所剩边数≥顶点数){ 从图中删去ei；若图不再连通，则恢复ei； i++；

admin2014-04-17 99

问题现有一种解决无向连通图的最小生成树的方法：
将图中所有边按权重从大到小排序为(e1，e2，…，em)；
i=1；
while(所剩边数≥顶点数){
从图中删去ei；
若图不再连通，则恢复ei；
i++；
}
请问上述方法能否求得原图的最小生成树?若该方法可行，请证明之；否则请举反例说明。

选项

答案思路分析：要证明最后生成的树是该无向连通图的最小生成树，只需证明以下两点。 (1)n个顶点的连通图的生成树有n—1条边。 (2)所构成的生成树的边的权值之和最小。结论：该方法可以求得最小生成树。证明如下： 1)从算法中while(所剩边数≥顶点数)可以得出，结束循环的条什是边数比顶点数少1停止，满足n个顶点的连通图的生成树有n—1条边的定义。 2)算法中的“若图不再连通，则恢复ei”含义是必须保留使图连通的边，这就保证了是生成树，甭则就会有同路，或者成为连通分最，都不是生成树。 3)由于边是按权值从大到小排序的，删去的边是权值大的边，结果的生成树必是最小生成树。综上所述，该办法可以求得无向连通图的最小生成树。提醒：对于这类题，考生需要对于所证明的概念具有哪种性质极其熟悉，然后根据性质各个击破。对于此题，如果考生连无向连通图的概念都不清楚，那就无从下手。所以，在复习的时候，建议重点抓一些基本概念的特征。

解析

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

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)； i=1； while(所剩边数≥顶点数){ 从图中删去ei；若图不再连通，则恢复ei； i++；

计算机408

学硕统考专业

斯大林模式的突出特点是()。

对西欧封建社会的说法不正确的是()。

以城市为重点的整个经济体制改革的中心环节是()。

汉延熹五年(162)皇甫规得罪宦官，论输左校，太学生()等三百人，跟大官僚一起诣阙陈诉，使皇甫规获得赦免。

中古时代实行索贡巡行赋税征收方式的国家是()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

蒙古军西征之后，罗斯处于()的控制之下。

开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

中国共产党在敌后战场上开创的第一块根据地是()。

强夯法和强夯置换法在施工前，应在现场有代表性的场地进行试夯或试验性施工，以取得必要的()。

地方性法规与行政法规中对同一个违法行为都有规定的，行政执法人员应该按照__________作出行政处罚？

如果客户存在运动的风险因素，应该建议其进行医学检查，然后根据医生的建议确定其是否可以运动及可采取的运动方式。在此基础上，健身教练可根据客户的()、体遗能水半及()等为其制订健身运动计划。

下列符合慢性特发性血小板性紫癜临床表现的是

以下为我国《领事特权与豁免条例》有规定，而《维也纳领事关系公约》没有规定的内容有：

工程咨询单位资格包括()。

产权界定应遵循的原则是()。

2014年11月3日，人民法院受理了甲公司的破产申请。根据企业破产法律制度的规定，下列已经开始、尚未终结的与甲公司有关的民事诉讼中，应当中止的是()。

某单位工会为了深入了解职工的工作状态。关心职工的身心健康。举办了一次“快乐工作”主题座谈会。作为一名新参加工作者．请你模拟在座谈会上作一个简短的即席讲话。(2012年7月16日上午湖南省公务员面试真题)

EmployeesoftheTaffValeRailwayCompanyinSouthWalesgreasedthetracksandcuttelegraphwiresduringabitterstrikein1

现有一种解决无向连通图的最小生成树的方法： 将图中所有边按权重从大到小排序为(e1，e2，…，em)； i=1； while(所剩边数≥顶点数){ 从图中删去ei； 若图不再连通，则恢复ei； i++；

计算机408

学硕统考专业

斯大林模式的突出特点是()。

对西欧封建社会的说法不正确的是()。

以城市为重点的整个经济体制改革的中心环节是()。

汉延熹五年(162)皇甫规得罪宦官，论输左校，太学生()等三百人，跟大官僚一起诣阙陈诉，使皇甫规获得赦免。

中古时代实行索贡巡行赋税征收方式的国家是()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

蒙古军西征之后，罗斯处于()的控制之下。

开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

中国共产党在敌后战场上开创的第一块根据地是()。

强夯法和强夯置换法在施工前，应在现场有代表性的场地进行试夯或试验性施工，以取得必要的()。

地方性法规与行政法规中对同一个违法行为都有规定的，行政执法人员应该按照__________作出行政处罚？

如果客户存在运动的风险因素，应该建议其进行医学检查，然后根据医生的建议确定其是否可以运动及可采取的运动方式。在此基础上，健身教练可根据客户的()、体遗能水半及()等为其制订健身运动计划。

下列符合慢性特发性血小板性紫癜临床表现的是

以下为我国《领事特权与豁免条例》有规定，而《维也纳领事关系公约》没有规定的内容有：

工程咨询单位资格包括()。

产权界定应遵循的原则是()。

2014年11月3日，人民法院受理了甲公司的破产申请。根据企业破产法律制度的规定，下列已经开始、尚未终结的与甲公司有关的民事诉讼中，应当中止的是()。

某单位工会为了深入了解职工的工作状态。关心职工的身心健康。举办了一次“快乐工作”主题座谈会。作为一名新参加工作者．请你模拟在座谈会上作一个简短的即席讲话。(2012年7月16日上午湖南省公务员面试真题)

EmployeesoftheTaffValeRailwayCompanyinSouthWalesgreasedthetracksandcuttelegraphwiresduringabitterstrikein1

现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)； i=1； while(所剩边数≥顶点数){ 从图中删去ei；若图不再连通，则恢复ei； i++；