关于网络流

流网络:是一个有向图(可以有环),有两个特殊的点:一个是源点(出发点),一个是汇点,每条边都有属性,叫做容量(也就是每条边的权),

可以想象成一条河,每个点就是一个汇集处,边的容量就是一段的流量。

对于反向边,可以在中间加一个点,所以我们可以默认成不存在反向边

如果边不存在,那容量就是0;

可行流(f),从源点流出如果满足2个条件就是可行流:1容量限制  2流量守恒(对于每个点,流进多少,就流出多少)

可行流流量值(|f|)=往外流的流量 – 流回来的流量(这里考虑了反向边,但基本上是不需要考虑的)

最大流:即最大的可行流

残留网络:针对流网络的某一条可行流而言,每个可行流都对应唯一的残留网络(Gf)

残留网络的点集就是原网络的点集,边集包括原网络的所有边,和所有反向边,

残留边的容量有两种情况

对于非反向边,也就是图里的边,就是他还没有用掉的容量值,啥意思??不是说每条边都有一个最大流量吗,那残留网络的边值就是最大流量减去原流量

对于反向边,就是这条边能退回去多少流量,那也就是这条边的原流量

那为啥要定义这个反向边呢??对于任意一个点你可以选择走或者是不走,但是你走着走着就发现这条路不是最优解,那你就后悔了于是要返回,返回的流量就是原来流出的流量!!

原网络的可行流(f)和残留网络可行流(f’)有啥关系?

f+f’也是原网络的一个可行流。

证明:那就看是否满足容量限制和流量守恒

分类讨论:如果这两条边的方向是相同的,我们知道残留的最大值就是c(最大容量)-f,也就是说: 0<=f'<=c-f,而原网络的的范围是 0<=f<=c,所以相加的范围就是:0<f+f'<=c,那他们就不会超限制,所以满足容量限制

如果方向不同,那又退回来一些,所以肯定不会超过限制:即:c(u,v)>=f(u,v)+f'(v,u)>=0

第二点就是流量守恒:

               

 

那我们可以看出来,反正两边总和是相同的,那就算是相减(反向)还是相加(正向),等号依旧是成立的

就好比 a=b , c=d  => a+c=b+d , a-c=b-d

那这个可行流的流量怎么算?

| f + f’ | = | f | + | f’ |

得到性质:任何一个残留网络的大于零可行流都可以增加原网络里的可行流

换句话说,如果一个残留网络里没有了大于零的可行流,那原网络的可行流就一定是最大的

 

增广路径:

残留网络里,从源点出发,沿着容量大于零的边,如果能走到终点的话,这条路径就是一条增广路径(一般不考虑环)

那由定义得,增广路径一定是一条可行流,有何用处?

 

割:

将点构成的集合V分成两部分:S和T,要求:S∪T=V,S∩T=∅,而且源点s∈S,汇点 t∈T。

那这个划分的结果就是一个

1、割的容量:所有从S集合指向T集合的边的容量值和(顺序不能换),c(S,T)=

 最小割:割的最小容量

2.割的流量:从S指向T的流量-从T指向S的流量,即:

那就有以下性质:对于任意一个割,割的流量一定小于等于割的容量,即

 

证明:其实就是考虑不能超过最大流呗

 

         

        

        

还有,就是我们刚才不是得出了:可行流流量值(|f|)=往外流的流量 – 流回来的流量,那也就是:

那我们再进阶一下:

这个就很好理解了对吧,感性理解一下吧 

那现在有个大问题:就是|f|与f(S,T)之间的关系:

来证明一下吧!

$\because   S\cup T = V,S\cap T = \phi$

$\therefore  f(S,V)=f(S,S)+f(S,T)=0+f(S,T)$

$\therefore f(S,T)=f(S,V)=f(s,V)+f(S-s,V)$

$\because t\notin S,s\notin S-s$
$\therefore t,s\notin S-s$
$设S’=S-s$
$\therefore S’是一个不包括汇点源点的集合,他一定满足流量守恒$
$\therefore f(S’,V)=\sum_{u\in S’}^{}\sum_{v\in V}^{}f(u,v)- \sum_{u\in S’}^{}\sum_{v\in V}^{}f(v,u)$
$=\sum_{u\in S’}^{}(\sum_{v\in V}^{}f(u,v)-\sum_{v\in V}^{}f(v,u)$
$=\sum_{u\in S’}^{}(0)$
$=0$
$\therefore f(S,T)=f(s,T)$
$由定义得:f(s,V)=|f|$
$\therefore f(S,T)=|f|$

其实要是是在理解不了(比如我),那就感性理解一下吧!

当然,还有另一种非常简单的解法(LaTeX在博客园上太太太丑了,所以还是换回来了那个字体):

 

然后找到有相同的项的并合并,一约就发现有等于0的部分,然后就OK啦!!!但是由于本蒟蒻精力有限,剩下的证明就不再赘述,请谅解(其实是因为打这玩意真真真太麻烦了)

所以我们得出:

 即:最大流<=最小割 

下面开始进入核心部分:

关于最大流最小割定定理:

最大流=最小割

首先我们需要知道的是,对于某一个流网络来说:1可行流f是最大流 <=>  2可行流f的残留网络中不包括增广路 <=> 3存在某一个割,使得可行流的流量=割的容量

如何证明?

首先,如果 f 是最大流,而且残留网络中还有增广路,那么 f 肯定还能加,那 f 就不是最大流了,与前面假设矛盾,所以 1=>2,也就是说如果f是最大流,那f的残留网络一定不包括增广路。

其次,如果有一条可行流,他的流量等于割的容量,假设他不是最大流,那就会存在一条比他大的最大流,那这条最大流的流量一定大于割的容量,由于容量限制,这种情况是肯定不会发生的,所以如果存在一个割,他的容量等于一条可行流的流量,那么这条可行流一定是最大流,所以3=>1,搞定!

最后,将S集合定义为在残留网络中,从s(源点)出发,沿着容量大于0的可行流走,所有能走到的点,T=V – S,这就是一个合法的割,那么,设f(x,y)<c(x,y),那么c(x,y)-f(x,y),也就是残留网络中的容量f'(x,y)就大于零,那也就说y这个点能从x这个点遍历到的,那么y就应该属于S,与原假设矛盾,所以f(x,y)=c(x,y),那么对于任意的反向边一定等于0。此时我们得出,

我们还可以更深一层的发现:

由于可行流一定小于等于割的容量,对于任意的割和流这都是满足的(前提是这个割是可行的),所以我们可以得出:最大流小于等于最小割

又因为最小割<=某一个割的容量c(S,T)=|f|<=最大流,所以最大流大于等于最小割

所以最大流等于最小割

 

算法:给定流网络,维护残留网络

每次迭代,现在残留网络里找增广路(也就是找一条从头到尾的路径),也就是BFS。之后更新残留网络,就是让原来的残留网络Gf变成Gf+f’。咋更新?举个例子吧!

假设我现在有一条正向边和一条反向边,设正向边容量为c1,反向边的流量是c2,假设我现在流进了k个单位的流量,那么正向可以流的流量就更新成c1-k,让反向变成c2+k。

 

就讲到这吧!!!

拜拜!!!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

页面下部广告