[音乐]
[音乐] [音乐]
大家好,我们本次讲解最大流最小割定理
我们在上一次课我们讲了最大流值一定是小于等于最小的 个容量的,而在本次课中,我们想讲,两者实际上是一样的
我们说给了一个流网络图,我们首先 介绍,怎么样去找从源点
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 ,那么 我们又想找到原始图中的一个最大匹配,我们只需要做什么?只需要调动 最大流算法。
最大流算法所输出的那个 最大的流值,就正好是我们这个最大匹配的边数
好了,本次课主要讲了最大流最小割定理,以及 这个最大流算法的一个简单应用,谢谢大家!
[音乐]