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