求解无向图最小割

 2021/12/26 

背景

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

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

算法

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 算法。

证明

定理记是图的两个点，通过合并得到，则图的最小割是最小割或者图的最小割。

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

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

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

记 MinimumCutPhase 的起点为，的任一割为。
当的前一个加入点与不在的同一部分（e.g. 一个与源点连通，一个与汇点连通）时，记是一个活跃(active)点。
是割的边权和。
表示之前加入的所有点，但不包括。
表示集合和点之间所有连边的权值和。
是点集在割上的导出割(induced cut)。

证明思路：对于的任一割，有，说明的最小割为，则引理得证。

首先，对于所有的活跃点有以下推论：使用数学归纳法证明。

对于第一个活跃点来说，该不等式显然成立。一部分点与起点连通，另一部分仅有一个点。导出割必然大于等于。
记是的下一个跃点，有：

根据 MinimumCutPhase 的定义，，因此，继而有：因为和点不在同一连通块中，割必然包含这部分边，那么就可推导出第 2 个不等式。

根据定义，割分割了，因此总是一个活跃点，符合不等式，引理得证。

代码

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;
}