什么是生成子树？
对于一个图G=(V, E)，其生成子图G'=(V, E')是一个树，则称G'为G的生成子树。
什么是最小生成树？
而最小生成树是指，一个图的所有生成子树中，所有边权之和最小的那一个生成子树。
如何求一个图的最小生成树？
求解一个图的最小生成树问题常用的两种方法是Kruscal算法与Prim算法。
在这篇文章中，给出对Kruscal算法的一个证明。
Kruscal算法
直观思路：在图G中，去权重最小的边，然后选取与已经选择的边不构成一个回路且边权最小的边，对余下的图重复这个步骤，直到G中没有边可选为止，即可以得到G的一个最小生成树。
算法步骤：
给定带权连通图G=(V, E)，图中的边权函数为w。
（1）令F=∅
（2）当存在一条不属于F的边α，使得F∪{α}中不包含图G的一个回路时，确定这样的一条最小的边α，并将其放入F中
（3）若|F|=|V|-1，则返回图G'=(V, F)
Kruscal算法的正确性证明
首先做出如下前提假设：给定图G，边权函数w。令T为通过Kruscal算法得到的一个最小生成树；令U为图G真实的一个最小生成树。
我们已知Kruscal算法是正确的，所以我们通常认定T=U。但是我们在这里想要证明Kruscal算法的正确性，因此我们需要证明T=U。
对于T与U，我们对其关系进行分类讨论：
（1）如果T=U
那么证明结束，我们认为通过Krsucal算法得到的最小生成树就是图G的最小生成树。
（2）如果T != U
那么我们的目的就是要证明，T和U的构造代价相同，也即是说，T与U都是最小生成树，但是是两颗不同的最小生成树。
由于T != U，因此一定存在k (k>0) 条边，存在于T中而不存在于U中。
因此，我们做如下k次变换，对于每一次变换，我们有：
a) 从T中选取一条不在U中的最小的边e，将e加入到U中
b) 由于生成树的性质，将e加入U后，U中必定会产生一个回路，在这个回路中，选择一条在U中而不在T中的边f，从U中删除f
经过变换后，U仍是一颗生成树。对于e与f的关系，我们对其关系进行分类讨论：
1、w(e)<w(f)
在这种情况下，经过变换后的U的所有边权的和要小于变换前的所有边权的和，而这和我们的假设“U是最小生成树”是矛盾的。
2、w(e)>w(f)
在这种情况下，由于f的边权较小，按照Kruscal算法，f应当在e之前被选中才对，但是却没有选，因此原因必然是选取f会与那些边权小于f的边构成一条回路，但是U中的这些边却没有和f构成回路，这显然是矛盾的。
因此只有可能是w(e)=w(f)。在这种情况下，T != U但是他们的构造代价相同，也即是说，他们是两个不同的最小生成树。
