文档介绍：关于组合数学克鲁斯卡尔定理的证明
现在学习的是第1页，共14页
如何证明
假设:这个算法终止于T有n-1条边
：
假设G是一个有n个顶点和e条边的图。那么G是树当且仅当G没有回路且n=e+1.
证明T是一棵关于组合数学克鲁斯卡尔定理的证明
现在学习的是第1页，共14页
如何证明
假设:这个算法终止于T有n-1条边
：
假设G是一个有n个顶点和e条边的图。那么G是树当且仅当G没有回路且n=e+1.
证明T是一棵树，是G的一棵支撑树。
因此，G是连通的图
若算法将终止于没有找到有n-1条边的集合T。 则G是非连通的图
现在学习的是第2页，共14页
分为两部分证明
现在学习的是第3页，共14页
：
如果G是n个顶点的联通网络，Kruskal算法将终止于一个有n-1条边的最小支撑树T。
如果G是非连通网络，那么算法在检查所有边之后，T中仍没有n-1条边，这时它将停止并输出G是非连通的信息。
证明思想：
：
(1)证明这个算法的确给出的是支撑树
(2)证明这个支撑树是最小的。
证明算法终止时没有给出有n-1条边的T
现在学习的是第4页，共14页
证明：
(1)若算法给出有n-1条边的T
：
假设G是一个有n个顶点和e条边的图。那么G是树当且仅当G是连通的且n=e+1.
则能证明算法给出的T是支撑树
现在学习的是第5页，共14页
(2)想要证明Kruskal生成的支撑树T是最小支撑树
1
2
5
4
6
3
5
6
9
19
11
26
21
1
2
3
4
5
6
5
6
11
14
14
14
18
16
16
要证明支撑树T是最小的。
反证法:
假设T不是最小支撑树
假设S是G的一棵最小支撑树
S≠T
现在学习的是第6页，共14页
e1(x,y):为第一条在T中而不在S中的边
这时会出现两种情况
情况1：e1的权值>e2的权值
情况2：e1的权值<e2的权值
Kruskal生成的支撑树T
1
2
5
4
6
3
14
16
5
6
11
e1
假设的最小支撑树S
1
2
5
4
6
3
14
16
5
6
e2
x
y
X
Y
S中存在一条简单链C(x,y),与e1(x,y)构成回路
在链C(x,y)中存在一条在S中但不在T中的边e2
现在学习的是第7页，共14页
情况1：e2的权值<e1的权值
1
2
5
4
6
3
14
16
5
6
11
e1
Kruskal生成的支撑树T
1
2
5
4
6
3
14
16
5
6
假设的最小支撑树S
9
e2
因为e1是第一条在T中但不在S中的边
所以T中在e1之前被找到的边也一定在S中出现
既然e2<e1，为什么T选择了e1却没选择e2
因为e2与e1之前出现的边形成了回路，所以T选择了边e1
因为S是支撑树，S中不能有回路
所以与假设矛盾
那么情况1不成立
现在学习的是第8页，共14页
情况2：e1的权值<e2的权值
S′:是从S中去除边e2，加上边e1的边的集合
S′=S-e2+e1(权值)
1
2
5
4
6
3
14
16
5
6
1
2
5
4
6
3
14
16
5
6
假设的最小支撑树S
1
2
5
4
6
3
14
16
5
6
e2
1
2
5
4
6
3
14
16
5
6
1
2
5
4
6
3
14
16
5
6
支撑树S’
1
2
5
4
6
3
14
16
5
6
e2
e1
现在学习的是第9页，共14页
情况2：e1的权值 < e2的权值
S′=S-e2+e1(权值)
1
2
5
4
6
3
14
16
5
6
1
2
5
4
6
3
14
16
5
6
假设的最小支撑树S
1
2
5
4
6
3
14
16
5
6
e2
1
2
5
4
6
3
14
16
5
6
1
2
5
4
6
3
14
16
5
6
支撑树S’
1
2
5
4
6
3
14
16
5
6
又因为S是最小支撑树
所以S