《数据结构》MST性质证明
发布时间:2021-04-02 00:02 所属栏目:53 来源:网络整理
导读:大家好,第六章图,第6.3小节最小生成树。MST性质的证明,课本用一了大段来证明,可能不是很便于看明白,这里给出一个网友的证明,供大家参考。 文字来自下面链接,http://fdcwqmst.blog.163.com/blog/static/164061455201010392833100/。并表示感谢。 MST性
大家好,第六章图,第6.3小节最小生成树。MST性质的证明,课本用一了大段来证明,可能不是很便于看明白,这里给出一个网友的证明,供大家参考。 文字来自下面链接,http://fdcwqmst.blog.163.com/blog/static/164061455201010392833100/。并表示感谢。 MST性质的证明??? ②而V-U中的顶点看作是蓝色顶点 ③连接红点和蓝点的边看作是橙色边 ④权最小的橙色边称为轻边(即权重最"轻"的边) 因此,MST性质中所述的边(u,v)就可简称为轻边。如下图: ?用反证法来证明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'。 如下: 很显然,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性质成立! ?? (编辑:ASP站长网) |
相关内容
网友评论
推荐文章
热点阅读