精华内容
下载资源
问答
  • 最大流最小割定理

    2019-09-28 21:10:35
    最小割 所有的割中边权和最小的割即为最小割 可以想象一下,Kido为了自给自足给自己建了超多供水管道(kido能进行光合作用),形成了一个网络,然后容量越大的管道防护设施越好,但是总有人想渴死Kido就想炸掉管道...

    先来理解几个概念

    在原先能够流通的网络中移除的边集,使得网络无法流通

    最小割

    所有的割中边权和最小的割即为最小割

    可以想象一下,Kido为了自给自足给自己建了超多供水管道(kido能进行光合作用),形成了一个网络,然后容量越大的管道防护设施越好,但是总有人想渴死Kido就想炸掉管道,但是贫乏的恐怖分子既想渴死kido又想节约成本,那么最节约成本的破坏管道的方案即为最小割

     

     最大流最小割定理

    在任何的网络中,最大流的值等于最小割的容量

    具体的证明分三部分

    1.任意一个流都小于等于任意一个割
    这个很好理解 自来水公司随便给你家通点水,构成一个流
    恐怖分子随便砍几刀 砍出一个割
    由于容量限制,每一根的被砍的水管子流出的水流量都小于管子的容量
    每一根被砍的水管的水本来都要到你家的,现在流到外面 加起来得到的流量还是等于原来的流
    管子的容量加起来就是割,所以流小于等于割
    由于上面的流和割都是任意构造的,所以任意一个流小于任意一个割

    2.构造出一个流等于一个割
    当达到最大流时,根据增广路定理
    残留网络中s到t已经没有通路了,否则还能继续增广
    我们把s能到的的点集设为S,不能到的点集为T
    构造出一个割集C[S,T],S到T的边必然满流 否则就能继续增广
    这些满流边的流量和就是当前的流即最大流
    把这些满流边作为割,就构造出了一个和最大流相等的割

    相当于在残量网络中,源点能到达的结点的各个边的容量和为最大流

    所以如果我们要求一个最小割的边集,我们只要跑一编最大流,然后在残量网络中找正向边残量为0的边,那么这条边肯定在最小割里面,这样就可以得到一组最小割的边集

    3.最大流等于最小割
    设相等的流和割分别为Fm和Cm
    则因为任意一个流小于等于任意一个割

    任意F≤Fm=Cm≤任意C

    定理说明完成,证明如下:

    对于一个网络流图G=(V,E) G=(V,E)G=(V,E),其中有源点s和汇点t,那么下面三个条件是等价的:

    1.流f是图G的最大流
    2.残留网络Gf不存在增广路
    3.对于G的某一个割(S,T),此时f=C(S,T) 
    首先证明1 => 2:

    我们利用反证法,假设流f是图G的最大流,但是残留网络中还存在有增广路p,其流量为fp。则我们有流f′=f+fp>f 。这与f是最大流产生矛盾。

    接着证明2 => 3:

    假设残留网络Gf不存在增广路,所以在残留网络Gf中不存在路径从s到达t。我们定义S集合为:当前残留网络中s能够到达的点。同时定义T=V-S。
    此时(S,T)构成一个割(S,T)。且对于任意的u∈S,v∈T ,有f(u,v)=c(u,v)。若f(u,v)=c(u,v) 。若c(u,v)f(u,v)<c(u,v),则有Gf(u,v)>0,s可以到达v,与v属于T矛盾。
    因此有f(S,T)=Σf(u,v)=Σc(u,v)=C(S,T)。

    最后证明3 => 1:

    由于f的上界为最小割,当f到达割的容量时,显然就已经到达最大值,因此f为最大流。

    这样就说明了为什么找不到增广路时,所求得的一定是最大流。

    转载于:https://www.cnblogs.com/graytido/p/10849560.html

    展开全文
  • 最大流最小割定理 下面介绍网络流理论中一个最为重要的定理 最大流最小割定理(Maximum Flow, Minimum Cut Theorem):网络的最大流等于最小割 具体的证明分三部分 1.任意一个流都小于等于任意一个割 这个很好...

    最大流最小割定理

     

    下面介绍网络流理论中一个最为重要的定理
    最大流最小割定理(Maximum Flow, Minimum Cut Theorem):网络的最大流等于最小割
    具体的证明分三部分

     

    1.任意一个流都小于等于任意一个割

     

    这个很好理解 自来水公司随便给你家通点水 构成一个流
    恐怖分子随便砍几刀 砍出一个割
    由于容量限制 每一根的被砍的水管子流出的水流量都小于管子的容量
    每一根被砍的水管的水本来都要到你家的 现在流到外面 加起来得到的流量还是等于原来的流
    管子的容量加起来就是割 所以流小于等于割
    由于上面的流和割都是任意构造的 所以任意一个流小于任意一个割

     

    2.构造出一个流等于一个割

     

    当达到最大流时 根据增广路定理
    残留网络中s到t已经没有通路了 否则还能继续增广
    我们把s能到的的点集设为S 不能到的点集为T
    构造出一个割集C[S,T] S到T的边必然满流 否则就能继续增广
    这些满流边的流量和就是当前的流即最大流
    把这些满流边作为割 就构造出了一个和最大流相等的割

     

    3.最大流等于最小割

     

    设相等的流和割分别为Fm和Cm
    则因为任意一个流小于等于任意一个割
    任意F≤Fm=Cm≤任意C
    --------------------- 
    作者:_Tham 
    来源:CSDN 
    原文:https://blog.csdn.net/txl199106/article/details/64441994 
    版权声明:本文为博主原创文章,转载请附上博文链接!

    展开全文
  • 目录线性规划及对偶形式最大流最小割定理 线性规划及对偶形式 线性规划即 min⁡cTxs.t.Ax⩾bx⩾0 \begin{aligned} \min\quad &c^Tx \\ s.t. \quad &Ax\geqslant b \\ &x\geqslant 0 \end{aligned} mins....

    线性规划及对偶形式

    线性规划即
    min ⁡ c T x s . t . A x ⩾ b x ⩾ 0 \begin{aligned} \min\quad &c^Tx \\ s.t. \quad &Ax\geqslant b \\ &x\geqslant 0 \end{aligned} mins.t.cTxAxbx0
    对偶形式为
    max ⁡ b T y s . t . A y ⩽ c y ⩾ 0 \begin{aligned} \max \quad &b^Ty \\ s.t. \quad &Ay\leqslant c \\ &y\geqslant 0 \end{aligned} maxs.t.bTyAycy0
    总有 b T y = x T A T y ⩽ c T x b^T y = x^TA^Ty \leqslant c^Tx bTy=xTATycTx

    最大流最小割定理

    该定理是线性规划对偶性的很好应用,Wiki写的很好,直接贴Wiki最大流最小割定理

    展开全文
  • 那么最小割为什么等于最大流? 直观理解:假设最大流为30,找一个割集,把网络流分割成了2部分,那现在最大流就是0了。相当于找的割集得把原来的流阻断,割要最小,就要恰好阻断所有流,如果割<30,说明一定存在...

    网络流中的割是指S-T割,即一个边集合E,使得网络流中所有点被划分成2个集合,一个集合含起点S,一个含终点T。E中边的流量就是割,最小割就是使得E的流量最小。那么最小割为什么等于最大流?

    直观理解:假设最大流为30,找一个割集,把网络流分割成了2部分,那现在最大流就是0了。相当于找的割集得把原来的流阻断,割要最小,就要恰好阻断所有流,如果割<30,说明一定存在一条S->T的路径有流,此时并没有把网络划分成2部分,所以割一定>=30,如果大于30了,说明有一部分割边把最大流30阻断了,然后有多余的边,多余的去了,就是最小割30了。

    要找最小割集,就可以先ISAP跑一遍最大流,然后最小割集一定在满流的边中,先BFS一下,然后遍历满流的边,若2个顶点,一个Vis==true,一个vis==false,这条边就是割边之一。具体参考代码。  (可以想象在求最大流的时候,把一条路径上的所有边流量加m,然后至少一条边会满流,如果只有一条边满流,这条边就是割边之一,否则,说明有至少2边的残差相等,就可以通过跑BFS把多余的边识别出来)

     


    网络流的基本概念
    网络流问题都是建立在类似上图的有向图之上,有向图的边的权值代表容量。其中A代表源点,C代表汇点,一般考察的问题情景就是从A中流出流量,经过这些有向边,最终汇集到C中。像这样的具有源点和汇点,并且每条边的权值均为正数的有向图就被称作是容量网络,图中的这些边被称作是弧,弧的权值被称作弧的容量,它代表着能够通过这条弧的最大流量。而经过弧上的实际流量被称作弧的流量,所有这些弧的流量所组成的集合就是所谓的网络流。

    直观上不难发现符合实际情况的网络流的特点,或者说是限制条件。首先每条弧上的流量不能超过其容量,还有对于除了源点和汇点以外的每个点来说,流入它的流量之和必须与从它流出的流量之和相等,即平衡条件。那么满足这两个条件的网络流就被称作是可行流,可行流的流量定义为从源点所流出的所有流量之和。在所有的可行流中,流量最大的那个被称作是最大流。

    对于一串顶点序列(U,U1,U2,U3,…,V)(U,U1,U2,U3,…,V)(U,U1,U2,U3,…,V),如果满足UUU是源点,VVV是汇点,并且序列中每相邻两个顶点之间均存在一条弧,那么就称这个顶点序列为一条链,注意这里并不要求这条弧的方向一定与有向图中的方向一致,在链中,弧被分为前向弧和后向弧,前向弧指在链中顶点的顺序与容量网络中弧的方向一致的弧,而后向弧则是方向不一致的弧。例如对于上图而言,(A,D,B,C)(A,D,B,C)(A,D,B,C)也是一条链,但是其中&lt;A,D>、&lt;B,C>&lt;A,D&gt;、&lt;B,C&gt;<A,D>、<B,C>是前向弧,&lt;D,B>&lt;D,B&gt;<D,B>是后向弧。

    有了链的定义就可以引出增广路的概念,对于可行流的一条链PPP,如果满足:
    1.PPP中所有的前向弧的流量小于容量
    2.PPP中所有的后向弧的流量均大于零
    那么这条链PPP就被称作增广路。为什么要叫作增广路呢?因为增广路上的所有前向弧都是可以继续添加流量的(增加的流量不能超过每条前向弧的容量与流量之差),而反向弧上的流量都是可以继续减少的(减少的流量不能超过反向弧的流量),这两种措施都会使得这个可行流的流量变得更大。

    割指的是一个弧的集合,将这个集合中的所有弧删除后原图的基图不再连通。割将原图中的所有顶点划分为两个部分,在网络流问题中,一般考虑的都是S-T割:即割将原图的顶点划分为两个部分S和T,源点∈S,汇点∈T。例如对于上图,将顶点划分为S=(A,B)、T=(C,D)S=(A,B)、T=(C,D)S=(A,B)、T=(C,D)的这样一个割就是S-T割。
    对于割而言,也有流量和容量的概念。割的容量用C(S,T)C(S,T)C(S,T)表示,C(S,T)=∑c(u,v)(u∈S、v∈T、&lt;u,v>∈E)C(S,T)=\sum c(u,v) (u∈S、v∈T、&lt;u,v&gt;∈E)C(S,T)=∑c(u,v)(u∈S、v∈T、<u,v>∈E)(E代表容量网络所有弧的集合),简单来说割的容量就是SSS中的所有点到TTT中所有点的前向弧的容量之和。例如对上图而言,割S=(A,B)S=(A,B)S=(A,B)、T=(C,D)T=(C,D)T=(C,D)的容量为1+5+3=91+5+3=91+5+3=9。而对于割S=(A,D)S=(A,D)S=(A,D) T=(B,C)T=(B,C)T=(B,C),它的容量为:4+8=124+8=124+8=12。在所有的割中,容量最小的割被称作最小割。
    而割的流量指的是前向弧的流量之和减去后向弧的流量之和。因此割的流量小于等于割的容量,当且仅当割所划分的两个点集中不存在后向弧时取等。

    最大流最小割定理及证明
    网络流的最大流和最小割具有非常重要的实际意义,而这两者之间有着非常重要的关系:最大流的流量=最小割的容量,这就是最大流最小割定理,下面就来证明这个定理。

    命题1:对于可行流的任意一个割,割的流量=可行流的流量
    证明:
    采用归纳法来证明。设可行流的源点为VSV_SV 
    S
    ​    
     ,汇点为VTV_TV 
    T
    ​    
     ,割(S0,T0)(S_0,T_0)(S 
    0
    ​    
     ,T 
    0
    ​    
     )将容量网络划分为T0={VT}T_0=\{ V_T \}T 
    0
    ​    
     ={V 
    T
    ​    
     },S0S_0S 
    0
    ​    
     为除VTV_TV 
    T
    ​    
     外所有顶点的集合。对于这个割而言,割的流量就代表着流入汇点的所有流量之和,因此割(S0,T0)(S_0,T_0)(S 
    0
    ​    
     ,T 
    0
    ​    
     )的流量就等于可行流的流量。
    而其它的割都可以通过往T0T_0T 
    0
    ​    
     中逐步添加顶点来获取,向T0T_0T 
    0
    ​    
     中添加一个顶点VpV_pV 
    p
    ​    
     就意味着割的流量会减去VpV_pV 
    p
    ​    
     到T0T_0T 
    0
    ​    
     中所有顶点的流量之和,同时加上VpV_pV 
    p
    ​    
     到S0S_0S 
    0
    ​    
     中其余各顶点的流量之和,而由可行流的平衡条件可知,减少的流量和添加的流量是相等的,因此割的流量不发生改变,即所有割的流量=割(S0,T0)(S_0,T_0)(S 
    0
    ​    
     ,T 
    0
    ​    
     )的流量=可行流的流量。

    命题2:可行流的流量一定小于等于任意一个割的容量
    证明:
    由命题1显然可得:可行流的流量=割的流量≤割的容量

    命题3:对于可行流G,设其流量为f,如下三个命题等价:
    1.存在一个割使得割的容量c=f
    2.f是最大流的流量
    3.G中不存在任何增广路

    证明:
    1→21\to21→2:由命题2,任何一个可行流的流量都小于等于割的容量,即流量的上界是割的容量的最小值,而现在又存在一个割的容量ccc与fff相等,假设ccc不是最小割的容量,那么存在c0&lt;cc_0&lt;cc 
    0
    ​    
     <c,而又有c=f&lt;c0c=f&lt;c_0c=f<c 
    0
    ​    
     ,因此推出了矛盾,即ccc一定是最小割的容量,fff达到了流量的上界,即fff是最大流的流量。
    注意在证明这一点后是没法说明最大流最小割定理的,因为1推出2只能说明如果存在一个割的容量等于流量,这个流量就是最大流流量,此时最大流流量=最小割容量,但是并不能说明这样的一个割一定是存在的,要证明这一点必须要证明2能推出1。

    2→32\to32→3:证明逆否命题:若G中存在增广路,则f不是最大流的流量。由前面增广路的定义可知,增广路上的每条前向弧都可以继续增加流量,后向弧可以继续减少流量,这两种措施都会导致最终的流量变大,因此f不是最大流的流量。

    3→13\to13→1:G中不存在任何增广路,意味着由源点到汇点的任何一条链中一定存在饱和前向弧(流量=容量)或者零流后向弧(流量=0)。这说明如果只通过非饱和前向弧和非零流后向弧绝对不可能从源点运动到汇点,那么取割(S,T)(S,T)(S,T),其中SSS为源点能够通过非饱和前向弧和非零流后向弧到达的所有顶点构成的集合,T为剩下的点构成的集合,VS∈S、VT∈TV_S∈S、V_T∈TV 
    S
    ​    
     ∈S、V 
    T
    ​    
     ∈T。SSS中的所有点都不能通过非饱和前向弧和非零流后向弧到达TTT,也就是说SSS与TTT之间的弧一定都是饱和前向弧或者零流后向弧,割的流量=前向弧流量-后向弧流量=前向弧流量-0=前向弧流量=前向弧容量=割的容量。因此一定存在一个割,满足割的流量=割的容量。

    由此就证明了这三个命题等价,同时论证了最大流最小割定理。

    由此就不难想到求解最大流的算法,可以在可行流G中不断地寻找增广路,如果不存在增广路,此时可行流就是最大流;如果存在增广路,就在增广路上作修正。这样不断地迭代下去,知道不存在增广路为止。而影响性能的最重要的一个地方就是如何查找增广路,不同的查找方式会使的算法的复杂度不同,这些算法这将在下一篇中整理总结
    ————————————————
    版权声明:本文为CSDN博主「syddf_shadow」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/yjr3426619/article/details/82715779

    展开全文
  • 网络流基础、最大流最小割定理以及证明

    千次阅读 多人点赞 2018-09-15 17:10:45
    像这样的具有源点和汇点,并且每条边的权值均为正数的有向图就被称作是容量网络,图中的这些边被称作是弧,弧的权值被称作弧的容量,它代表着能够通过这条弧的最大流量。而经过弧上的实际流量被称作弧的流量,所有...
  • 最大流最小割定理 (定理,割集)

    千次阅读 2018-09-25 21:31:27
    #1378 : 网络流二·最大流最小割定理 题目链接:http://hihocoder.com/problemset/problem/1378?sid=1393576 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi:在上一周的Hiho一下中我们初步讲解...
  • 详细讲解了最大流最小割定理的证明及其应用,加深理解
  • 1. 在优化理论中,最大流最小割定理指:在一个网络流中,能够从源点到达汇点的最大流量,等于,如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。 2. 定义:  假设N=(V,E)是一个有向图,...
  • 详细介绍了最大流最小割定理 详细介绍了最大流最小割定理详细介绍了最大流最小割定理
  • hihocoder 网络流二·最大流最小割定理 网络流二·最大流最小割定理 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi:在上一周的Hiho一下中我们初步讲解了网络流的概念以及常规解法
  • 最近在看maxflow相关的资料,本文主要介绍下自己对最大流最小割的理解。最大流本来是网络流方面的算法,后来在计算机视觉中也得到广泛的应用,如图割。我觉得要理解一个算法首先要从起源开始,然后再去泛化问题、...
  • 最大流最小割定理,指网络流的最大流等于其最小割。 最大流指符合三个性质的前提下,从S到T能流过的最大流量。 最小割指符合割的定义,最小的割容量。 求最大流: 不断寻找增广路,计算能增加的最小流量,然后...
  • 最大流-最小割定理

    万次阅读 多人点赞 2016-01-18 21:59:28
    最大流-最小割原理浅析,在进行graph-cut算法的时候遇到的。
  • 一篇写得不错得最大流博客,术语很齐全 论如何卡掉Dinic(我没看懂) 咕咕讨论,Zadeh Construction是个什么东西 二分图匹配Dinic重拳出击 各种算法的时间复杂度以及HLPP的讲解 Dinic之神 最大流的正确性 各种算法的...
  • #1378 : 网络流二·最大流最小割定理 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi:在上一周的Hiho一下中我们初步讲解了网络流的概念以及常规解法,小Ho你还记得内容么...
  • 题目链接: ...   代码: ...也没仔细看思想是哪一个...这题求的是最小割和割完后原点所在的集合点的个数和原点所在集合所有点。 flag就是判断是不是最后一遍搜索,最后一遍bfs就是为了求与s联通的点并标记,计数。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,767
精华内容 1,906
关键字:

最大流最小割定理