首页 > 其他 > 详细

MST性质(用于构造最小生成树)

时间:2016-03-08 02:06:42      阅读:345      评论:0      收藏:0      [点我收藏+]

描述:假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。

证明:

       假设网N的任何一棵最小生成树都不包含(u,v)。设T是连通网上的一棵最小生成树,当边(u,v)加入到T中时,由生成树的定义,T中必存在一天包含(u,v)的回路。另一方面,由于T是生成树,则在T上必存在另一条边(u’,v’),其中u’∈U,v’∈V-U,且u和u’之间,v和v’之间均有路径相通。删去边(u’,v’),便可消除上述回路,同时得到另一棵生成树T’。因为(u,v)的代价不高于(u’,v’),则T’的待机亦不高于T,T’是包含(u,v)的一棵最小生成树。由此和假设矛盾。

MST性质(用于构造最小生成树)

原文:http://www.cnblogs.com/insiwhy556/p/5252552.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!