《数据结构》MST性质证明

大家好,第六章图,第6.3小节最小生成树。MST性质的证明,课本用一了大段来证明,可能不是很便于看明白,这里给出一个网友的证明,供大家参考。

文字来自下面链接,http://fdcwqmst.blog.163.com/blog/static/164061455201010392833100/。并表示感谢。

MST性质的证明??

?
最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中一条“一个端点在U中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)。

关于这个性质的证明过程,网上的资料不多,即使有,也不是很全面或者证明过程不够细节,我也是花了很长时间才弄清楚的,其实很简单,下面大家看看我是怎么证明的:

为了方便下面的证明过程,预先做一些约定:

①将集合U中的顶点看作是红色顶点

②而V-U中的顶点看作是蓝色顶点

③连接红点和蓝点的边看作是橙色边

④权最小的橙色边称为轻边(即权重最”轻”的边)

因此,MST性质中所述的边(u,v)就可简称为轻边。如下图:

《数据结构》MST性质证明

?用反证法来证明MST性质的正确性,假设G中任何一棵最小生成树都不含轻边(u,v)。则若T是G的一棵最小生成树,则它不含此轻边。

?由于T是包含了G中所有顶点的连通图,所以T中必有一条从红点u到蓝点v的路径P,而且路径P中必定包含一条橙色边(u’,v’)连接红点集和蓝点集,否则u和v不可能连通。我们假设
u-a-u’-v’-v 就是这样的一条路径,看下面的图:

?

当把轻边(u,v)加入树T时,该轻边和P明显构成了一个回路。删去紫边(u’,v’)后回路亦消除,由此可得另一生成树T’。 如下:

《数据结构》MST性质证明

很显然,T’和T的差别仅仅在于T’用轻边(u,v)取代了T中权重可能更大的橙色边(u’,v’)。因为(u’,v’)的权重不可能比(u,v)小,由反证法的原理可知我们的前提条件里已经说明,所有橙色边里最小的一条边称为轻边,因为(u,v)是已经假定了的轻边,因此,必定有如下关系式:

w(u,v)≤w(u’,v’)


所以,
w(T’)=w(T)+w(u,v)-w(u’,v’) ? ≤? w(T)
故此T’也是G的一颗最小生成树,但是它包含(u,v),这与假设是矛盾的,所以,MST性质成立!

??

相关文章

发表回复

您的电子邮箱地址不会被公开。