愛丁堡

[拼音]：wangluoliu

[英文]：network flows

圖論中一種理論和方法，研究網路上的一類最優化問題。T.E.哈里斯於1955年研究鐵路網的最大通過能力時首先提出，在一個給定的網路上尋求某兩點間的最大運輸量問題。1956年，L.R.福特和D.R.富爾克森給出了演算法，從而建立了網路流理論。

在網路流問題中，網路是由一個有向圖G ＝(V，E)和一個定義在弧集E上的已知非負函式с所組成，其中點集V中有兩個指定的點υs和υt，分別稱為發點和收點，而V中其他的點都稱為中間點；с稱為網路的容量函式。用сij表示函式с在弧e＝(υi，υj)上的函式值，並稱之為弧(υi，υj)的容量。

設ƒ是定義在集合E上的非負函式。用ƒij表示ƒ在弧e=(υi，υj)上的函式值，並稱為在弧e上從υi到υj的流量。若函式ƒ滿足以下兩個條件，則稱函式ƒ為網路上的流，簡稱網路流：

（1）在每一條弧上，流量ƒij不超過容量сij，即0≤ƒij≤сij；

（2）在任何一箇中間點υj上，從υi流出的總流量等於流入υi的總流量，即

，式中

是對所有以υi為起點的弧求和，

是對所有以υi為終點的弧求和。條件②稱為流的平衡條件。

對任意給定的流ƒ，易見，發點的淨出量等於收點的淨收量，即

。淨出量是指從υs流出的總流量減去流入υs的總流量的差；淨收量是指從υt流入的總流量減去從υt流出的總流量的差。以υ(ƒ)表示υs的淨出量或υt的淨收量，並稱為ƒ(在網路上)的流量。如圖1

中的a表示一個網路，箭頭表示弧的方向，弧上的數表示容量。b、c表示網路a上的兩個流，弧上的數字表示該弧的流量。b的流量為4，c的流量為5。

由網路中的點組成的序列

若對每一對相繼點υi、υi+1或者(υi，υi+1)或者(υi+1，υi)是網路中的弧，則稱p是一條連結υ0到υk的鏈。設p是一條連線υs到υt的鏈，從υs出發，沿p走到υt時，則鏈p中與走向有相同方向的弧稱為前向弧；有相反方向的稱為後向弧。如果對於給定的流ƒ，它在p 的每條前向弧上的流量都小於容量，在每條後向弧上的流量都大於零，則稱鏈 p是關於流ƒ的一個增廣鏈。例如，在圖1b中，p＝{υs，υ2，υ1，υ4，υt}是一個增廣鏈。(υs，υ2)、(υ4，υt)是前向弧，其上的流量都小於容量；(υ1，υ2)，(υ4，υ1)是後向弧，其上的流量都大於零。如果在此增廣鏈的前向弧上，流量都增加1，後向弧上流量都減少1，就可從b變到c，從而使流量從4增加到5。

在網路上尋求一個使流量 υ(ƒ)達到最大的流ƒ，稱之為網路最大流問題。它是網路流理論中的一個主要研究課題，已獲得一些重要結果：

（1）流ƒ是最大流的充分必要條件是，不存在關於ƒ的增廣鏈。從而將尋求最大流問題化為判斷有無增廣鏈問題。易見，圖1中的b不是最大流。福特和富爾克森提出了一種標號法，即對網路上的點給以標號，從υs出發沿網路上的弧向υt探尋增廣鏈的方法。

（2）若各弧上的容量都是正整數，則必存在各弧上的流量都是整數的最大流。

（3）設x是含有υs而不含υt的點集，(X，塣)表示起點在x中而終點不在x中的弧的集合，並稱為分離υs和υt的截集，簡稱截集。網路中去掉一個截集後，就沒有從υs到υt的定向鏈。(X，塣)中所有弧的容量之和，稱為這個截集的截量，記作с(X，塣)。使截量最小的截集稱為最小截集。網路流理論中有一個基本的對偶定理:最大流的流量等於最小截集的截量。圖1的c是一個流量達到最大的流（流量為5），截集{(υs，υ1)，(υ2，υ4)}是一個最小截集（截量為5），這裡x＝{υs，υ2}。

最小費用流問題是常見的一類重要的網路流問題。設在網路的每條弧(υi，υj)上，除сij外，還賦予一個數值αij，求出一個流ƒ，使其流量為給定的υ*，而且

取最小值。這裡∑是對所有的弧求和，αij可理解為從υi沿弧（υi，υj）運輸單位物資到υj的費用，

是總的運輸費用。這類問題的解法，一種是從一個流量為υ1(υ1<υ*)的最小費用流ƒ1出發尋求關於流ƒ1的增廣鏈M，使得沿M可以把ƒ1調整為流量是

的最小費用流，反覆進行，直到得出流量為υ*的流ƒ，或者判明網路中不存在流量為υ*的流。另一種解法是，從流量為υ*的流出發，在不改變流量的情況下，逐步調整，使總費用減少到不能再減少為止。1961年，富爾克森還提出一個求解更一般的最小費用流問題的方法。80年代，一些學者提出了更有效的最小費用流演算法。

作為網路最大流問題的推廣，弧上流量有非零下界的網路流、動態流、帶增益的流、多種物資流、網路流的分析和合成等問題，都有了一系列的研究結果。在網路最大流的演算法方面也取得了很大的改進。網路流理論已經成為解決許多組合問題的有力工具。組合數學中的一個著名問題，即不同代表系問題：有n個人自由組成m個不同的社會團體，每個人可以同時自由參加幾個團體，如何選出m個不同的人，使其分別成為m個團體的代表。這個問題就可用網路流方法解決。例如，設有5個人:｛1，2，3，4，5｝，4個團體：A =｛2，4，5｝，

B

的網路最大流得到解答，圖2中，未標明容量的弧上，其容量是+∞。｛5，1，3，4｝就可分別成為4個團體的代表。利用網路流的對偶定理，還可證明，霍爾定理:存在各團體的不同代表的充分必要條件是，任何k個團體的成員合在一起的總人數不少於k(1≤k≤n)。在分析交通運輸、工程進度以及生產任務時，也往往應用網路流中最小截集的概念來找出薄弱環節。

參考書目

L.R.Ford and D.R.Fulkerson，Flows in Networks，Princeton Univ. Press， Princeton.1962.

J.C.Hu，Integer Programming and Network Flows，Addison-Wesley， London，1969.