[音乐]

[音乐] [音乐]

大家好，我们本次讲解最大流最小割定理

我们在上一次课我们讲了最大流值一定是小于等于最小的个容量的，而在本次课中，我们想讲，两者实际上是一样的

我们说给了一个流网络图，我们首先介绍，怎么样去找从源点

s 到汇点 t 的这样一个路径这是一个例子。

我们说从 s 出发，它到 t 了吗？它首先有一个可以到

v2，从 v2 出发可以到 v4，那么从 v4 出发可以到 t 这样就找到了从 s 到 t 的一条路径。

当然还有其他很多不同的路径，我们说以当前这个例子看来，我们还从

v2 出发，它下一步不到 v4，可以到 v3，那么 v3 又可以到 v4，又到

t 类似的，v3 还可以走另外一个方向，v3 直接走到

t 以及 v2 还可以走到 v1 到 v3

到 v4 到 t 或者是我们是走 v1 到 v3 到

t 这样一条路径，或者是 v1 s 到了 v1 之后，直接到

v3，然后 v3 再到 v4 再到 t，或者是 v3 直接到

t 刚才这个寻找从源点 s 到汇点 t 的这样一个方法呢，我们称为一个深度优先搜索

在介绍了怎么样找到从源点 s 到汇点

t 的一个路径之后，一个自然而然的寻找最大流的一个方法，我们说是这样。

我们首先初始化流函数为全 0 这是初始值。

接着我们寻找从源点 s 到汇点 t

的这样一个路径并且我们假设要找到的这个路径上，所有

边都有流的值是严格的小于这个边上所允许的容量。

那么这个时候我们可以做什么事呢？我们就可以沿着这个路径，去扩展原始流

我们重复上面的步骤，一直找到找不到下一条满足要求的这样一个路径

我们看下面这个例子，我们说给了一个流网络以及它对应的那个流值我们首先初始化所有的边的流都为

0 接着我们找一条从 s 到 t 的一个边，我们现在找的是最下面的这条边在这条路径上，所有的

边上的流值，都是严格的小于边容量的，那么我们说扩多少呢？应该是能够扩最多能扩的那个值。

我们说当前最多能扩 11，所以我们把 11

给扩上去类似的我们再在剩下的

这个流图中间，我们再找一个从 s 到 t 的这样一个边一个路径。

我们找到了如图中红线所示的这样一个路径，我们进一步地扩流，这次我们扩了一个

2 大家可以看到，我们的流函数被重写了

我们仍然重复刚才的步骤，寻找从 s 到 t 的这样一个路径

找到了最上面这样一条路径，我们沿着这条路径去扩流。

注意在这条路径上，仍然是每一条边的流值，都严格的小于经过这个边的所允许的容量值。

那么我们走到这一步似乎就做不下去了我们说，当前的流值是多少呢？它的流值是等于

4+13=17 那这是不是一个正确的算法呢？我们说，很遗憾它不是的

因为关于这个流网络，我们能够定义如图所示的这样一个流函数它的流值为

19，而 19 才是这个流网络允许的最大流值

那么我们希望修改我们这里所说的这个算法为了修改这个算法，我们需要定义一个概念，叫做剩余图

剩余图首先是什么是原始边，原始边就是说我们给了流网络之后原始的边集，我们用小 e

来表示其中的一个边，那么 u 和 v 表示这个有向边的两个顶点

那什么是剩余边呢？剩余边有两种一个就是原图中的这样一个边，就是原图中的边

e 第二种边我们把它 eR，eR 是什么呢？就表示原始边的一个反向边

在这边右图中我们给出了这样一个原始图中的一个边，u 到

v，是原图中的一个边，并且我们指明了在这个边上当前的流量是 6 而这条边的容量呢，是 17。

那什么叫做关于流的剩余容量？我们是这样定义的。

我们说关于这个边小 e 如果小 e 就是原始边集和大 E 中的一条边

那么我们说剩余容量，就是我们允许沿着这个边的方向继续推送的流量数，换句话说，就是这个边的

容量再减去这个边上已经走了的流量这是第一种情况。

而第二种情况比较特殊我们说如果这个，它是

eR，也就是原始边的反向边是在这个这个边集

E 中，那么我们规定这个边的容量呢是多少，是 f（e）

简单地说就是说原始的流图中，你有从 u 到

v 有一个 f（e）的一个一个流，那么我们在后面马上要介绍的这个

剩余图中，我们沿着反向的边，我们应该有一个相应的一个允许减少我们定义剩余图为大

V 和 Ef Ef 就是我们刚刚所讲的这个

剩余容量中，剩余容量为正的那些值所对应的边注意我们这里只允许剩余容量为正，如果剩余容量为

0 的话，那么这条边我们不允许它出现在剩余图中，也就是说形式化的表示，Ef

是两个部分第一个是原始的边 e，如果已经有的

流量是严格地小于这个边的容量的话，那么这条边在剩余图中第二种情况，是我们把

也就是原始边的反向边给放进去，什么时候呢，是如果允许的流量大于 0

我们说，根据刚才这个例子根据刚才这个例子，我们说从 u 到 v

已经有一个 6 的一个容量，那么 u 到 v 还允许继续传送多少呢？应该是

17-6，是 11 这样一个值，这就是 uv 这个边的剩余容量。

那么从 v 到 u 的这个边的剩余容量是多少呢？我们说由于从 u 到 v

已经传送了 6 所以我们允许从 v 到 u 把这个原始的 6

这个流量给消掉，也就是说反向的这个剩余容量应该是 6

那我们再看两个比较特殊的例子第一个例子是说，我们

u 到 v 的这个边目前是饱和的这个边的容量是 17，我们也确实已经传了

17 的这样一个流量那么在剩余图中，这个边会表现成什么样子呢？剩余图中，我们说，从 v 到

u 它是有一个 17 的剩余容量，但是要注意到，在剩余图中

u 到 v 的边是没有的，因为 u 到 v 的剩余容量是 17-17

等于 0 了第二种情况，是说，我们 u 到

v，它的容量是 17，但 u 到 v 我们实际上流的赋值为

0 那么这个时候的剩余图会是什么样子呢？我们说沿着 uv

的方向我们还可以继续传送的流量值，也就是说剩余图的

剩余容量，应该是 17，而反向，从 v 到 u 的

剩余容量，我们说为 0 的，因为你正向的流量为 0，所以我反向没有办法消掉

我们再看一个，一个完整的一个例子。

我们这里给出了一个流网络图以及对应的一个流函数。

那么根据这个流函数，我们画出它的剩余图是什么样子呢？是下面这张图我们可以看到，比如说从 s

到 v1 的这个边 s 到 v1 这个边，我们说它有一个

2 大的一个流值，那么我们说，在剩余图中，我们沿着 s 到 v1 这个边的方向，允许在传送

8 的这样一个流值，而 v1 到 s 这个边呢，我们允许反推 2 的一个流值。

类似的可以检查，比如说 v2 到 v3 这条边，我们说容量为

10，而实际上传的为 0，那么在剩余图中，我们可以继续推的一个剩余容量应该是

10，其他的都可以验证关于剩余图我们有一个重要的性质

在定义这个性质之前，我们先定义两个流的加法我们假设小

f 是 G 的，就原始图 G 的一个流而小 f' 是什么呢，小 f'

是关于流 f 的剩余图 Gf 上的一个流，就这两个流是不一样的，小

f 对于原图的流而小 f' 是对剩余图的这样一个流。

我们定义两个流，函数的加法 f+f'，定义为什么呢？它作用在

uv 这条边上的值，应该是等于 f（u，v）再加上 f'（u，v）

这里有一个性质是说，如果我们已经知道小 f

是 G 上，原图 G 上的流，而 f' 是剩余图上的这样一个流

那么 f+f'，就我们刚刚定义的流函数的加法，也会是原图 G 上的一个流

这是一个很好用的一个性质，我们看一下它的证明我们把 f+f'

简写为小写的 g 那么我们首先验证是它的这样一个容量性质，那么

根据我们的要求，g(u,v) 应该是等于 f(u,v) 再加上 f'(u,v) 的

那么 f'(u,v) 是多少呢？就是我们现在假设 u，v 是原图 G

中的一个边，所以说我们说 f'(u,v) 呢，一定是被

c(u,v) 减去 f(u,v) 所绑定因为我们说，f'

是剩余图中的一个流所以它也应该满足流函数的三个要求，它不会大于它的剩余容量，它一定是小于等于这样一个值

然后这个展开的话，那么我们就得到了 g(u,v) 其实是小于等于

c(u,v) 的这就是流函数的第一个要求。

第二个我们检查一下对称性我们说，g(v,u) 呢，根据流函数加法的定义，它应该等于

f(v,u) 再加上 f'(v,u) 那么因为 f 和 f' 都是流函数，所以

f(v,u) 我们说它是等于 f'

所以我们说，f(v,u) 是等于负的 f(u,v) 的。

类似的，f'(v,u) 呢，应该是等于负的 f'(u,v)。

所以把它全部写起合起来我们就得到了 g(v,u) 应该是等于负的

g(u,v)，这就是对称性当然我们也可以验证第三个性质，也就是流的保持性，除了源点和汇点以外的点

其他的点相关的流之和应该为 0 这里用的主要的工具还是说，因为小

f 是一个流，小 f' 也是一个流，所以它应该满足流的这样一个保持性，它们加起来仍然是为

0 这样就得到了一个重要的性质，就是说，原图

G 中的一个流，再加上它的剩余图中的一个流，仍然是原图

G 中的一个流接着我们要定义一个概念，叫做扩流路径

扩流路径是什么呢？就是说给了一个流网络途径和一个流 f

我们刚才已经讲了怎么去构造一个剩余图 G 下标

f，扩流路径呢就是说，剩余图中，从 s

到 t 的一个简单路径，就是这跟我们一开始讲的找 s 到 t 的路径不一样了，现在是找的剩余图中的一个

简单路径 P

这个路径上的一个流量瓶颈，当然我们在右图中用红色表现出了从 s 到 t 的这样一个扩流路径。

那么这个路径的流量瓶颈是什么呢？

这个流量瓶颈是被称为这个扩流路径各边在这个剩余图中最小的剩余容量值，我们用小写的 b 来表示。

还是同样这个例子，我们可以看到，从 s 到 t 的这一条扩流路径上，最小的那个剩余容量应该是

2 接着我们想要做的一件事情就是沿着路径

P 去扩流怎么样去扩流呢？我们说，如果

这条边是在我们刚才说找到的这条扩流路径上，我们去看，这条边首先它是不是原图 G

中的一条边如果它就是属于原图 G 中的一条边，那么我们就沿着

这个方向去扩展流，由这里的例子为例，我们说，比如说原始的 s

到 v1 是原图中的一条边，那么我们把原始的 2

这个流扩到了 4 类似的，比如说 v2 到 v3

这个是原始图中的一个边，那么我们扩，从 0 扩到了 2，类似的。

但是第二种情况如果我们这个扩流路径中所用到的这条边

它不是原图中的一条边，而是原图边的一个取反在我们这个例子中，我们说从 v1

到 v2 的这个到 v1 到 v2 的这条边，它其实是原图中的边应该是

v2 到 v1 的那么这个时候我们怎么样去更新流呢？我们是定义为原图的流

为 2，我们它推一个反向的流，或者是理解成消掉一个价值为

2 的一个流所以更新它的流值为 0。

而对于其他的边，也就是说不出现在扩流路径中的边，我们说它的流值就是原始流值

这就是一个沿着扩流路径的一个扩流的一个方法

我们看一个完整的例子，就是对刚才的这个图以及图上的流，我们说，它的剩余图应该是如图这样

又第二张图中我们仍然给出了从 s 到 t 的一个扩流路径，并且用高亮表示出了这条扩流路径上的这个瓶颈。

那么有了这个信息之后我们就可以扩流，沿着这条路径，大家可以看到，4 被扩流为了

6，类似的，第二条 v1 到 v3 也是扩大到了 6 而 v3 到 t 也是扩大到了 6。

当然我们对这个新的流呢，我们又可以去构造它的扩流路径

或者是去定义它的这样一个剩余图是第四张图所示。

大家可以看到，在这个图中我们就已经找不到扩流路径

但找不到扩流路径告诉了我们一个什么信息呢？这就是这节课的一个核心定理，称为一个最大流最小割定理

它说对流网络而言，如下三个命题是等价的就是你给了这个流网络以及流网络上的一个流函数小

f 第一个，它说存在一个割 (A,B)，这个割的容量呢，跟这个流的值相等

第二个命题是说，流 f 是原流网络中的一个最大的

第三个，是说不存在相对于流 f 的扩流路径

这里大家可以看到，不存在扩流路径，就意味着，因为

3 和 2 是相等的，所以我们就意味着当前的 f 已经是最大

那么我们当然要证明这样一个定理，首先我们证明 1 蕴含 2

我们说，对任意的一个割 (A,B)

和任意的一个流 g，就是上次课我们证明了这个流 g，它

只要是符合那个流函数的定理的，那么这个流的值一定是小于等于经过

(A,B) 的割的这样一个容量所以你如果现在有了 1 是对的，换句话说，你有了

c(A,B) 等于 f 的话，那么你马上能够得到的是 g

的流值一定是小于等于 f 的流值，换句话说，f 一定是最大的

那么 2 怎么样证明蕴含 3 呢？我们用反证法

假设 3 不成立，也就是说存在相对于当前流 f

的一个扩流路径，那么根据我们刚才讲的那个扩流算法那么我们就可以沿着这个扩流路径

P，去进一步扩大原始的流函数那么这就违反了 2，也就是说你当前的流函数不是一个最大

这也就产生了一个矛盾，换句话说，2 应该是蕴含 3

为了完成整个这证明呢，最后我们需要证明 3 蕴含 1 如果

3 成立，如果 3 成立的话，那么我们现在假设

A 是什么呢，A 是从源点 s 出发，沿着剩余图可以到达的所有的点

我们把 B 取成余下的点，这显然是一个划分

那么既然 3 成立，也就是说不存在从大 A 到大 B

的路径所以说，我们说从原图中，从 B 到 A 的边的流应该为

0，因为如果从 B 到 A 的边的流大于零的话，我们根据剩余图的构造

它的剩余容量，从 A 到 B 的剩余容量将为正，那么就有从 A 到 B 的边

类似的，我们说原图中从大 A 到大 B 的所有的边也必须是饱和的

换一句话说，f(e) 必须等于 c(e)，因为 f(e) 如果小于 c(e)

的话我们说我们沿着这个边还可以再推流，也就是剩余图中所对应的剩余容量仍然为正

也就是说还是有从 A 到 B 的边，那么这就不对了

根据刚才这两个信息我们能够得到 (A,B)

这个割的容量实际上等于经过 (A,B)

的流量值，也就是等于那个原始流的值这里我们就证明了刚才这三个基本性质互相蕴含，也就是说它们是等价的

换句话说，我们怎么样用这个定理呢？就是说，我们如果能够在算法中找到

能够走到一个步骤是找不到扩流路径的，那么我们就能够说我们当前所找到的流值是最大流值这里就是我们的

Ford-Fulkerson 最大流算法

它的方法，输入是原始的流网络，是 (G,s,t,c)

这样一个流网络初始化跟一开始是一样的，我们把所有的边的流值都初始化为

0 接着，我们处理剩余图，对当前流值我们处理剩余图，我们在剩余图中找一条扩流路径

P 我们沿着这条扩流路径去扩流，得到一个新的流值，我们把它称为

f+ 那么我们把 f 更新为，就更新为定义为 f+，那么我们一直重复

①②③，一直找到什么时候结束呢，就找不到新的扩流路径的时候

整个迭代无法进行，算法终止，并且输出当前的流值那么这个算法的正确性我们说是显然的，因为

找不到新的扩流路径就根据我们刚才证明的最大流最小割定理，那么当前的流值一定是最大的

我们还是通过一个例子来看一下这个算法的运行，这是原始的

流网络图，一开始我们初始化所有的流值都是 0。

我们找到一条扩流路径当然我们先是

这次先是找到它的剩余图，那么我们找到这个剩余图上的一条扩流路径我们是用红色表示，这个路径上的瓶颈呢，我们还是高亮色是

3 所以我们沿着这条扩流路径去扩流，把原始的流在这条路径上都扩大了

3 我们得到一个新的流那么新的流我们又可以定义剩余图是如图这样，我们在新的剩余图中又可以找新的扩流路-

径，以及它的瓶颈是 5 ，那么我们沿着这个扩流路径进一步去扩流

大家可以看到我们得到了这样的一个流函数。

那么我们进一步得到剩余图，以及剩余图上的扩流路径

以及瓶颈是 9 ，那么我们仍然沿着这个路径去扩流

如此继续一直到这一步到当前这个流以及对应的剩余图呢，我们可以看到

这个时候我们找不到新的扩流路径了，那么根据最大流最小割定理，我们当前这个流值应该就是最大的流

那么我们看一下在算，就我们的那个证明中的 A 和 B

在这个图中分别是什么呢？ A 我们是说从 s 出发能到的点，我们现在用阴影表示

A 注意，现在 A 是在剩余图中从 s

出发能够到的点那么反映在原图中它到的点仍然是这些点

但是我们说这个点、这个割它的容量是多少？那么显然是

3+5+10=18，它正好等于流值好了，我们刚刚介绍好了那个

Ford-Fulkerson 的那个最大流算法，我们想分析一下这个最大流算法

我们说如果容量函数取值都为整数的话，那么刚才这个算法它一定会终止的。

因为我们说算法每迭代一次，它的那个流函数它允许的流至少扩大

1 ，所以你假设原流网络中最大流为 f* 的话，那么我们这个算法最多迭代

f* 的数量级这么多次就一定会终止

这就给出了我们一个算法的一个运行时间的一个估计，当然我们说还有一些时间是用来

找扩流路径，但这个应该是跟原始图的边集是一个同样的规模当然这不是一件很好的事情，我们可以看一个这样一个例子

就在这个一个非常简单的图中，就图中只含有 4 个点，但是每个边的容量呢可能比较大，现在是用

100 来表示假如说我们找扩流路径找的不好，就第一条扩流路径我们找的是

s-a-b 到 t 的这样一条路径，我们并且沿着它去扩流了

我们得到一个新的一个剩余图。

然后我们进一步去找扩流路径，但是这个时候呢，我们正好又找的是

s-b-a-t 这一条路径还是红线表示出来，我们仍然是沿着

s-b-a-t 去扩流又得到一个新的剩余图。

假如说我们每一次扩流我们找到的那个扩流路径正好每次都用到了

ab 或者 ba 这一条边了，大家可以看我们大家这个迭代大概要经过 100 次。

就是这个图虽然很简单但是我们扩流路径找的不好，就有可能导致我们的算法要很长时间才能终止

这里呢，我们说关于最大流还有一些改进的算法这里不详细介绍，但我们介绍一下相关的结论

我们还是图 G 是 V 和 E ，那么包含了n 个顶点，m

条边那么还有一个，一个第一个我们想说的是如果我们在找

扩流路径的时候，如果使用了最短路径算法来选择下一条扩流路径呢

那我们得到一个算法，它的运行时间就跟我们的最大流值没有关系，它只跟原始图的规模有关是

n 乘以 m² 这样一个数量级当然我们可以对这个算法作进一步的改进，另外一个很有名的算法叫

Dinic 算法它说我们每次不是找一条扩流路径，而是去找一个整个的一个扩流块

那么可以改进得到一个算法的复杂性是 m

乘以 n² 这个细节我都不再讲了。

我们最后讲一点的是最大流算法的一个应用，主要是应用在二分图的一个匹配问题上

那二分图是什么一个二分图呢？二分图我们说是把所有的点分成两部分

这两部分之间没有边，而所有的边，换句话说都是在这两部分之间

那什么是匹配呢？匹配是原始边的一个子集

并且这些边没有，彼此之间是没有共同的点，就是说如图中的红色的边

就是原始边集的一个子集，它任何两条边它是不相交的它就是一个匹配。

那什么是最大匹配呢？就是我们去找使得匹配的集合中边数最大的那个匹配。

比如说我们那个刚才找到的那个匹配，它不是一个最大的匹配，因为我们能够把下面这个匹配给改进，找到一个大小为

4 的这样一个匹配好，我们现在讲一下怎么样用

最大流算法来找二分图的最大匹配，就是给了一个二分图我们点分为左右两部分，然后边都在这左右两部分之间

为了用流算法，首先我们需要把它改成一个流网络图

首先我们定义所有的边，原始的边都是从左边指向右边，从一个集合指向另外一个集合接着我们添加两个特殊的点，称为 s

点和 t 点 s 点出发的边全部指向左边这个集合中的

左边这个集合中的这样一些点而 t

呢是从右边这个集合中的出发的边都指向 t

那么我们规定它的容量函数是什么呢？就是每个边的容量我们都规定为 1

每个边最多使用一次，这就是匹配的要求那么到了这里就很显然了，我们现在规定了每个边的容量都是

1 ，那么我们又想找到原始图中的一个最大匹配，我们只需要做什么？只需要调动最大流算法。

最大流算法所输出的那个最大的流值，就正好是我们这个最大匹配的边数

好了，本次课主要讲了最大流最小割定理，以及这个最大流算法的一个简单应用，谢谢大家！

[音乐]

最大流量=最小割容量

离散数学

Meet the Instructors