图的最小割问题与Stoer-Wagner算法

问题描述
图的最小割问题是指在无向带权图中，找到一个边的集合，使得移除这些边后图被分为两个连通分量，且这些边的权重之和最小。最小割在图论、网络优化等领域有重要应用。Stoer-Wagner算法是一种高效求解无向图全局最小割的算法，时间复杂度为O(nm + n² log n)，其中n为顶点数，m为边数。

关键概念

1. 割：将顶点集V划分为两个非空子集S和T，割的权值是连接S和T的所有边的权重和。
2. 全局最小割：所有权值最小的割中，权值最小的那个可能不包含指定顶点，需要全局求解。

算法步骤详解
Phase 1: 最小割阶段（Min-Cut Phase）
目标：找到当前图的某个最小割（s-t最小割），并合并最后两个顶点。
步骤：

1. 初始化：

   • 设集合A初始为空，选择一个任意顶点（如第一个顶点）加入A。
   • 定义权值函数w(u, v)为顶点u与v之间边的权重（若无边则为0）。

2. 贪心扩展集合A：

   • 每次选择与A连接权值最大的顶点加入A。具体地，计算每个不在A中的顶点z与A的总连接权值：

\[ w(A, z) = \sum_{v \in A} w(z, v) \]

• 选择使w(A, z)最大的z加入A，并记录该次加入时的权值为当前割的权值。
• 重复直到A包含所有顶点。最后加入的两个顶点记为s和t（s在倒数第二步加入，t最后加入）。

3. 合并顶点s和t：
   • 将s和t合并为一个新顶点，边权合并：对于其他顶点u，新权值w(u, 合并点) = w(u, s) + w(u, t)。
   • 删除自环边（连接s和t的边）。

Phase 2: 递归求解

• 对合并后的新图递归执行Phase 1，直到图只剩一个顶点。
• 在所有Phase 1过程中记录的割权值中，取最小值作为全局最小割的权值。

为什么算法有效？

• 关键引理：在任意一个Min-Cut Phase中，最后加入的顶点t与之前集合构成的割（即最后一步的w(A, t)）是当前图的一个最小割。
• 通过合并s和t，确保至少有一个最小割不会因合并而丢失（因为s和t在最小割的同一侧）。
• 递归缩小图规模，最终覆盖所有可能的最小割情况。

示例演示
考虑一个4顶点图：顶点1-2权值3，1-3权值2，2-3权值2，2-4权值2，3-4权值3。

1. 初始A={1}，计算w(A,2)=3, w(A,3)=2, w(A,4)=0，选顶点2加入A（割值3）。
2. A={1,2}，计算w(A,3)=w(1,3)+w(2,3)=4, w(A,4)=w(2,4)=2，选顶点3加入A（割值4）。
3. A={1,2,3}，w(A,4)=w(2,4)+w(3,4)=5，选顶点4加入A（割值5）。
   • 最后加入的s=3, t=4，当前最小割权值为5（对应划分{1,2,3}和{4}）。
4. 合并顶点3和4：新图顶点为1、2、合并点(3,4)。边权更新：1-合并点=2+0=2，2-合并点=2+2=4。
5. 递归新图：A初始={1}，选顶点2加入（割值w(1,2)=3），再选合并点加入（割值w(A,合并点)=4）。最小割权值min(5,3,4)=3。
   最终全局最小割权值为3（对应移除边1-2和2-3? 需回溯实际划分）。

总结
Stoer-Wagner算法通过贪心扩展和顶点合并，将全局最小割问题转化为一系列s-t最小割问题，避免了对所有顶点对的枚举。其核心在于每次Min-Cut Phase中确定的割是当前图的最小割，且合并操作保留最小割结构。