网络流和棒球赛淘汰问题

1996 年 9 月 10 日，《旧金山纪事报》的体育版上登载了《巨人队正式告别 NL 西区比赛》一文，宣布了旧金山巨人队输掉比赛的消息。当时，圣地亚哥教士队凭借 80 场胜利暂列西区比赛第一，旧金山巨人队只赢得了 59 场比赛，要想追上圣地亚哥教士队，至少还得再赢 21 场比赛才行。然而，根据赛程安排，巨人队只剩下 20 场比赛没打了，因而彻底与冠军无缘。

有趣的是，报社可能没有发现，其实在两天以前，也就是 1996 年 9 月 8 日，巨人队就已经没有夺冠的可能了。那一天，圣地亚哥教士队还只有 78 场胜利，与洛杉矶道奇队暂时并列第一。此时的巨人队仍然是 59 场胜利，但还有 22 场比赛没打。因而，表面上看起来，巨人队似乎仍有夺冠的可能。然而，根据赛程安排，圣地亚哥教士队和洛杉矶道奇队互相之间还有 7 场比赛要打，其中必有一方会获得至少 4 场胜利，从而拿到 82 胜的总分；即使巨人队剩下的 22 场比赛全胜，也只能得到 81 胜。由此可见，巨人队再怎么努力，也不能获得冠军了。

在美国职业棒球的例行赛中，每个球队都要打 162 场比赛（对手包括但不限于同一分区里的其他队伍，和同一队伍也往往会有多次交手），所胜场数最多者为该分区的冠军；如果有并列第一的情况，则用加赛决出冠军。在比赛过程中，如果我们发现，某支球队无论如何都已经不可能以第一名或者并列第一名的成绩结束比赛，那么这支球队就提前被淘汰了（虽然它还要继续打下去）。从上面的例子中可以看出，发现并且证明一个球队已经告败，有时并不是一件容易的事。为了说明这一点，我们展示一组虚构的数据（这是在 1996 年 8 月 30 日美国联盟东区比赛结果的基础上略作修改得来的），如下表所示。

其中，纽约扬基队暂时排名第一，总共胜 75 场，负 59 场，剩余 28 场比赛没打，其中和巴尔的摩还有 3 场比赛，和波士顿还有 8 场比赛，和多伦多还有 7 场比赛，和底特律还有 3 场比赛（还有 7 场与不在此分区的其他队伍的比赛）。底特律暂时只有 49 场比赛获胜，剩余 27 场比赛没打。如果剩余的 27 场比赛全都获胜的话，是有希望超过纽约扬基队的；即使只有其中 26 场比赛获胜，也有希望与纽约扬基队战平，并在加赛中取胜。然而，根据表里的信息已经足以判断，其实底特律已经没有希望夺冠了，大家不妨自己来推导一下。

有没有什么通用的方法，能够根据目前各球队的得分情况和剩余的场次安排，有效地判断出一个球队是否有夺冠的可能？ 1966 年， Schwartz 在一篇题为 Possible winners in partially completed tournaments 的论文中指出，其实刚才提出的问题，可以归结为一个简单而巧妙的网络流模型。

让我们先来看一个似乎完全无关的问题。假设图 1 是一个交通网示意图，其中 s 点是出发点（或者说入口）， t 点是终点（或者说出口），其余所有的点都是交叉路口。点与点之间的连线代表道路，所有道路都是单行道，汽车只能沿着箭头方向行驶。由于道路的宽度、限速不同等原因，每条道路都有各自的最大车流量限制，我们已经把它们标在了图上。例如，道路 b → c 的最大车流量为 6 ，这就表示当你站在这条道路上的任意一点时，单位时间内最多可以有 6 辆汽车经过你所在的位置。假设在 s 点处源源不断地有汽车想要到达 t 点，这些汽车已经在 s 点处排起了长队。那么，应该怎样安排每条道路的实际流量，才能让整个交通网络的总流量最大化，从而最大程度地缓解排队压力呢？

其中一种规划如图 2 所示，各道路上标有实际流量和最大流量，此时整个交通网络的流量为 6 。由 s 点出发的汽车平分两路，这两条路的实际流量均为 3 ，分别驶入 a 路口和 b 路口。在 b 路口处还有另外一条驶入的路，流量为 2 。从 s → b 和 a → b 这两条路上来的车合流后驶入 b → c ，因而 b → c 的实际流量就是 5 。这 5 个单位的车流量是 c 路口的驶入汽车的唯一来源，这些车分为两拨，其中 1 个单位的车流量进入 c → a 路，另外 4 个单位的车流量直接流向了终点。 a 路口的情况比较复杂，其中有两条路是驶入的，实际流量分别为 3 和 1 ；有两条路是驶出的，实际流量分别为 2 和 2 。注意，我们实际上并不需要关心从每条路上驶入的车都从哪儿出去了，也不需要关心驶往各个地方的车又都是从哪儿来的，只要总的流入量等于总的流出量，这个路口就不会发生问题。

有些朋友可能已经发现，我们的规划多少有些奇怪：图中存在 a → b → c → a 这么一个“圈”，搞得不好的话，有些车会在里面转圈，永远到不了 t 点。不过，我们只关心整个系统的总流量，并不关心实际上每个个体的命运。换句话说，我们可以假设汽车与汽车之间都是无差异的。事实上，如果把这个圈里的所有道路的实际流量都减 1 ，整个网络的总流量仍然不会发生变化，但得到的却是一个更简洁、更明晰的流量规划。不过，为了让后面的讲解更有趣一些，我们故意选取了一个复杂的规划。

给定一个交通网络图，给出图中每条道路允许的最大流量，再指定一个点作为源点（通常用 s 表示），指定一个点作为汇点（通常用 t 表示）。如果为每条道路设定一个实际流量（通常可以假设流量值为整数），使得每条道路的实际流量都不超过这条道路的最大流量，并且除了s点和t点之外，其他每个点的总流入量都等于总流出量，我们就说这是一个网络流。由于制造流量的只有 s 点，消耗流量的只有 t 点，其他点的出入都是平衡的，因此很容易看出，在任意一个网络流中， s 点的总流出，一定等于 t 点的总流入。我们就把这个数值叫做网络流的总流量。我们通常关心的是，如何为各条道路设定实际流量，使得整个图的总流量最大。

图 2 的流量显然还没有达到最大，因为我们还可以找出一条从 s 到 t 的路径，使得途中经过的每条道路的流量都还没满。例如， s → a → b → c → t 就是这样的一条路径。把这条路径上的每条道路的实际流量都加 1 ，显然能够得到一个仍然合法，但总流量比原来大 1 的网络流。新的网络流如图 3 所示。

我们还能进一步增加流量吗？还能，但是这一次就不容易看出来了。考虑路径 s → b → a → c → t ，注意这条路径中只有 s → b 段和 c → t 段是沿着道路方向走的，而 b → a 段和 a → c 段与图中所示的箭头方向正好相反。现在，我们把路径中所有与图中箭头方向相同的路段的实际流量都加 1 ，把路径中所有与图中箭头方向相反的路段的实际流量都减 1 。于是，整个网络变成了图 4 的样子。此时你会发现，这番调整之后， s 点的流出量增加了 1 个单位， t 点的流入量增加了 1 个单位，其他所有点的出入依旧平衡。因此，新的图仍然是一个合法的网络流，并且流量增加了 1 个单位。

现在，我们有了两种增加网络流流量的通用模式，考虑到前者实际上是后者的一个特例，因而它们可以被归结为一种模式。首先，从 s 点出发，寻找一条到 t 点的路径，途中要么顺着某条流量还没满的（还能再加流量的）道路走一步，要么逆着某条流量不为零的（能够减少流量的）道路走一步。我们把这样的路径叫做“增广路径”。找到一条增广路径之后，增加或者减少沿途道路的流量，从而在保证网络流仍然合法的前提下，增加网络流的总流量。

1956 年，美国数学家 Lester Ford, Jr. 和 Delbert Fulkerson 共同发表了一篇题为 Maximal flow through a network 的论文，论文中指出，为了找出一个网络中的最大流量，我们只需要用到上面这种流量改进模式。换句话说，如果不能用上述模式增加某个网络流的流量，即如果图中不存在增广路径，那么此时的流量就一定达到最大值了。

例如，在图 4 中，网络流的流量已经达到了 8 个单位，但我们再也找不到增广路径了。这就说明，图 4 中的流量已经不能再改进，流量最大就是 8 了。

这个结论有一个非常漂亮的证明。假设现在有这么一个网络流，它里面不存在任何增广路径，这就意味着，从 s 点出发，沿着尚未满流的道路走，或者逆着尚有流量的道路走，是无法走到 t 点的。我们把从 s 点出发按此规则能够走到的所有点组成的集合记作 U 。根据集合 U 的定义，任何一条从 U 内走到 U 外的道路一定都已经满流了，任何一条从 U 外走进 U 内的道路流量一定都为零，否则的话集合 U 都还能进一步扩大。例如，在图 4 中，集合 U 就是 {s, a, b} 。驶出 U 的道路有两条，分别是 a → t 和 b → c ，它们都已经满流了；驶入 U 的道路只有 c → a ，它的流量一定为零。我们不妨把所有驶出 U 的道路都涂成红色，把所有驶入 U 的道路都涂成蓝色。

现在，保持集合 U 的范围和道路的颜色不变，修改图中各道路的实际流量，使之成为任意一个合法的网络流。你会发现，下面这个重要的结论始终成立：红色道路里的总流量，减去蓝色道路里的总流量，总是等于整个网络流的流量。比如，把图 4 中的网络流改成图 2 或者图 3 的样子，那么道路 a → t 的流量加上道路 b → c 的流量，再减去道路 c → a 的流量，一定都等于整个网络流的总流量。为什么？其实道理很简单，别忘了，制造流量的只有 s 点，消耗流量的只有 t 点，其他点只负责转移流量，因而不管网络流长什么样，如果从 U 里边流出去的流量比从外边流入 U 的流量更多，多出来的部分就一定是 s 制造的那些流量。

对于任意一个网络流，这些红色道路的总流量减去这些蓝色道路的总流量，就可以得出整个网络流的总流量，这实际上给出了网络流的流量大小的一个上限——如果在某个网络流中，所有的红色道路都满流，并且所有蓝色道路都无流量，那么流量值便达到上限，再也上不去了。然而，这个上限刚才已经实现了，因而它对应的流量就是最大的了。至此，我们便证明了 Ford 和 Fulkerson 的结论。

根据这一结论，我们可以从零出发，反复寻找增广路径，一点一点增加流量，直到流量不能再增加为止。这种寻找最大流的方法就叫做 Ford–Fulkerson 算法。

在运筹学中，网络流问题有着大量直接的应用。然而，网络流问题还有一个更重要的意义——它可以作为一种强大的语言，用于描述很多其他的实际问题。很多乍看上去与图论八竿子打不着的问题，都可以巧妙地转化为网络流问题，用已有的最大流算法来解决。让我们来看一看， Schwartz 是如何用网络流来解决棒球赛淘汰问题的。

一支队伍必然落败，意即这支队伍在最好的局面下也拿不到第一。让我们来分析一下底特律可能的最好局面。显然，对于底特律来说，最好的局面就是，剩余 27 场比赛全都赢了，并且其他四个队在对外队的比赛中全都输了。这样，底特律将会得到 76 胜的成绩，从而排名第一。但是，麻烦就麻烦在，剩下的四个队内部之间还会有多次比赛，其中必然会有一些队伍获胜。为了让底特律仍然排在第一，我们需要保证剩下的四个队内部之间比完之后都不要超过 76 胜的成绩。换句话说，在纽约、巴尔的摩、波士顿、多伦多之间的 3 + 8 + 7 + 2 + 7 + 0 = 27 场比赛中，纽约最多还能胜 1 次，巴尔的摩最多还能胜 4 次，波士顿最多还能胜 7 次，多伦多最多还能胜 16 次。只要这 27 场比赛所产生的 27 个胜局能够按照上述要求分给这四个队，底特律就有夺冠的希望。

网络流是描述这种“分配关系”的绝佳模型。为了简便起见，我们把这四个队分别记作 a 、 b 、 c 、 d 。我们为每支队伍都设置一个结点，并且为这四个结点各作一条指向汇点 t 的道路。 a 和 b 之间有 3 场比赛，于是我们设置一个名为 a-b 的结点，然后从源点 s 引出一条道路指向这个结点，并将其最大流量设定为 3 ；再从这个结点出发，引出两条道路，分别指向 a 和 b ，其最大流量可以均设为 3 ，或者任意比 3 大的值（一般设为无穷大，以表示无需限制）。因而，在一个网络流中，结点 a-b 将会从源点 s 处获得最多 3 个单位的流量，并将所得的流量再分给结点 a 和结点 b 。如果把每个单位的流量理解成一个一个的胜局，那么网络流也就可以理解为这些胜局的来源和去向。类似地，我们设置一个名为 a-c 的结点，从 s 到 a-c 有一条道路，最大流量为 8 ，从 a-c 再引出两条道路，分别指向右边的 a 和 c 。除了 c 和 d 之间没有比赛以外，其他任意两队之间都有比赛，因此在最终的网络当中，有 a-b 、 a-c 、 a-d 、 b-c 、 b-d 共 5 个代表比赛的结点。每一个合法的网络流，也就代表了这些比赛所产生的胜局的一种归派方案。我们希望找出一种胜局归派方案，使得 a 、 b 、 c 、 d 获得的胜局数量分别都不超过 1 、 4 、 7 、 16 。因而，我们给 a → t 、 b → t 、 c → t 、 d → t 四条道路的最大流量依次设为 1 、 4 、 7 、 16 。最后，我们利用 Ford–Fulkerson 算法寻找整个网络的最大流，若流量能够达到 27 ，这就说明我们能够仔细地安排四支队伍之间全部比赛的结果，使得它们各自获得的胜局数都在限制范围之内，从而把第一名的位置留给底特律；如果最大流的流量无法达到 27 ，这就说明四个队之间的比赛场数太多，无法满足各队获胜局数的限制，那么底特律也就不可能取胜了。

事实上，在图 5 所示的网络中，可能的最大流量是 26 （其中一种网络流方案如图 6 所示），没有达到 27 ，因而底特律也就必败无疑了。类似地，我们也可以为其他队伍建立对应的网络，依次计算每个队伍的命运，从而完美解决了棒球赛淘汰问题。

网络流还有很多妙用。感兴趣的读者不妨了解一下二分图最大匹配问题和任务分配问题，继续欣赏网络流模型之美。最大流最小割定理是网络流理论中的一个极其重要的定理，它与上文中 Ford–Fulkerson 算法的正确性证明息息相关，读者朋友们也可以研究研究。