🏷️ 知识点：环性质

下面是一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”,是指“任取 一圈，去掉圈上权最大的边”,反复执行这一步骤，直到没有圈为止。试判断这种方 法是否正确。若正确，说明理由；若不正确，举出反例(注：圈就是回路)。

[tag_link]

参考答案

这种方法正确。

先看“最终得到树”：从连通图的一个回路中删除一条边，不会破坏连通性，因为该边的两个端点仍可沿回路中的其余边互相到达。反复删除到没有回路时，图仍连通且无环，所以得到一棵生成树。

再证明“权值最小”。设当前回路中被删除的最大权边为 e。取当前图的一棵最小生成树 T：

• 若 e 不在 T 中，删除 e 不影响 T；
• 若 e 在 T 中，删去 e 会把 T 分成两个连通分量。原回路上必有另一条跨越这两个分量的边 f，且 w(f) ≤ w(e)。用 f 替换 e 后仍为生成树，且总权值不增，因此仍能得到一棵最小生成树。

所以每次“破圈”后，剩余图中始终至少保留一棵最小生成树；最终只剩一棵生成树时，它必为最小生成树。

易错点

环上最大权边并不一定唯一。若有多条并列最大边，任删其中一条即可；不能说所有最大边都绝不属于任何最小生成树。