探讨最小分割与K类划分的问题

首先来介绍一下割的概念。
给定一个连通无向图G=（V,E），边的权重为w，定义一个割，割是一组边的集合，当图中去掉这组边之后，图就分为了两个互不连通的连通分支。割中的每一条割边，都分别连接着这两个连通分支。如果我们设定两个端点s，t，分别属于两个连通分支，那么，这个割就称为s-t割。我们可以用最大流算法去求这个s-t割的最小割边权重和。

多向切割（Multiwaycut）

定义

多向切割

给定一组端点S = s1，s2，…，sk⊆V，多向切割是一组边集，将这组边移除会断开端点彼此的连接，也就是变成不连通图。 多向切割要求边权值最小。
与上面所定义的割相比，从原图中去掉多向切割的割边，原图会形成多个连通分支，而上面所定义的割是形成两个连通分支。并且注意，多向切割是最小割。

k-割

移除掉割边之后，形成了k个连通分支，就是k-割。k-割也是最小割。

当k>=3的时候，找多路切割的最小割就是一个np难问题，k=2的时候恰好为s-t割问题，可以用最大流算法解决。np难问题是没有办法在多项式时间内解决的，因此，下面将提出近似比为2-2/k的近似算法。

基于贪心和独立割的近似算法

独立割

独立割：定义$s_i$是一个割，移除掉了这个割之后，$s_i$和剩余的端点就不联通了。
也就是说，U是边的全集，$s_i$是U的子集，$s_i$的并集得到U，对这个$s_i$定义一个独立割，这个割是边的集合，去掉了割中的这些边之后，$s_i$和其他的$s_j$就不连通了。

可以看到，上图中，左边是s2的一个独立割，让包含s2的连通分支和其他的点都不在连通。右边则是s2的一个最小独立割。最小独立割的割边是最少的。

算法

对于每一个$s_i$，i从1到k，都计算一个最小独立割，称为$C_i$。丢弃掉这些割里最重的割，然后把剩余的割组成一个割集，称为$C$
丢弃最重割的原因在于，当把前k-1个$s_i$独立出去之后，最后一个也就自然独立了。可以参考下图，两条边分别把S1和S2独立出去，最后一个S3也自然独立。由于我们要求是最小独立割，因此把全部的$s_i$的独立割计算出来之后，丢掉最重的，剩下的就是根据分别计算独立割可以得到的最小的多路切割。

我们在计算每个$s_i$的最小独立割的时候，可以把非$s_i$的其他部分看作是一个部分，这样，就可以将多路切割的np难问题降为s-t割问题，就可以采用最大流算法来求到每个$s_i$的最小独立割。

令A为G中的最小多路割，我们可以把A看作是K-割的并集如下：把A从G中移除会导致生成k个联通部分，定义一个$A_i$，$A_i$是把剩余的图中包含$s_i$的联通部分分离出来的割。然后就有
A = ${\bigcup }_{i=1}^k{A}_i$.（A是$A_1->A_k中元素的并集$）

下图是一个k=3的割，可以看到，把e1-e5移除掉之后，S1,S2,S3都成为了独立的连通分支

割A1是把S1独立于其他端点的割，A3是把S3独立于其他端点的割，对于e1来说，e1既属于A1,也属于A3,所以说，A的每个割边都会出现在两个不同的$A_i$中，所以计数的时候，就有$A_i$的权重之和为A的权重的二倍。

关于此图，首先A={e1,e2}是最小割，然后A1，A2，A3是S1，S2，S3的独立割，三个红圈分别表示包含S1到S3的连通分量。我们可以看到每个割边出现在了两个集合中，因为它连接着两个连通分量，因此在这两个联通分量的独立割中都会有他。

计数的直接例子：如上图
e1和e2的权重为w1.w2，w（A1）=w1，w(A2)=w2,w(A3)=w1+w2.
A为{e1，e2}，那么${\sum }_{i=1}^{k}w(A_i)$=w1+w2+w1+w2;
w(A)=W1+W2,所以就有下面这个公式。
$$\sum _{i=1}^{k}w(A_i)=2w(A)(4.4.1)$$
显然， $A_i$就是使得$s_i$独立于其他顶点的割，因为$C_i$是$S_i$的最小独立割，所以有w($C_i$) ≤ w($A_i$)。注意这里已经根据k-割的并集$C_i$给了一个因素两种算法[或者译成已经给出来近似比的两种算法]。最后，因为C是由抛弃最重的割所获得的，因此有下面这个公式：
$$\omega (c)=\sum _{i=1}^k\omega (c_i)-max(c_i)\le (1-\frac{1}{k})\sum _{i=1}^k\omega (c_i)\le (1-\frac{1}{k})\sum _{i=1}^{k}w(A_i)=2(1-\frac{1}{k})\omega (A)$$
c就是丢弃k个最小割之中最重的，$(1-\frac{1}{k})$是减掉k个最小割的和的1/k,也就是K个最小割加起来求一个平均值，那么最终的最小割一定会大于这个平均值，所以有c的权值小于等于$c_i$中的权值之和乘$(1-\frac{1}{k})$。上一段的翻译中提到，$A_i$把$s_i$独立出来的割，因为$C_i$