网络流问题

李晓明

在高速公路网中有车流，在互联网上有信息流，在自来水管网中有水流，在公用电网中有电流，等等。但凡网络，大都和某种流联系在一起;网络的作用，就是要保障那些流的畅通。对网络中流的研究是具有普遍意义的主题。

研究网络中的流问题可有多个不同的视角和目标追求。本文讨论两个节点之间可能经过的最大流量。我们从简单例子开始，建立讨论这个话题的语境。

图1所示为一个3节点{s，a，t}的有向网络，边上的数字表示能支持的流量（不妨看成是单位时间能通过的车辆数），一般也称为对应边的“容量”。这个例子数据表明s—a边的容量为3，a—t边的容量为2。想象为道路，也就相当于是说s—a路段要比a—t路段宽一些。边的箭头方向则表示“单行线”的方向。

现在的问题是，如果我们要不断从s发出开往t的车，单位时间能发多少辆？几乎不用多想，你马上会认识到3是不行的，最多是2。而且如果有人说1，你则会说每条边的容量都还有剩余，因而流量还可以增加。于是我们说，2就是这个网络中从s到t的最大流量。并且，如果面对的不止两个路段，而是多个如此串联的路段，你也能认识到从s到t的最大流量受限于最小容量的路段。那样的路段，也称为“瓶颈”，别的路段再宽也没有用。在本专栏前两期讨论调度问题时，我们有过一个背景不同但精神上有类似之处的概念，就是“关键路径”，它就是完成任务的瓶颈。下面考虑图2所示的一个稍微复杂一点的例子。

先看图2（a），不妨也看成是一个道路网的抽象。……