《数据结构》MST性质证明

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

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

?
最小生成树性质：设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性质成立！