最小生成树之MST性质

时间:2021-07-05 09:49:06

在数据结构上看到这个性质的时候并不是很理解,觉得很抽象,所以我决定记录一下,以免以后又不理解了。

其实就是一个 最优选择问题。

原性质描述如下:

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

就先不画图了,现在把V分成U和V - U两个集合,想一下,现在已经有一棵生成树T了,所以在U和V - U之间一定有一条边连着,所以这种情况下V - U中的所有点一定是互相连通的,(u,v)这条边权最小,但是此刻并没有连着。那么就是V - U中的另一条边连接着这两个点集。那么假如把这条边换成(u ,v)了,一定比T的总权和小啊。就是酱紫。

这么说可能还有点不理解,结合一下反证法就知道了。

假设网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)的一棵最小生成树,和假设矛盾。