[音乐] [音乐] [音乐] 各位同学大家好，我们本次介绍网络流的基本概念。 首先介绍流网络，流网络是一个四元组。 它首先包括了一个有向图。 有向图，我们需要刻画它的点集和边集。 在点中有两个特殊的点，一个叫做源点，一个叫做汇点。 我们说源点只有出发的边儿，而对汇点只有进入的边。 第四个参数是一个特殊的函数，叫做容量函数，它是对边的一个 赋值。 我们说每个边的容量函数，我们总是定义它一定是一个正数，或者等价地讲 如果某一个边的容量为 0 的话，那么这个边不出现在原始的边集中。 我们说，流网络可以刻画现实中的很多问题 比如说我们用点来表示网络上的一些节点，而用这个 有向边来表示网络的传输路径，那么容量函数就是说 我们沿着这条路径最多允许传送的数据量是多少。 当然还有其他的应用，比如说交通的运输量的一些控制等等。 关于流网络有一个简单而重要的概念叫做割，我们有时候称为 s-t 割。 它是将顶点集 V 划分成两个集合 A 和 B。 并且我们总是约定源点小 s 在第一个集合 A 中，而汇点在 B 中。 回忆一下什么是划分，划分是说这两个集合的交 为空，而这两个集合的并集应该是包含了所有的点集。 在下面这张图中我们用阴影表示了 集合 A，而除了阴影以外的点呢，我们表示集合 B。 我们经常用一个包含了 A、 B 这两个符号的集合来表示这样一个割。 我们可以定义割的容量。 割的容量是定义为从 大 A 出发的到 B 的这样一些边上的容量 相加，我们用这样一个数学符号来表示。 还是刚才这个例子，我们说对这样一个割划分来说，它的 割容量是多少？那应该是 10+13 = 23。 当然我们说我们选择的割不同，它可能割的容量也会不同，比如说 我们定一个新的割，大 A 中包含了 s 点和 v1 点，而余下的点都在 B 中。 那么它的容量是多少？应该是 19。 类似我们定一个新割，包含了s、 v1、 v2 在 A 中，余下的点在 B 中，那么它的容量是 27。 而这个割呢，我们说它的容量是 36。 那什么是最小割问题？我们说刚才看到了 选择割的不同，会导致它的割的容量不同。 那么最小割问题，就是想要寻找怎样的一个割划分，使得割的容量最小。 关于流网络的第二个重要概念是流，流是对边上的一个流的一个赋值。 我们说这个流的赋值函数应该满足如下三个条件： 第一个，我们说每一个边上传送的流量或者是流的函数的 值呢，应该是小于等于这条边上所允许的容量。 换句话说 在下面这张图中，我们说这条边上它的 容量为 6，那么我们沿着这条边最多只能够传送 值小于等于 6 的这样一个流的数据。 第二个要求我们是称为对称性，我们说 u 到 v 的这个流值应该 是等于 v 到 u 这条边的流值的负数，就注意一条边是另外一条边的一个 反向边，那么它们的流值正好是一个正负的相差关系。 然后还有第三个要求，第三个要求是说对任意非源点、 非汇点的边 与这个边相关的流量相加起来应该为 0，换句话说，从这个点 出发的流应该是等于这个进入这个点的流 这个性质被称为流的保持性。 我们还是用这个例子来看，我们说下面这个图呢，当前是表示了一个 流网络，并且边上的这个正数呢，表示了它允许的容量 那么我们用一个分数的形式来表示流以及容量。 我们在斜线的左边，我们以这里的这个为例，我们用 2 来表示当前这个流函数对 v3、 t 这个边的赋值，我们在这个边上推送了一个价值为 2 的一个流 而这个边的容量呢，是 23，显然 2 是小于等于 23 的。 我们也希望验证这个流它满足流函数的其他的要求。 比如说我们验证第三条。 第三条我们说一个非源点、 非汇点的边，以 v4 点为例，我们说进入 v4 的流是 2+11，那么之和是 13 而从 v4 流出的流是多少呢？是它有一个到 t 的流是 13。 所以说，我们说跟 v4 相关的流之和应该 是 2+11 再减去 13，正好为 0。 它是一个 流保持的这样一个性质。 我们 可以验证这个流函数，就是当前的流函数满足了 流的三个要求。 我们定义了流之后，我们定义什么是流的 一个值？流得值被定义为从源点出发的流的和。 我们可以看到，还是在刚才这个例子中，从源点 h 出发的流是多少呢？应该是 3+12 = 15。 那什么是最大流问题？我们说满足流函数的三个要求的 流可能有很多种，而最大流问题就是需希望我们去找 值最大的流，换句话说，就是从源点出发的流最大的那个流函数赋值。 比如说以刚才这个例子，我们说刚才这个流的 值是 15，但 15 不是最好的，它还可以被进一步提升，我们可以找到这张图中的一个流赋值 它的值呢，达到了 19。 我们 刚才已经介绍了割和流，我们现在把割和流放在一起 引申出一个定义，是关于经过某一个割的流 经过割，这里是用 A, B 表示的流。 那么经过 A, B 的流是怎么样表示的呢？它是我们是用 f 还是用调用流函数，但是它的参数现在是一个割划分，是大 A 和大 B 我们说它是所有小 u 在来自大 A，而小 v 来自大 B，我们把流函数在 f (u, v) 上的所有的值全部加起来，我们看它是多少，就定义为经过这个 割的流。 注意我们现在 f (u, v) 这个值可能为正，也可能为负。 在一些特殊的情况下，比如说我们说大 A 中只含有一个点 那么很多时候，我们就把那个集合符号给去掉，就直接写一个小 u 这个点。 类似地，我们说大 B 中间如果只有一个点，那么我们也经常把 这个点外面的集合符号去掉，而直接用 f (A, {v})来表示。 我们看一个例子。 还是这样一个流网络图以及流赋值以及对应的容量。 我们说，用阴影表示集合 A，用余下的点呢，当然就相应地表示集合 B 那么我们说，经过这个割的流是多少？ 我们说，可以看到从大 A 流出的 流，我们是用蓝色表示，而进入大 A 的流呢，我们是用红色表示 所以我们把全部加起来。 根据我们经过割的流的定义，它应该是 6+2 +14 再减去 3 等于 19 这样一个量。 我们说对同样的这样一个图，我们考察这个流的值 是多少？记得流的值是仅仅是关于源点而言的 我们说不难看出它应该是 6+13 = 19 这个正好等于我们刚才所选择这个 现在是用虚线表示这个大 A 的经过这个 A, B 割的流的值，就这两个 流的值与经过这个割的流的值正好是相等的。 我们说呢，这其实是一个一般的结论，因为我们可以证明这样一个性质 给了这样一个流网络：G, s, t, c 以及这个流网络上的一个割 X, Y 以后，那么我们能够 证明这个流的值总是等于经过这个割的流的值。 这个证明呢，我们是要用一个归纳法。 对那个划分的第一部分，也就是大 X 的大小 做归纳，我们知道大 X 中至少含有源点，所以最基本的情况 是大 X 就是等于小 s 这个只包含了小 s 这样一个集合，那么这个时候其实它就是流的那个原始定义 所以我们知道结论成立。 现在我们假设 这个结论，这个等式呢，对割 X, Y 成立，我们 需要用归纳法，所以我们要扩大 X 集合。 为了扩大 X 集合，我们从大 Y 中选择一个点，注意这个点不能是 t 我们用 w 来表示这个点。 这样我们考察一个新的割是 X', Y' X' 呢，是等于 X 中加入这个新的点 w，而 Y' 呢，是从大 Y 中去掉 w 这个点。 所以我们问 f (X', Y') 等于多少？ 根据经过割的流的定义，我们说 f (X', Y') 等于 f (X, Y) 再加上因为现在 w 这个点也在 X' 中，所以它要加上 f (w, Y) 但是又注意到 w 原来是在…… Y 中，而现在不在 Y' 中，所以我们要减掉两个相应的量，分别是 X 到 w 的流 之和，以及 w 到 w 的流。 但是 w 到 w 的流是多少呢？我们说这一部分的值，它一定是为 0 的。 这是由流的三个基本性质中的流的保持性，就是 经过一个非源点、 非汇点的点，它的相关的流之和一定为零。 可以 很容易地证明。 而对 负的 f (X, w) 等于多少呢？我们说根据流的对称性，它应该正好等于 f (w, X) 就是这样一个值。 那么我们看这个等式的倒数第二项和倒数第三项相加 它是什么？我们根据经过割的那个流的一个定义 我们说它正好等于 f (w, V)。 那么我们又根据那个流的定义中的第三条，就是说非 源点、 非汇点的点，那么相关的流之和为 0，我们知道 f (w, V) 是多少，它一定正好是 0。 换句话说，我们知道 f (X', Y') 一定是等于 f (X, Y) 的。 而由归纳假设，我们知道 f (X, Y) 一定是等于流的值。 所以，我们知道 f (X', Y') 这个，也就是说现在这个划分中第一个集合更大一点之后 它经过这个新的割的流，仍然是等于原始流的值。 这就证到了我们的这样一个结论。 从这个性质出发，我们可以看到一些有意思的 一些结论。 我们说流的值被定义为从源点 s 出发的流相加 当然我们说也可以用这样一个符号，用这样一个符号。 换句话说，就是从 s，从源点 s 有多少流流出去，加一加。 那么我们说因为流的值跟割的划分 当然是 s-t 割划分本身没有关系，所以我们可以用一个新的割，新的是割什么呢？ 这个新的割，我们把汇点 t 放在一个集合中，而除了汇点 t 以外的其他的点，放在另外一个集合中。 那么我们说经过这个新的割的这个流，跟我们那个刚才这个割 的流应该是一样的。 换句话说，就是流入汇点 t 的 流的值，一定是等于从 s 流出的 流的值。 好了，我们介绍了 流，我们介绍了最大流，我们也介绍了割容量，也介绍了什么是最小割容量问题 我们要证明的是，最大的流值总是小于等于最小割容量的。 这个证明也比较简单，我们可以看对一个流函数 小 f，考察任何一个 s-t 割，我们还是用 A, B 来表示这样一个割。 根据我们刚才的性质，我们证明了流的值一定是等于 经过 A, B 的割的流。 那么经过 A, B 割的流，我们说根据定义，它可以写成这样一个等式。 但是我们一开始讲了，这个 原始的等式中，这个 f (u, v) 呢，它可能为正值，也可能为负值。 所以如果我们把 那些负的值去掉，我们要求 f (u, v) 一定是大于等于 0 的话 那么我们会得到一个量，不会比原来的量小。 而允许的正的流量 f (u, v) 我们说它的最多是多少呢？ 从流的定义中，我们知道，任何一个流 一定是小于等于这条边上所允许的容量。 所以 f (u, v) 被 c (u, v) 所绑定。 而我们下面这个等式，也就是当前最下面这个式子 它告诉我们的是什么呢？它正好就是经过 A, B 的 割的这样一个容量。 换句话说，我们就得到了任意一个流的值一定是小于等于 任意一个割的容量，那么我们可以简单地推论得到 那么你最大的流，也一定是小于等于最小的割容量。 而在下一次课，我们会看到 这个小于等于关系其实可以被加强，我们能够证明最大的流值，实际上是等于最小的割容量的。 好了，这就是本次课的主要内容，谢谢大家。 [音乐]
