Question

Cut

“割”有两种定义方式：

一、“割”是点集合：图上所有点分成第一群和第二群。

二、“割”是边集合：第一群点连向第二群点的边。

“割”还有另一种等价观点：

一、“割”是点集合：从图上挑出一群点。

二、“割”是边集合：一群点连向其他点的边。

点分成两群，一种分法就是一个 Cut。所有点可以集中在同一群，此时另一群就是空的。

V 个点的有向图，一共有 2^V 种 Cut。V 个点的无向图，第一群和第二群的顺序没有差别，一共有(2^V)/2 种 Cut。

一个 Cut 的权重，是所有边的权重总和。

s-t Cut

限制 s 点位在第一群、限制 t 点位在第二群的 Cut。

s 点、t 点所属的点集合，一般称作 s 侧、t 侧。

Minimum Cut

“最小割”，一张图权重最小的 Cut，可能会有许多个。

求最小割是 NP-hard 问题。当图上没有负边，才有多项式时间的演算法。

Maximum Cut

求最大割是 NP-hard 问题。图上每一条边变号后，求最大割就变成求最小割。当图上没有正边，才有多项式时间的演算法。

一群点收缩为一个点

收缩一群点之后，这群点连接的边就集中在同一点了。

收缩同属一群的点，Cut 的权重依旧相同。

多重的边变成单独的边

当一点到另一点有多重的边，加总这些边的权重，合併成单独的边，Cut 的权重依旧相同。

Submodular Function

一道特别的不等式，说明原集合、交集、联集之间的大小关係。

当图上只有正边、零边的时候，Cut 的权重也符合这个不等式。这裡只证明无向图，至于有向图也是成立的。

Minimum s-t Cut: Max-Flow Min-Cut Theorem

用途

以最大源汇流 Maximum s-t Flow，求出其中一个最小源汇割 Minimum s-t Cut。

限制：有向图，只有正边、零边，不得有负边。

亦得用于无向图，每一条无向边都换成两条有向边。

演算法

根据最大流最小割定理，在一张图上求得一个最大源汇流（流量），则同时形成至少一个最小源汇割（容量）。阴阳相生。

找到最大流之后，部分管线满溢，达到容量上限，形成瓶颈，即是最小源汇割所在之处。

由源点开始遍历，不通过管线满溢的边，能够触及的点集合（瓶颈之前）、无法触及的点集合（瓶颈之后），就是其中一个最小源汇割；而且源点侧的点数是最少的。

由汇点开始反向遍历，亦有类似结果。

一个最大源汇流，能找到不只一个最小源汇割。通常我们只找源点侧点数最少的、汇点侧点数最少的，其他的最小源汇割则不好找。

UVa 10480 ICPC 5099

Minimum s-t Cut

Minimum s-t Cut

介绍几个 Minimum s-t Cut 的基本性质。以下只针对无向图无负边的最小割。

这些性质是了无生趣的数学。如果您无暇深究，可以略过不看；如果您打算设计新演算法，可以参考看看。

性质名称是我随兴取的。欢迎各位读者提供建议。

性质：叛离

一个最小 st 割，从 s 侧或 t 侧分离出一群点（不移动 s 点与 t 点），得到不等式：

从一侧分离出一群点到另一侧（不移动 s 点与 t 点），权重将变大、或者不变（遇到另一个最小 st 割）：

各种 st 割的权重，一定比最小 st 割的权重来得大、或者相等。

性质：基准

一个最小 st 割。x 点在 s 侧，y 点在 t 侧，那麽最小 xy 割的权重小于等于最小 st 割的权重。

最小 xy 割的背后有著最小 st 割撑腰，青出于蓝更胜于蓝。

性质：共侧

图上任取三点 ijk，求出最小 ij 割、最小 jk 割、最小 ki 割。

权重较小的那两个割，事实上权重相等；那两个割可以是同一个割。

以几何角度来看，ijk 是顶角大于等于 60°的等腰三角形。

一、最小 ij 割、最小 jk 割、最小 ki 割，
　　找到权重最小的。
　　不失一般性，暂定是最小 ij 割。
二、要嘛 k 点在 i 侧，要嘛 k 点在 j 侧。
　甲、暂定 k 点在 j 侧。
　　　由基准性质可知：最小 kj 割的权重小于等于最小 ij 割的权重。
　　　又因为最小 ij 割已经是权重最小的，
　　　所以，最小 kj 割的权重被迫等于最小 ij 割的权重。
　　　既然权重相等，那麽是同一个割也无所谓。
　乙、暂定 k 点在 j 侧。
　　　同理，最小 ki 割的权重被迫等于最小 ij 割的权重。

此性质可用 min 函数表示，但是性质会变弱、失真：

最小 st 割的权重，标作 Wst。

图上任意三点 ijk，
Wik ≥ min(Wij, Wjk)

数学归纳法，推广至任意序列：
Waz ≥ min(Wab, Wbc, Wcd, ..., Wyz) 

等号什麽时候成立？似乎没有多大讨论意义。

性质：交集与联集

一个最小 st 割、一个最小 xy 割，各取一侧进行交集或联集。当交集不是空集合，则有可能是：

另一个最小 st 割、另一个最小 xy 割、权重更小或一样的其他割、权重不明的其他割。

根据 stxy 四个点所在位置，可以鑑定结果是哪些种。详细情况请见下列证明过程。

一、cut(S) + cut(X) ≥ cut(S∩X) + cut(S∪X)。
二甲、假设 cut(S∩X) 不含 s 点、不含 t 点。
　　　此时归纳不出任何结论。
二乙、假设 cut(S∩X) 含有 s 点、不含 t 点，是个 st 割。
　　　因为 cut(S∩X) 是 st 割，又知道 cut(S) 是最小 st 割，所以
　　　cut(S∩X) ≥ cut(S)。
　　　然后併入步骤一的式子，轻鬆得到
　　　cut(S∪X) ≤ cut(X)。
三甲、假设 cut(S∪X) 含有 x 点、不含 y 点，是个 xy 割。
　　　以最小 xy 割 cut(X) 为基准，根据叛离性质，
　　　cut(S∪X) 的权重只会变大（或不变），
　　　cut(S∪X) ≥ cut(X)。
　　　然后併入步骤二乙的结论，轻鬆得到
　　　cut(S∪X) = cut(X)。
　　　证得 cut(S∪X) 与 cut(X) 都是最小 xy 割。
三乙、假设 cut(S∪X) 含有 x 点也含有 y 点，不是个 xy 割。
　　　此时无法套用叛离性质。
　　　使用步骤二乙的结论
　　　cut(S∪X) ≤ cut(X)。
　　　证得 cut(S∪X) 是比 cut(X) 权重更小（或一样）的其他割。
四、附带一提，无向图上，一个割的两侧，对调也无妨，
　　cut(S∪X) = cut(T∩Y)。

步骤二，可以改为假设 cut(S∩X) 是 xy 割，
然后在步骤三，对应地改成 st 割，
最后就得到 cut(S∪X) 与 cut(S) 的关係。

步骤一，可以改为其他 submodular function：
cut(S) + cut(X) ≥ cut(S∩X) + cut(S∪X)，证得 cut(S∪X)。
cut(S) + cut(Y) ≥ cut(S∩Y) + cut(S∪Y)，证得 cut(S∪Y)。
cut(T) + cut(X) ≥ cut(T∩X) + cut(T∪X)，证得 cut(T∪X)。
cut(T) + cut(Y) ≥ cut(T∩Y) + cut(T∪Y)，证得 cut(T∪Y)。

步骤二，以 cut(S∩X) 或者以 cut(S∪X) 作为主角都是可以的。
最后证得的分别是(S∪X) 与 cut(S∩X)。

Minimum Cut Tree

已知一个最小 st 割，又有 xy 两点。

甲、xy 两点同在 s 侧（xy 两点同在 t 侧）：

根据联集交集性质，可以发现最小 xy 割不只一个。最小 xy 割的某一侧，可以完全包含 t 侧。无论 xy 是哪两点都成立！

也就是说，就算收缩 t 侧、不理 t 侧，仍然可以找到一个最小 xy 割。用抽象感觉来说，s 侧与 t 侧划清界线、各自为政。

乙、x 点在 s 侧、y 点在 t 侧（x 点在 t 侧、y 点在 s 侧）：

根据基准性质，最小 xy 割的权重，一定小于等于最小 st 割的权重。

由甲乙得知“最小割树”的存在：树上取 st 两点，s 点到 t 点的路径当中，权重最小的边（路径瓶颈），就是最小 st 割的权重；移除权重最小的边，即形成最小 st 割。

一张无向图的最小割树可能有许多棵。至于有向图的最小割树，至今仍未被发现。

最小生成树、最小割树

最小生成树：任意两点之间的路径，最宽的边尽量窄。
最小割树：任意两点之间的所有通道，最宽的切面尽量窄。

UVa 11603 10816 ICPC 4848

All Pairs Minimum s-t Cuts: Divide and Conquer

演算法（Gomory-Hu Algorithm）

求得无向图的一棵最小割树。

http://www.cs.bgu.ac.il/~visproj/eransagi/flow.html

Divide：
随便求一个 Minimum s-t Cut，得到 s 侧、t 侧。
注意到 s 点和 t 点必须是图上原本的点，而不是收缩之后的点。

Conquer：
此图收缩 t 侧（得 t'点），递迴求解，得到 s 侧的 Minimum Cut Tree。
此图收缩 s 侧（得 s'点），递迴求解，得到 t 侧的 Minimum Cut Tree。

Combine：
新增边 s't'，权重设定为 Minimum s-t Cut 的权重。
所有新增的边，最后拼在一起，构成一棵 Minimum Cut Tree。

时间複杂度

为下列三项总和，主要取决于第一项：

一、求 V-1 次最小 st 割的时间。

二、收缩点的时间，平均 O(VlogV)，最差 O(V^2)。

三、新增边的时间，共 V-1 条边，O(V)。

使用 Dynamic Programming 建立表格，就能快速得到所有两点之间的最小 st 割，时间複杂度与空间複杂度都是 O(V^2)。

加速

如果原图已经有一部分是树，此部分显然就是最小割树，不必再逐次计算最小 st 割。

UVa 11603

All Pairs Minimum s-t Cuts: Incremental Method

演算法（Gusfield's Algorithm）

求 V-1 次最小 st 割，得到无向图的一棵最小割树。

时间複杂度为求 V-1 次最小 st 割的时间。

演算法：找出一棵最小割树

一、初始化最小割树：
　　第零点是中心，第一点到第 V-1 点皆连向第零点。
二、依序处理第一点到第 V-1 点：
　甲、当前点 s，只有连向点 t。
　　　边 st 的权重设定为最小 st 割的权重。
　乙、属于 s 侧的点 x，全部改为连往 s 点。
　　　边 xs 保持原本设定的权重。

【待补程式码】

演算法：找出一棵简易版的最小割树（Equivalent Flow Tree）

此树只能求得最小 st 割的权重，但是不能求出最小 st 割。

一、初始化最小割树：
　　第零点是中心，第一点到第 V-1 点皆连向第零点。
二、依序处理第一点到第 V-1 点：
　甲、当前点 s，只有连向点 t。
　　　边 st 的权重设定为最小 st 割的权重。
　乙、属于 s 侧、并且尚未处理的点，全部改为连往 s 点。

Minimum Cut: Stoer-Wagner Algorithm

用途

求出一张无向图的其中一个最小割。

限制：无向图，只有正边、零边，不得有负边。

Maximum Adjacency Search（MAS）

可视作“ Maximum Cardinality Search ”引入权重之后的版本。每回合找到一个点，连往已拜访点的权重总和最多。如果很多点同时符合条件，则任选一点。

Graph Traversal 引入权重，常见的情况就是 Maximum Adjacency Search、Prim's Algorithm、Dijkstra's Algorithm 这三种。

时间複杂度是 O(V^2)。运用 Binary Heap 得压至 O(V+ElogV)。运用 Fibonacci Heap 得压至 O(E+VlogV)。

Minimum Cut: Karger's Algorithm

用途

求出一张无向图的其中一个最小（大）割。

Monte Carlo Algorithm，不保证答案百分之百正确。

演算法

图上随意取一条边，要嘛在最小割上，要嘛不在最小割上。

图上随意取两个点，要嘛在最小割异侧，要嘛在最小割同侧。

怕麻烦的话，直接都当作不在最小割上、都在同侧不就好了。

重複下述步骤 V-1 次，直到图上剩下两个点，得到一个割，推定为最小割：
甲、随机取图上一条边。
乙、推定这条边不在最小割上，
　　也就是推定这条边的两个端点在最小割同侧。
　　收缩这条边的两个端点，不影响最小割权重。

Kruskal's Algorithm 也是每次选择一条边、连结两端点。两者的差异，在于 Karger's Algorithm 是随机选择一条边，而 Kruskal's Algorithm 是选择权重最小的边。

时间複杂度不知如何计算，可能很接近 O(V+E) 吧。

正确率

既然是随机演算法，就得计算一下正确率了！

令一张图的最小割有 c 条边。

补充零边，令图上每一个点连著 c 条边。如此一来，图上每一个割都有 c 条边、每一个割都可能成为最小割，利于分析。

现在图上总共 c*V/2 条边。V 是点数。

随机从图上选择一条边，这条边在最小割上的机率是 c / (c*V/2) = 2/V，不在最小割上的机率是 1 - 2/V。

Karger's Algorithm 每个步骤选择的边，都必须不是最小割的边，最后才能得到正确的最小割。选对的机率是 1 - 2/V。

每个步骤都会减少一个点，推得正确率是[1-2/V] * [1-2/(V-1)] * … * [1-2/4] * [1-2/3] = 1/C{V,2} = Ω(1/V^2) = Ω(V^-2)。

根据这个正确率，只要实施 V^2 次以上的 Karger's Algorithm，结果就相当准确了！

Separation

Vertex Separator

“点分离器”。断开 a 点到 b 点，使之不连通的点集合。ab 不相同、不相邻才有讨论意义。

Minimum Vertex Separator

“最小点分离器”。一张图上点数最少的点分离器。可能有许多个。

Max-Flow Min-Cut Theorem：点容量为一，求最大流、最小割，得到最小点分离器。

Menger's Theorem：两点之间，点不重覆（端点除外）的路径同时最多有几条。其数量等于最小点分离器的大小。

Vertex Connectivity

“点连通度”。欲让图不连通，至少需要拿掉的点数。

换句话说，一张图上随意拿掉“点连通度减一”个点，一定还是连通的。

穷举所有点对，分别求最小点分离器的大小，取最小值即得。

ICPC 4322

Edge Separator

“边分离器”。断开 a 点到 b 点，使之不连通的边集合。ab 不相同才有讨论意义。

Minimum Edge Separator（Minimum s-t Cut）

“最小边分离器”。一张图上边数最少的边分离器。可能有许多个。即是最小源汇割。

Max-Flow Min-Cut Theorem：边容量为一，求最大流、最小割，得到最小边分离器。

Menger's Theorem：两点之间，边不重覆的路径同时最多有几条。其数量等于最小边分离器的大小。

Edge Connectivity

“边连通度”。欲让图不连通，至少需要拿掉的边数。

换句话说，一张图上随意拿掉“边连通度减一”条边，一定还是连通的。

穷举所有点对，分别求最小边分离器的大小，取最小值即得。

ICPC 3811

Closure

Closure

“闭包”。导出子图，没有联外边。可能有许多个。

Minimum Closure / Maximum Closure

“最小闭包”。点数最少的闭包，即是空图，缺乏讨论意义。

“最大闭包”。点数最多的闭包，即是原图，缺乏讨论意义。

无向图的情况下，闭包是连通分量，缺乏讨论意义。

有向图的情况下，收缩强连通分量，得到 DAG，容易找闭包。

Maximum Weight Closure

“最大权闭包”。一张图上，点有权重、边无权重，点的权重总和最大的闭包。只有唯一一个。

无向图演算法：权重最大的连通分量。

有向图演算法：重新打造一张网路流量图，求最小源汇割。我不知道为什麽这样做，真是不好意思。

新增源点、汇点。源点连向所有正点，容量是正点权重；所有负点连向汇点，容量是负点权重变号；原图的边，容量是无限大。

最小源汇割不会包含容量无限大的边。也就是说，源点侧到汇点侧，没有容量无限大的边、没有原图的边。源点侧没有连外边。源点侧是闭包。源点侧去掉源点即是最大权闭包。