最小生成树和切分定理
本文提纲
- 最小生成树
- 切分定理
- 证明
1.最小生成树
最小生成树问题，针对带权无向图，就是在一个V个结点的连通图里面寻找V-1条边，使得这个图连通，并且权值之和最小的问题。
2.切分定理(Cut Property)
- 定义一：把图中的结点分为两部分，称为一个切分(Cut)
- 定义二：如果一个边的两个端点，属于切分不同的两边，这个边称为横切边(Crossing Edge)
切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树
如图中的0.16这条边
3.证明
假如一条横切边他不是最短的，那么必然存在一条最短的边，连接两部分，否则这两部分不连通，无法构成生成树。