图中的非循环交叉切割

Question

给定我们有一个图 G = (V,E) 和一个只有 V 的子集 F，对于 F 的每个连通分量 S，在切割 (S, V \ S) 中添加最小权重边到 F.

为什么每次给F加上最小权重的边，F还是无环的？

Answer 1

要创建循环，您必须创建连接已连接顶点的边。

如果在未连接的顶点之间添加边，则不会创建新循环。您连接两个未连接的组件。但是图仍然是非循环的。

为了更好地理解它的工作原理，您可以将图的连通分量表示为单个顶点。然后，当您在未连接的组件之间添加边时，您只需合并顶点。

顺便说一句，这道题与权重（和MST算法）无关。没有重量它仍然有效。