网络流与棒球赛淘汰问题

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点之外，其他每个点的总流入量都等于总流出量，我们就说这是一个“网络流”（network flow）。由于制造流量的只有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点的路径，途中要么顺着某条流量还没满的（还能再加流量的）道路走一步，要么逆着某条流量不为零的（能够减少流量的）道路走一步。我们把这样的路径叫作“增广路径”（augmenting path）。找到一条增广路径之后，增加或者减少沿途道路的流量，从而在保证网络流仍然合法的前提下，增加网络流的总流量。

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都还能进一步扩大。例如，在图5中，集合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 algorithm）。

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

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

网络流是描述这种“分配关系”的绝佳模型。为了简便起见，我们把这4个队分别记作a、b、c、d。我们为每支队伍都设置一个节点，并且为这4个节点各作一条指向汇点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。最后，我们利用福特--富尔克森算法寻找整个网络的最大流，若流量能够达到27，这就说明我们能够仔细地安排四支队伍之间全部比赛的结果，使得它们各自获得的胜局数都在限制范围之内，从而把第一名的位置留给底特律；如果最大流的流量无法达到27，这就说明四个队之间的比赛场数太多，无法满足各队获胜局数的限制，那么底特律也就不可能取胜了。

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

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