最小割问题（Stoer-Wagner算法）

题目描述
给定一个无向带权图（权重表示边的容量），求该图的全局最小割（Global Minimum Cut）。最小割是指将图划分为两个不相交子集，使得连接这两个子集的边的权重之和最小。注意，这里的图可能不是连通的，但算法要求处理一般无向图。

解题过程

1. 问题分析

   • 最小割问题在无向图中等价于求使图不连通所需删除边的最小总权重。
   • 若图有 \(n\) 个顶点，则共有 \(2^{n-1}\) 种划分，直接枚举不可行。
   • Stoer-Wagner算法通过递归合并顶点来求解，时间复杂度为 \(O(n^3)\) 或优化后 \(O(n^2 \log n)\)。

2. 算法核心思想

   • 关键观察：对于图中任意两点 \(s\) 和 \(t\)，最小割要么是 \(s$-$t\) 最小割，要么是合并 \(s\) 和 \(t\) 后新图的最小割。
   • 算法重复以下步骤直到图只剩一个顶点：
     1. 使用最大邻接搜索（Maximum Adjacency Search）找到一对顶点 \(s\) 和 \(t\)，并记录割的权重。
     2. 合并 \(s\) 和 \(t\) 为一个超级顶点，更新边权重（合并后边权重相加）。
     3. 在合并后的图中递归求解最小割，并保留所有步骤中的最小割值。

3. 最大邻接搜索（MAS）

   • 目的：找到一对顶点 \(s\) 和 \(t\)，使得割 \((t, V \setminus \{t\})\) 的权重是当前图的一个最小割候选。
   • 步骤：
     1. 从任意顶点开始（如第一个顶点），初始化一个集合 \(A\) 包含该顶点。
     2. 每次将不在 \(A\) 中但与 \(A\) 内顶点连接边权重之和最大的顶点加入 \(A\)。
     3. 最后加入 \(A\) 的两个顶点即为 \(s\) 和 \(t\)，最后加入时的权重和为当前割值。

4. 合并顶点与更新图

   • 将 \(s\) 和 \(t\) 合并为一个新顶点 \(st\)，原图中与 \(s\) 或 \(t\) 相连的边合并到 \(st\)：
     • 若某顶点 \(v\) 同时与 \(s\) 和 \(t\) 有边，则新边权重为 \(w(v,s) + w(v,t)\)。
     • 仅与其中之一相连，则保留原权重。
   • 合并后图顶点数减1，重复过程直到剩余1个顶点。

5. 示例演示
   考虑一个4顶点图：边权重为 \((A,B)=2, (A,C)=3, (B,C)=1, (B,D)=4, (C,D)=5\)。

   • 初始图：顶点集 \(\{A,B,C,D\}\)。
   • 第一轮 MAS：
     • 从 \(A\) 开始，\(A\) 的邻接权重为 \(B:2, C:3\)，选最大权重顶点 \(C\) 加入 \(A\)。
     • 更新 \(A\) 集合为 \(\{A,C\}\)，邻接权重为 \(B:2+1=3, D:0+5=5\)，选 \(D\) 加入。
     • 最后加入 \(B\)，割值为 \(w(B, \{A,C,D\}) = w(B,A)+w(B,C)+w(B,D)=2+1+4=7\)。
     • 合并 \(B\) 和 \(D\) 为新顶点 \(BD\)，更新边：\(A\) 连 \(BD\) 权重 \(2+0=2\)，\(C\) 连 \(BD\) 权重 \(1+5=6\)。
   • 第二轮 MAS：在新图 \(\{A,C,BD\}\) 中重复，得到割值并更新最小割。
   • 最终最小割为所有轮中记录的最小值（本例中为3，对应割 \(\{A\} \) 和 \(\{B,C,D\}\)）。

6. 复杂度与优化

   • 朴素实现每轮 MAS 需 \(O(n^2)\)，共 \(n-1\) 轮，总复杂度 \(O(n^3)\)。
   • 使用优先队列（如斐波那契堆）可优化 MAS 到 \(O(m + n \log n)\)，总复杂度 \(O(nm + n^2 \log n)\)。
   • 适用于稠密图（\(m\) 接近 \(n^2\)）时效率较高。

7. 总结
   Stoer-Wagner算法通过递归合并顶点和最大邻接搜索，逐步缩小图规模并记录最小割值，最终得到全局最小割。其核心在于利用割的递归性质，避免直接枚举所有划分。