如何证明用 Kruskal's 算法生成的树是最小生成树

为了避免最小生成树不唯一的问题,可以不妨假设这个图所有的边长都不相等（注意最小生成树的总长度是原图边长的连续函数,所以可以这样加强条件）然后用反证法,假定Kruskal算法中的第k步首次出现错误,算法选了E1,但实际上必须选另一条边E2才能得到最小生成树T0E1连接了两个连通分支,这两个连通分支在最终的T0里是连通的,所以把T0和E1放在一起之后形成的图有一个环,在这个环里一定有k步或之后新选的边（如果没有的话仅凭前k-1条边和E1不会构成环）,依照E1的定义,这个环里存在比E1长的边,用E1换掉这条边之后得到的树T1比T0更短,矛盾