最小生成树
在无向图中选出\(|V|-1\)条边，使得生成树的边权和最小，这就是最小生成树问题。
我们有一个看上去有些草率的做法：给所有边按照权值从小到大排序，假设所有边都消失了，那么以从小到大的顺序加边（如果这条边对应的两点间已经有路径就跳过不加），等到加完第\(|V|-1\)条边时，我们会得到一棵“生成树”。由于每一次我们都在选择当前最优的策略，我们并没有自信我们得到的生成树就是“最小生成树”。但神奇的是，我们可以证明，这就是最小生成树。这就是最小生成树的Kruscal算法。
我们归纳地证明：当我们以从小到大的顺序加入两端点原本并不连通的一条边\((u,v)\)时，一定存在以先前已经选择的边和这条边为基础构成的某棵最小生成树。我们取一个包含\(u\)的点的集合\(S\)，以及它的补集\(T\)，要求这两个集合之间没有任何横跨的边是已经被选取了的（这是容易做到的，不妨把\(S\)设成\(u\)出发的连通块，\(T\)是其余的点）。假设不存在这样的最小生成树，那么随意取出某棵最终的最小生成树，点\(u\)和点\(v\)虽然不是树边，但通过生成树一定有一条路径相通，这条路径和边\((u,v)\)恰好形成了一个环。并且，这条路径一定经过了另一条横跨边，记为\((p,q)\)。由于我们是从小到达取边的，而此时\((p,q)\)一定还没有被取，因此其权值必须比\((u,v)\)大或与\((u,v)\)相同。这时我们发现，如果我们断开\((p,q)\)这条边，连接\((u,v)\)这条边，我们依然能形成一棵生成树——断开\((p,q)\)时，生成树变成了两个连通块，由于\(p,u\)同属一个连通块，\(q,v\)同属一个连通块，所以\((u,v)\)会再次连通这两个连通块。\(n-1\)条边的\(n\)个点的连通块一定形成树（归纳证明）。如果\((p,q)>(u,v)\)，那么我们得到了一棵更小的生成树，矛盾；如果\((p,q)=(u,v)\)，那么我们得到了一棵包含\((u,v)\)的最小生成树，矛盾。于是我们证明了Kruscal算法是正确的。