最小割集2的卡格算法（分析与应用）

我们在下面进行了介绍和讨论 卡格算法 第一组。

1)  Initialize contracted graph CG as copy of original graph
2)  While there are more than 2 vertices.
      a) Pick a random edge (u, v) in the contracted graph.
      b) Merge (or contract) u and v into a single vertex (update 
         the contracted graph).
      c) Remove self-loops
3) Return cut represented by two vertices.

如前一篇帖子所述， 卡格算法 并不总是能找到min cut。在这篇文章中，我们讨论了找到最小割的可能性。

卡格算法产生的割为最小割的概率大于或等于1/（n） ^2. )

证据： 设给定图有唯一的最小割，最小割中有C边，边为{e _1. E _2. E _三 , .. E _C }.当且仅当集合{e]中没有任何边时，卡格算法才会产生这个最小割 ₁ E _2. E _3. , .. E _C }在上述算法的主while循环中，在迭代中被删除。

c is number of edges in min-cut
m is total number of edges
n is total number of vertices

S1 = Event that one of the edges in {e1, e2, 
     e3, .. ec} is chosen in 1st iteration.
S2 = Event that one of the edges in {e1, e2, 
     e3, .. ec} is chosen in 2nd iteration.
S3 = Event that one of the edges in {e1, e2, 
     e3, .. ec} is chosen in 3rd iteration.

..................
..................

The cut produced by Karger's algorithm would be a min-cut if none of the above
events happen.

So the required probability is P[S1' ∩ S2' ∩ S3' ∩  ............]

在第一次迭代中选择最小切割边的概率：

Let us calculate  P[S1']
P[S1]  = c/m
P[S1'] = (1 - c/m)

Above value is in terms of m (or edges), let us convert 
it in terms of n (or vertices) using below 2 facts.. 

1) Since size of min-cut is c, degree of all vertices must be greater 
than or equal to c. 

2) As per Handshaking Lemma, sum of degrees of all vertices = 2m

From above two facts, we can conclude below.
  n*c <= 2m
    m >= nc/2

  P[S1] <= c / (cn/2)
        <= 2/n

  P[S1] <= c / (cn/2)
        <= 2/n

  P[S1'] >= (1-2/n) ------------(1)

在第二次迭代中选择最小切割边的概率：

P[S1' ∩  S2'] = P[S2' | S1' ] * P[S1']

In the above expression, we know value of P[S1'] >= (1-2/n)

P[S2' | S1'] is conditional probability that is, a min cut is 
not chosen in second iteration given that it is not chosen in first iteration

Since there are total (n-1) edges left now and number of cut edges is still c,
we can replace n by n-1 in inequality (1).  So we get.
  P[S2' | S1' ] >= (1 - 2/(n-1)) 

  P[S1' ∩  S2'] >= (1-2/n) x (1-2/(n-1))

在所有迭代中选择最小切割边的概率：

P[S1' ∩  S2' ∩ S3'  ∩.......... ∩ Sn-2']

>= [1 - 2/n] * [1 - 2/(n-1)] * [1 - 2/(n-2)] * [1 - 2/(n-3)] *...
                              ... * [1 - 2/(n - (n-4)] * [1 - 2/(n - (n-3)]

>= [(n-2)/n] * [(n-3)/(n-1)] * [(n-4)/(n-2)] * .... 2/4 * 2/3

>= 2/(n * (n-1))
>= 1/n2 

如何提高成功的概率？ 上述基本算法的成功概率非常小。例如，对于具有10个节点的图，找到最小割的概率大于或等于1/100。通过重复运行基本算法和返回找到的所有切割的最小值，可以增加概率。

应用： 1) 在战争情况下，一方会有兴趣找到中断敌人通信网络的最小链路数。

2) 最小割问题可以用来研究网络的可靠性（可能失效的边的最小数目）。

3) 网络优化研究（寻找最大流量）。

4) 聚类问题（如关联规则等边）匹配问题（如 北卡罗来纳州 有向图中的最小割算法会导致 北卡罗来纳州 二部图的最大匹配算法（英文）

5) 匹配问题（有向图中最小割集的NC算法将导致二部图中最大匹配的NC算法）

资料来源： https://www.youtube.com/watch?v=-Uivvyhpas http://disi.unal.edu.co/~gjernandezp/psc/touchts/02/MinCut。pdf

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。