Mcginn's Blog

求解无向图最小割

SW
字数统计: 946阅读时长: 4 min
2021/12/26 Share

背景

Stoer-Wagner 算法求解非负边权的无向图全局最小割，即不指定源点和汇点。

割：去掉图上的若干边，使得源点 $S$ 和汇点 $T$ 不再连通。去掉的边的集合称为割。

算法

1
2
3
4
5
6
7
8
9
10
MinimumCutPhase(G, w, a)
	A ← {a}
	while A ≠ V
		加入和集合 A 连接最紧密的点，即边权和最大的点
	记录当前阶段的割值(CutOfThePhase)，并合并最后加入集合 A 的 2 个点
	
MinimumCut(G, w, a)
	while |V| > 1
		MinimumCutPhase(G, w, a)
		基于现阶段割值(CutOfThePhase)更新全局最小割的值
  • MinimumCutPhase 等同于最小生成树的 Prim 算法。

证明

定理 记 $s, t$ 是图 $G$ 的两个点，通过合并 $s, t$ 得到 $G/\{s, t\}$，则图 $G$ 的最小割是最小 $s-t$ 割或者图 $G/\{s, t\}$ 的最小割。

该定理算是比较显然的，因为 $s, t$ 要么被最小割分开，要么在最小割的同一部分中。

引理 记 $s, t$ 是当前阶段合并的 2 个点（即最后加入的 2 个点），则当前阶段的割值(CutOfThePhase)是当前图的最小 $s-t$ 割。

证明 先给出一些定义，用于后续推导：

  1. 记 MinimumCutPhase 的起点为 $a$，$s, t$ 的任一割为 $C$。

  2. 当 $v$ 的前一个加入点与 $v$ 不在 $C$ 的同一部分（e.g. 一个与源点连通，一个与汇点连通）时，记 $v$ 是一个活跃(active)点。

  3. $w(C)$ 是割 $C$ 的边权和。
  4. $A_v$ 表示 $v$ 之前加入的所有点，但不包括 $v$。
  5. $w(A, v)$ 表示集合 $A$ 和点 $v$ 之间所有连边的权值和。
  6. $C_v$ 是点集 $A_v\cup {v}$ 在割 $C$ 上的导出割(induced cut)。

证明思路：对于 $s, t$ 的任一割 $C$，有 $w(A_t, t)\le w(C)$，说明 $s, t$ 的最小割为 $w(A_t, t)$，则引理得证。

首先，对于所有的活跃点有以下推论：

使用数学归纳法证明。

  1. 对于第一个活跃点来说，该不等式显然成立。一部分点与起点 $a$ 连通，另一部分仅有 $v$ 一个点。导出割 $C_v$ 必然大于等于 $w(A_v, v)$。
  2. 记 $u$ 是 $v$ 的下一个跃点，有：

根据 MinimumCutPhase 的定义，$v=\text{argmax}_{z\notin A}\{w(A, z)\}$，因此 $w(A_v, u)\le w(A_v, v)\le w(C_v)$，继而有：

因为 $A_u\setminus A_v$ 和点 $u$ 不在同一连通块中，割 $C$ 必然包含这部分边，那么就可推导出第 2 个不等式。

根据定义，割 $C$ 分割了 $s, t$，因此 $t$ 总是一个活跃点，符合不等式 $w(A_t, t)\le w(C_t)=w(C)$，引理得证。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int N = 601;

int n, m, f[N], w[N], g[N][N];
bool vis[N];

int get(int x) {
	return x == f[x] ? x : f[x] = get(f[x]);
}

int argmax(int n, int *a, bool *v) {
	pair<int, int> rec(INT_MIN, 0);
	rep(i, 0, n) if (!v[i])
		rec = max(rec, make_pair(a[i], i));
	return rec.second;
}

int min_cut_phase(int A, int &s, int &t) {
	rep(i, 0, n) {
		w[i] = 0, vis[i] = (i != get(i));	
	}
	rep(_, A, n) {
		s = t;
		t = argmax(n, w, vis);
		vis[t] = true;
		rep(i, 0, n) if (!vis[i]) w[i] += g[t][i];
	}
	return w[t];
}

void merge_nodes(int s, int t) {
	f[get(t)] = get(s);
	rep(i, 0, n) {
		g[s][i] += g[t][i];
		g[i][s] += g[i][t];
	}
}

int stoer_wagner_mincut() {
	rep(i, 0, n) f[i] = i;

	int ans = INT_MAX;
	rep(i, 1, n) {
		int s, t, cut_of_the_phase;
		cut_of_the_phase = min_cut_phase(i - 1, s, t);
		if (cut_of_the_phase < ans) {
			ans = cut_of_the_phase;
			rep(j, 0, n) if (get(j) == get(t)) {
				// A
			} else {
				// B
			}
		}
		merge_nodes(s, t);
	}
	return ans;
}

参考资料

  1. Stoer M , F Wagner. A simple min cut algorithm[C]// Springer Berlin Heidelberg. Springer Berlin Heidelberg, 1994.
  2. oiwiki-Stoer-Wagner 算法
  3. SJTU-Stoer-Wagner Algorithm
  4. https://www.luogu.com.cn/problem/P5632
  5. POJ2914-Minimum Cut
CATALOG
  1. 1. 背景
  2. 2. 算法
  3. 3. 证明
  4. 4. 代码
  5. 5. 参考资料
Total : 31
2021
2020
2019
2018
AhoCorasick AC自动机 domjudge DR KMP ICPC 贪心 vim git bash polya 斜率优化 SW