流网络最小割中最大化S集合的算法修改可行性求证

核心思路 #

要让最小ST割中的S集合尽可能大，本质是找到所有最小割中最小的T集合——仅包含必须属于T的节点，剩余节点自然构成最大的S集合。

具体算法步骤 #

• 用Edmonds-Karp（EK）算法计算流网络的最大流
• 构建原残差网络的反向图：翻转所有边的方向，边的残差容量保持不变
• 在该反向图上，从汇点t出发执行BFS，仅遍历残差容量为正的边
• 所有从t可达的节点，就是所有最小割中必然属于T集合的节点；其余节点组成的集合即为最大的S集合

推导验证 #

在最小ST割中，所有S→T方向的边都已饱和，因此原残差网络中这类边的残差容量为0。翻转边的方向后，这些跨割边变为T→S方向，残差容量仍为0，无法被BFS遍历。

而反向图中T→S方向残差容量为正的边，要么是原网络中S→T方向未饱和的边，要么是原网络中T→S方向的反向边——这类边不可能跨越最小割（否则会违背最小割的饱和性）。因此从t出发的可达路径必然全部停留在T集合内，由此得到的T集合是所有最小割中最小的，仅包含必须属于T的节点，对应的S集合就是最大的最小割S集合。

内容的提问来源于stack exchange，提问作者Leah Golub