因为题目要求没两个点间必须存在通路。
故满足条件的任意方案为一生成树（spanning tree)
1.先证最小生成树T的最长边（u，v）小于等于任一生成树T的最长边
反证：假设不满足上述命题，即：存在一个生成树T'，其最长边小于(u,v)
则有T'的任一边 <= T’最长边 < (u,v)，
因为T'是生成树，则其上u,v两点间必存在唯一通路P;
由于u,v位于(u,v)所通过的某割的两边，P上必有一边(x,y)通过割且(x,y)<(u,v)
在T上去掉(u,v)加上(x,y)形成T''可证T‘’仍然是生成树且所有边权值和小于T的权值和。与T是最小生成树矛盾。得证
2.再证存在一个可达的方案，其最长边等于(u,v)，即1中的下限是紧确的。
 显然，只要选取最小生成树为所选方案即可得

综上所述，最小生成树的最长边即为题目所述任一生成树的最长边的最小值

• Re:关于最小生成树的最长边为所求的证明 (276) eiwoqu 2014-12-11 18:43:52
• Re:关于最小生成树的最长边为所求的证明 (160) ryx 2015-05-09 11:09:37