关于随机收缩算法：为何收缩割边无法输出目标最小割？

首先得明确随机收缩算法的核心逻辑：每次随机选一条边，把两个端点合并成一个超级顶点，重复这个过程直到图里只剩2个顶点，这两个顶点对应的原始顶点集合就是算法输出的一个割。

你疑惑的点在于收缩F中的边(C,D)后，A和B好像还存在，但实际上问题出在合并后的超级顶点打破了原割(A,B)的划分边界：

• 原割(A,B)要求一侧是所有A的顶点，另一侧是所有B的顶点，二者完全没有交集。
• 当你把A侧的C和B侧的D合并成一个超级顶点后，这个超级顶点同时包含了原A和原B的顶点。后续不管怎么收缩，最终剩下的两个顶点集合里，必然有一个集合包含这个超级顶点——也就是说，这个集合同时包含了原A和原B的部分顶点，完全不可能再对应到恰好是(A,B)的划分了。

举个简单例子：假设A={C,X}, B={D,Y}，F={(C,D)}。当你收缩(C,D)得到超级顶点CD后，剩下的顶点是CD、X、Y。后续不管收缩哪条边，最终剩下的两个集合比如是{CD,X}和{Y}，对应的原顶点集合是{C,X,D}和{Y}，显然不是原来的(A,B)；或者{CD,Y}和{X}，对应{C,D,Y}和{X}，也不是(A,B)。

所以课程里的结论是对的：只要收缩了F中的任意一条边，算法就不可能输出原最小割(A,B)了。

内容的提问来源于stack exchange，提问作者Jack Duan