064-图论-全局最小割

1. YAML 元数据 已设置 tags: [KACTL, 图论, 核心概念]。

2. 核心概述 在无向非负边权图上，通过“最小割阶段 + 缩点”迭代求得不指定源汇对的全局最小割，典型复杂度 O(N^3)。

3. 原文引述

Description: Global minimum cut of an undirected weighted graph using the Stoer–Wagner algorithm (“minimum cut phases” with contractions). Time: O(N^3) (or O(MN + N^2 log N) with appropriate data structures)

4. 展开阐述

• 定义与背景

  • 问题：给定无向带权图 G，寻找将顶点集划分为两部分 S 与 V\S 的割，使跨割边权和最小（全局最小割），不预先指定 s、t。
  • 背景：与 s–t 最小割不同，全局最小割不固定端点；Stoer–Wagner 通过反复“阶段”和“缩点”在多次候选中取最小值即为结果。

• 接口/数据结构（据实现习惯）

  • minCut(G)：返回全局最小割权值；G 可为邻接矩阵或邻接表（需保持对称 w[u][v]=w[v][u]），自环忽略，多边权可累加。
  • 如需割集一侧 S，可在最后一次阶段按加入序列回溯恢复。

• 核心流程/要点（Stoer–Wagner）

  1. 阶段（Maximum Adjacency Search）
     • 从任一点 a0 出发，反复将“对当前集合 S 的连接权和最大”的顶点加入 S，直到加入所有顶点。
     • 记最后加入的顶点为 t，倒数第二个为 s，则在该阶段得到的候选割值即 t 到 S{t} 的连接权和。
  2. 记录候选答案
     • 用 ans 维护所有阶段的最小割值；可在该阶段保存 S 以供恢复割集。
  3. 缩点
     • 将 s 与 t 缩并为超点，边权合并；图规模减少 1；继续下一阶段，直到只剩 1 个超点。
  4. 终止
     • 所有阶段的最小值即为全局最小割。

• 复杂度与边界条件

  • 复杂度：朴素实现 O(N^3)；用堆维护“到 S 的连接权”和可达 O(MN + N^2 log N)。
  • 权值与图型：要求无向、非负边权；自环忽略；重边可合并。
  • 矩阵约定：邻接矩阵常设 w[i][i]=0，且保持对称。
  • 连通性：若图不连通，全局最小割为 0（空割），实现上可能在第一阶段即出现 0 候选。

• 变体/扩展与关系

  • 与 s–t 最小割（最大流对偶）：若关心固定端点对，改用最大流（如 057-图论-Dinic最大流、060-图论-EdmondsKarp、076-图论-PushRelabel）。
  • 与 Gomory–Hu 树：GH 树通过 N−1 次 s–t 最小割刻画所有点对最小割，若需要批量点对查询更适合（见 065-图论-GomoryHu树）。
  • 对比全源最短路：最小割关注“容量/割”，与最短路的“路径长度”性质不同。

• 正确性要点与不变式

  • 阶段末 (S, V\S) 的割值即 t 到 S{t} 的连接权和，取所有阶段最小者即全局最小割。
  • 缩点不改变任何剩余顶点对之间的最小割值（对任意两点 u,v，其 mincut 在缩并过程中保持）。

• 与相邻技术的取舍建议

  • 若仅需全局最小割值，Stoer–Wagner 直接高效；
  • 若需任意点对最小割或多次 s–t 查询，优先 GH 树或在流框架上重复最小割。

5. 关联节点

• 065-图论-GomoryHu树
• 074-图论-最小割
• 057-图论-Dinic最大流
• 076-图论-PushRelabel