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