问题：
将点集V分成S、T两个集合。使E(S,T)的边数量最少，求解最小割的值
本文将采用确定性网络流算法和非确定性随机算法两方面讲解，主要求解高级算法中的随机思想
1.经典的网络流问题
对于一个网络图来说，定义了源点A 和汇点B，那么设定图上所有的边的容量均为1，源点A可流出的流量是无穷的，那么到汇点B的最大流其实就是等于最小割的值。
对于这个问题来说，只要任意确定一个源点A，枚举汇点B，这个时间复杂度是O(n)，然后利用最大流算法求解对于这样的源点A和汇点B求得的解。
最小割的确定性算法
目前已知最好的求最小割的确定性算法是Stoer–Wagner algorithm (O(mn+n2logn),m=|E|)(O(mn+n2logn),m=|E|),包含并行边
2.高级算法—随机思想 (Karger’s Contraction algorithm解决最小割问题及其运行复杂度分析。)
收缩操作
The contraction operator Contract(G, e)
say e = uv:
- replace {u,v} by a new vertex x;
- for every edge (no matter parallel or not) in the form of uw or vw that connects one of {u,v} to a vertex w∈V{u,v} in the graph other than u,v replace it by a new edge xw;
- the reset of the graph does not change.
简单理解就是Contract(G,uv)就是将u,v合并成一个新的点x,其他任何点与u,v相连的边都改为和x相连，所以x可以出现重边，当前图应该看作MultiGraph.
收缩的过程中是为了将两个等价类合并为一个等价类。因为在保证是一个连通图的情况下，那么最终区分成S，T两个等价类集合，S和T中的所有点都是相连的，我们每次将相连的点合并是肯定没有问题的，最终合并成只剩两个点的情况下，那么这两个点就是当前随机结果下划分出来的S，T集合。
但结果不一定保证是最优的，可以证明这种随机方法一次求得正确的解的概率是 $\ge2/((n)(n-1))$ ， 独立重复实验次数t应该要达到$t = n(n-1)ln(n) / 2$，这样结果正确的概率就能达到:
$$
\begin{equation}
\begin{aligned}
& 1-Pr[all \space t \space independant \space runnings \space of \space RandomContract \space fails \space to \space find \space a \space min-cut] \\
& = 1 - Pr[a \space single \space running \space of \space RandomContract \space fails]^t \\
& \ge 1-(1-\frac{2}{n(n-1)})^{n(n-1)ln(n) / 2} \\
& \ge 1 - 1/n
\end{aligned}
\end{equation}
$$
简单的随机思想方法
- 在当前的multi-graph（G）中，随机选择一条边来收缩，得到新的图G
- 如果图G的点的数目大于2，返回上一步的操作
- 最终剩下的两个点就可以理解为S，T两个分割的集合，它们之间的平行边就是原始图的一个Cut
- 多次执行以上三步操作，不断更新更大的Cut值，降低错误概率
(1) 伪代码
RandomContract (Karger 1993)
Input: multi-graph G(V,E);
while | V | > 2 do
choose an edge uv∈E uniformly at random;
G = Contract(G,uv);
return C = E (the parallel edges between the only two vertices in V);
(2) 算法分析的证明
1）一次RandomContract随机算法得到结果的正确概率为$\frac{2}{n(n-1)}$证明
Suppose:$e_1,e_2,\cdots,e_{n-2}$为运行RandomContract过程中要被收缩的n-2条边，每次收缩相当于图上少了一个点，那么n-2次收缩最后图上就剩下了2个点。$G_1 = G$为原始的输入multi-graph，$G_{i+1} = Contract(G_i, e_i)$，i=1,2,…,n-2，C是原图G中的最小割。
最后为了保证答案的正确性，目标其实就很明确，保证每次对收缩到当前的图$G_i$来说，取到的要收缩的边$e_i$不存在于$C$中。这样最后n-2次缩边后留下的就是最小割C。根据概率中的链式规则:
$$
\begin{equation}
\begin{aligned}
Pr[C \space is \space returned] & = Pr[e_1,e_2,\cdots,e_{n-2} \notin C] \\
& = Pr[e_1 \notin C \bigwedge e_2 \notin C \bigwedge \cdots \bigwedge e_{n-2} \notin C] \\
& = \prod_{i=1}^{n-2}{Pr[e_i \notin C]}
\end{aligned}
\end{equation}
$$
对于每个$Pr[e_i \notin C]$来说，当前$G_i$还剩的点的数目是n-i+1，可以保证的是这个概率就是1减去从所有的边中选到了C的边的概率，那么选中$Pr[e_i \notin C] = 1 - \frac{|C|}{|E|} $
$$
\frac{|C|}{|E|} \le \frac{2}{n}
$$
上述式子可证：
$$
deg(v)表示v的节点的度数 \\
\sum_v^{v \in G(V)}{deg(v)} = 2|E| \ge |V||C| = n*|C|\\
\frac{|C|}{|E|} \le \frac{2}{n} \\
Pr[e_i \notin C] = 1 - \frac{|C|}{|E|} \ge 1- \frac{2}{n}
$$
由上述式子就可以证得：
$$
Pr[e_i \notin C] = 1 - \frac{|C|}{|E_i|} \ge 1-\frac{2}{n-i+1} = \frac{n-i-1}{n-i+1} \\
\begin{equation}
\begin{aligned}
Pr[C \space is \space returned] & = \prod_{i=1}^{n-2}{Pr[e_i \notin C]} \\
& = \prod_{i=1}^{n-2}{\frac{n-i-1}{n-i+1}} \\
& = \frac{n-2}{n}∗\frac{n-3}{n-1}∗\frac{n-4}{n-2}∗…∗\frac{1}{3} \\
& = \frac{2}{n∗(n-1)}
\end{aligned}
\end{equation}
$$
2）算法复杂度分析
独立重复实验次数t应该要达到$t = n(n-1)ln(n) / 2$时
$$
\begin{equation}
\begin{aligned}
& 1-Pr[all \space t \space independant \space runnings \space of \space RandomContract \space fails \space to \space find \space a \space min-cut] \\
& = 1 - Pr[a \space single \space running \space of \space RandomContract \space fails]^t \\
& \ge 1-(1-\frac{2}{n(n-1)})^{n(n-1)ln(n) / 2} \\
& \ge 1 - 1/n
\end{aligned}
\end{equation}
$$
每一次RandomContract的时间复杂度是$O(n^2)$，为了提高准确率运行次数达到$t = n(n-1)ln(n) / 2$，总的时间复杂度就是$O(n^4logn)$.
3）扩展思考一个图上最多出现最小割的方法数
任何一个图n个点，具有最小割的数目至多n(n-1)/2个。
证明：
假设最小的数目有M个，表示为$C_1,C_2, … ,C_M$，这些事件之间不存在交集，它们的并集的概率具有可加性。
$$
$$
$$
\begin{equation}
\begin{aligned}
Pr[C_1 \lor C_2 \lor … \lor C_M] & =Pr[C_1]+Pr[C_2]+…+Pr[C_M] \\
& = \frac{2}{n∗(n-1)} ∗ M \le 1 \\
\\
M & \le \frac{n∗(n-1)}{2}
\end{aligned}
\end{equation}
$$
Fast Min-Cut (最小割随机算法的效率优化)
算法
- 预处理算法：RandomContract
RandomContract(G,t)
Input: multi-graph G(V,E), and integer t≥2; while |V|>t do
- choose an edge uv∈E uniformly at random;
- G=Contract(G,uv); return GG;
- FastCut算法
FastCut(G)
Input: multi-graph G(V,E);
if |V|≤6 then return a mincut by brute force;
else let t=⌈1+|V|/ $\sqrt 2$⌉;
- G1 = RandomContract(G,t);
- G2 = RandomContract(G,t);
- return the smaller one of FastCut(G1) and FastCut(G2);
根据上述求解已知
$$
\begin{equation}
\begin{aligned}
Pr[C \space is \space returned] & = \prod_{i=1}^{n-2}{Pr[e_i \notin C]} \\
& = \prod_{i=1}^{n-2}{\frac{n-i-1}{n-i+1}} \\
& = \frac{n-2}{n}∗\frac{n-3}{n-1}∗\frac{n-4}{n-2}∗…∗\frac{1}{3} \\
& = \frac{2}{n∗(n-1)}
\end{aligned}
\end{equation}
$$
很容易看出收缩的边的数量越多，概率下降越快，比如，当剩下3个点满足要求未删除C中边的概率是
$$
\begin{equation}
\begin{aligned}
Pr[e_1 \notin C \land e_2 \notin C \land … \land e_{n-3} \notin C] & = \prod_{i=1}^{n-3}{Pr[e_i \notin C]} \\
& = \prod_{i=1}^{n-3}{\frac{n-i-1}{n-i+1}} \\
& = \frac{n-2}{n}∗\frac{n-3}{n-1}∗\frac{n-4}{n-2}∗…∗\frac{2}{4} \\
& = \frac{2∗3}{n∗(n-1)}
\end{aligned}
\end{equation}
$$
再由此可推出当剩余t个点的multi-graph $G_{n-t}$满足
$$
\begin{equation}
\begin{aligned}
Pr[e_1 \notin C \land e_2 \notin C \land … \land e_{n-t} \notin C] & = \prod_{i=1}^{n-3}{Pr[e_i \notin C]} \\
& = \prod_{i=1}^{n-3}{\frac{n-i-1}{n-i+1}} \\
& = \frac{n-2}{n}∗\frac{n-3}{n-1}∗\frac{n-4}{n-2}∗…∗\frac{t-1}{t+1} \\
& = \frac{t∗(t-1)}{n∗(n-1)}
\end{aligned}
\end{equation}
$$
那么当$t = \left \lceil 1+ n/ \sqrt2 \right \rceil $ , 上述式子中的概率至少是1/2，然后对剩余t个点进行暴力标准求解，保证后t个点的正确性，这样之后的操作不会影响这个概率。
但是t如果太大用暴力不太合适，所以可以规定当t小于等于6时才用暴力，如果大于6，就不断用递归的方法进行计算，这样n值不断在除以$\sqrt 2$下降，每次递归过程中进行点与点之间的处理操作是$O(n^2)$。
时间复杂度计算就是
$$
T(n) = 2T(\left \lceil 1+ n/ \sqrt2 \right \rceil) + O(n^2) \quad n>6 \\
T(n) = O(1) \quad n \le 6
\\
T(n) = O(n^2logn)
$$
代码实现
|
|
|
|
Reference
http://keyun.ml/2016/10/06/Course/advanced-algorithm-3.html
https://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec2final.pdf
