来自《算法竞赛进阶指南》:
给定一张无向图 G=(V,E),n=∣V∣,m=∣E∣G=(V,E),n=|V|,m=|E|G=(V,E),n=∣V∣,m=∣E∣。从 EEE 中选出 k<n−1k<n-1k<n−1 条边构成 GGG 的一个生成森林。若再从剩余的 m−km-km−k 条边中选 n−1−kn-1-kn−1−k 条添加到生成森林中,使其成为 GGG 的生成树,并且选出的边的权值之和最小,则该生成树一定包含这 m−km-km−k 条边中连接生成森林的两个不连通节点的权值最小的边。
求上述结论的证明和理解,以及依此如何来说明 Kruskal 算法的正确性。