【算法导论】第二十六章最大流

一，概念

1）流网络：简单有向图，且有两个特别的顶点（源点s，汇点t）

2）流的边标识为f(u,v)/c(u,v)，流量/容量

3）流的三个性质：1>容量限制 对于所有边 流量<容量

2>反对称性 f(u,v)=-f(v,u)

3>流守恒性 正向流与反响流之和为零

4）割：流网络G=(V,E)的割（S,T）将顶点V划分为S和T=V-S两部分，定义割的容量为C(S)割这条线上S中顶点到T中顶点的容量之和

5）残留网络：残留容量 c f (u, v) = c(u, v) - f (u, v) //边的容量减去边的实际流量

6）增广路径：对于残留网络 G f 中的一条 s-t 路径 p 称其为增广路径

二，最大流和最小割问题

1）最大流：对于一个流网络 G  (V , E ) ,其流量 f 的最大值称为最大流,最大流问题就
是求一个流网络的最大流。

2）最小割：是指流网络中容量最小的割

三、最大流算法的应用

1）最大流模型

例题：现在有 N 只奶牛,F 种食物和 D 种饮料,每只奶牛喜欢其中的一些食物和饮料。现在每种食物和饮料只能分给一只奶牛,每只奶牛也只能吃一种食物和一种饮料,问最多能使多少奶牛既吃到食物又喝到饮料。

解决：由于有 N 只奶牛、F 种食物和 D 种饮料,因此我们可以将这些东西抽象成图中的点。为了方便,我们将食物放在左边,奶牛放在中间,饮料放在右边。由于食物和饮料的使用限制,我们从源点向每种食物连一条边,从每种饮料向汇点连一条边,容量都为 1。而每只奶牛都有喜欢的食物和饮料,因此将每只奶牛喜欢的食物连到这只奶牛,从这只奶牛连到每种它喜欢的饮料。但这样是否就对了呢?实际还是有问题的,因为经过每只奶牛的食物可能超过一种,这就意味着每只奶牛可能会吃超过一组的食物和饮料,而这在题目中是不允许的。怎么解决这个问题呢?我们又回到了流的基本性质:容量限制f (u, v) - c(u, v) 。因此我们将每只奶牛拆成两个点,同一只奶牛的两个点之间连边,容量为 1。这样们就能保证通过每只奶牛的流量为 1 了。每个流对应每种方案,最大流即为最佳方案。