首页 > 其他 > 详细

求无向图最小割

时间:2014-07-29 22:09:22      阅读:594      评论:0      收藏:0      [点我收藏+]

    先解释下名词的意思。

无向图的割:就是去掉一些边,使得原图不连通,最小割就是要去掉边的数量最小。

解决这个问题的常用办法就是Stoer-Wagner 算法;

先说下这个算法的步骤后面给出证明:

1.min=MAXINT,固定一个顶点P
2.从点P用类似prim的s算法扩展出“最大生成树”,记录最后扩展的顶点和最后扩展的边
3.计算最后扩展到的顶点的切割值(即与此顶点相连的所有边权和),若比min小更新min
4.合并最后扩展的那条边的两个端点为一个顶点
5.转到2,合并N-1次后结束
6.min即为所求,输出min

       这个算法过程不难理解,我在这里还是简单的演示下算法的过程,

任选一个点P,开始了扩展之路初始化wage数组的值都是0,并且已把点P放入了已扩展点的集合;

第一个点P扩展完的wage数组的值如下图

(图中边上的权值是表示两点间相连的边的条数,也可以认为是两点间的连通度)

     bubuko.com,布布扣x

wage[4]的值最大这时候把点4加入到已访问集合;

        下一次就选取wage数组最大值的点(也就是点4)开始向外扩展,注意在扩展点4的时候点P不会再被更新,

因为它已经进入被扩展集合了。过程同上。

反复扩展。。。

扩展到最后两个点的时候我们记为S,T;

其中T是最后一个点;

这时候我们得到了wage[S] 和 wage[T];

现在有如下性质:

1,wage[T]是将单点T分离出原图的最小的割的值(这里说的是把T这个点单独拿出去);

2,wage[T]的值是将S或T单独分离出原图的最小割值中较小的那一个;

首先性质一很好证明,因为你最后更新到wage[T]的时候 wage[T]的值就是所有与它相连的边的权值的和,显然成立;

性质二的证明分为两种情况,S与T有边相连,和无边相连;

S与T有边相连时,在通过S进行扩展时,由于先选择S所以扩展前wage[S]>=wage[T] 在扩展时 wage[T]的值必然会增加S与T之间的权值。

但是这个权值也是属于S的

两个相加了同一个数,由于之前wage[S]>=wage[T] 所以相加同一个数后不等式仍然成立;

同理S,T无边相连也可以仿照上面的解释;

 

下面要进行合点操作了,我们需要证明一件事情就是合点操作后不会影响最终的答案,

说明这个问题前,我们先进行下面的一个讨论。

算法进行到这就到了合并点的步骤了,我们先来分析下上面prim算法的过程,

首先对于上面的性质1和性质2你要已经理解了下面的说明你才会觉得清晰。

到目前为止好像对于我们有用处的就是最后那两个点S,T。我们不禁要问下,

如果只是为了选出两个点,有必要这么麻烦吗(最大生成树)?

直接随意选两个点,计算出对应的wage的值,

即计算把他们单独分割出去的值,比较大小,小的记为T大的记为S,然后跟新min。

好像也满足了上面所要的结果。显然这么做不对。我们考虑下面一种情况

我们先来想一想分割后的情况,假设我们找到了原图的最小割然后按照最小割集进行分割,

那么原图一定被分为两部分且只能是两部分,记为A,B ;

A,B彼此连同,分割后的A,B 显然是不连通的。

为了简化证明过程我假设 原图A与B 仅有一条边相连。当然这条边的值就是最小割的值。

这条边连接的两个点一个在A中一个在B中 分别记为啊a,b。

如果A中或B中只有一个点,那么你按照随意选点的方法不会影响最后的答案,我们这里要讨论A和B中点的个数大于1。

这时如果你还随意的找两个点进行更新min 合点操作就会出错了。

 这很好想,因为如果你选的是a,b 两个点,

那么你计算出的wage肯定是大于最小割,因为无论a,b都肯定与至少2个点相连,而最终的答案是a,b间边的权值。

这时如果把a,b合点后再进行上面的重复操作显然已经把最佳答案错过了。

所以上面的这选点的prim是为了确定一个顺序问题,我还以这个例子来说,

通过prim选出的两个点S,T一定都在A中或者在B中(前提是A,B中包含2个或以上的点)

也只有在这个前提下进行点的合并才不会影响最后的答案。

我们先来证明下这两个点一定在一边而不会是一边一个(前提是A,B中包含2个或以上的点)

 证明:

 不妨设我们prim 过程的第一个点在A中,那么它一定先在A中的点开始扩展操作,

进行prim扩展若干次后首次计算B中点的wage 时 一定是A,B相连的那个点此时wage[b]的值为最小割的值,接下来,

如果A中可扩展的点的wage值都大于wage[b],那一定是A中的点都扩展玩了才会去扩展B中的点那么最后的两个点一定都在B中。

否者,首次由b点开始扩展时候,我们可以肯定的就是在A中可扩展的点的wage值都小于wage[b],

如果接下来B中的可扩展的点的wage值一直都大于A中可扩展点的wage值

那么就是B中的点全都扩展完然后再进行A中的扩展最后两个点就都在A中。

否则,在B中扩展若干次,再次回到A中扩展的时候,B中可扩展点的wage值都小于A中的可扩展点的值,

由前面可知这个值一定小于wage[b]。接下来就是按照这个思路,如果一直在A中那么最后的点在B中,

如果再次回到B中扩展可知此时A中可扩展的点的wage值都小于B中可扩展点的wage值,反复反复下去,

如果最后A中一个点,B中一个点,会出现什么情况呢?显然最后的那个点的wage值小于wage[b]了。

这样更新完原图的最小割更小了,这显然这显然矛盾了。矛盾的原因就在于prim的过程根本就没法实现一个在A中一个在B中。

有了这么个结论再讨论合点不影响最后答案就很显然了,稍微想一想画一画就懂了这里就不仔细说了

如果S,T相连, 我已经更新了将S,T分割单独分割出去时最小割的值,那么现在即使将S和T合并也不会影响全局最小割的求解。

如果S,T不直接相连时,如果答案是S,T合并后的解显然将两者一起分离的时候已经将T单独分开了。

肯定不会是最优的答案因为画蛇添足啊。所以将S和T合并,并不会影响后面的计算。

到此我就粗略的说完了 无向图最小割的算法的正确性,以及证明,

合点操作之所以不影响答案的关键是prim算法的步骤决定了选点的顺序。代码如下O(n^3)优化的其实效率并没有提高。。

这个要根据题目数据决定。测试题目:厦大OJ 1100。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 105
#define inf 1000000
int node[maxn],cnt[maxn],vis[maxn],p[maxn][maxn];
int main()
{
    int n,m,a,b,ans=inf;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        if(i<n)
        node[i]=i;
        scanf("%d%d",&a,&b);
        p[a][b]++;
        p[b][a]++;
    }
    while(n>1)
    {
        memset(vis,0,sizeof(vis));
        vis[node[0] ] =1;
        int maxi = 1;
        for(int i=0;i<n;i++)
        {
            cnt[node[i] ]=p[ node[i] ][node[0] ];
            if(cnt[node[i] ]>cnt[ node[maxi] ])
            {
                maxi=i;
            }
        }
        int pre = 0;
        for(int s=1;s<n;s++)
        {

            if(s==n-1)
            {
                ans=min(ans,cnt[node[maxi] ]);
                for(int k=0;k<n;k++)
                    p[node[k] ][node[pre] ]  =p[node[pre] ][node [k] ] += p[node[k] ][node[maxi] ];
                node[maxi] = node[--n];
            }
            vis[node[maxi] ] =1;
            pre=maxi;
            maxi=-1;
            for(int i=0;i<n;i++)
            {
                if(!vis[node[i]])
                {
                    cnt[node[i] ] += p[node[i] ][node[pre] ];
                    if(maxi==-1 || cnt[node[i] ]>cnt[node[maxi] ])
                    {
                        maxi = i;
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


 

求无向图最小割,布布扣,bubuko.com

求无向图最小割

原文:http://blog.csdn.net/u012317281/article/details/38115515

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!