第 41 题
（10 分）下面有一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。 试判断这种方法是否正确。如果正确，请说明理由；如果不正确，举出反例（注：圈就是回路）。
[tag_link]
**【答案】** 正确
**【解析】** 连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n-1 条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩 n-1 条边为止。
[图片]
破圈法的正确性基于最小生成树的一个关键性质：在连通无向图的任意一个圈中，权值最大的边一定不属于任何最小生成树（如果边权互异，则该边绝对不在最小生成树中；如果边权有重复，则存在至少一个最小生成树不包含该边）。执行破圈法时，每次任选一个圈并去掉其中权最大的边，相当于移除了一条不在最小生成树中的边，且由于圈是连通的，去掉一条边不会破坏图的连通性。反复执行这一操作，直到图中没有圈为止，此时得到的图是连通且无环的，即为一棵生成树。由于去除的边都不在最小生成树中，而剩下的边数恰好为顶点数减一，因此这棵生成树就是最小生成树。综上，破圈法是求解最小生成树的一种正确方法。