網路流

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

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

　　設f是定義在集合E上的非負函數。用f_ij表示f在弧e=(υ_i，υ_j)上的函數值，並稱為在弧e上從υ_i到υ_j的流量。若函數f滿足以下兩個條件，則稱函數f為網絡上的流，簡稱網絡流：①在每一條弧上，流量f_ij不超過容量с_ij，即0≤f_ij≤с_ij；②在任何一個中間點υ_j上，從υ_i流出的總流量等於流入υ_i的總流量，即

，式中 是對所有以υ _i為起點的弧求和， 是對所有以υ _i為終點的弧求和。條件②稱為流的平衡條件。

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

。凈出量是指從υ _s流出的總流量減去流入υ _s的總流量的差；凈收量是指從υ _t流入的總流量減去從υ _t流出的總流量的差。以υ( f)表示υ _s的凈出量或υ _t的凈收量，並稱為 f(在網絡上)的流量。如圖1 中的a表示一個網絡，箭頭表示弧的方向，弧上的數表示容量。b、c表示網絡a上的兩個流，弧上的數字表示該弧的流量。b的流量為4，c的流量為5。

　　由網絡中的點組成的序列

若對每一對相繼點υ _i、υ ⁱ⁺¹或者(υ _i，υ ⁱ⁺¹)或者(υ ⁱ⁺¹，υ _i)是網絡中的弧，則稱 p是一條連結υ ₀到υ _k的鏈。設 p是一條連接υ _s到υ _t的鏈，從υ _s出發，沿 p走到υ _t時，則鏈 p中與走向有相同方向的弧稱為前向弧；有相反方向的稱為後向弧。如果對於給定的流 f，它在 p的每條前向弧上的流量都小於容量，在每條後向弧上的流量都大於零，則稱鏈 p是關於流 f的一個增廣鏈。例如，在圖1b中， p＝{υ _s，υ ₂，υ ₁，υ ₄，υ _t}是一個增廣鏈。(υ _s，υ ₂)、(υ ₄，υ _t)是前向弧，其上的流量都小於容量；(υ ₁，υ ₂)，(υ ₄，υ ₁)是後向弧，其上的流量都大於零。如果在此增廣鏈的前向弧上，流量都增加1，後向弧上流量都減少1，就可從b變到c，從而使流量從4增加到5。

　　在網絡上尋求一個使流量 υ(f)達到最大的流f，稱之為網絡最大流問題。它是網絡流理論中的一個主要研究課題，已獲得一些重要結果：①流f是最大流的充分必要條件是，不存在關於f的增廣鏈。從而將尋求最大流問題化為判斷有無增廣鏈問題。易見，圖1中的b不是最大流。福特和富爾克森提出瞭一種標號法，即對網絡上的點給以標號，從υ_s出發沿網絡上的弧向υ_t探尋增廣鏈的方法。②若各弧上的容量都是正整數，則必存在各弧上的流量都是整數的最大流。③設x是含有υ_s而不含υ_t的點集，(X，x)表示起點在x中而終點不在x中的弧的集合，並稱為分離υ_s和υ_t的截集，簡稱截集。網絡中去掉一個截集後，就沒有從υ_s到υ_t的定向鏈。(X，x)中所有弧的容量之和，稱為這個截集的截量，記作с(X，x)。使截量最小的截集稱為最小截集。網絡流理論中有一個基本的對偶定理：最大流的流量等於最小截集的截量。圖1的c是一個流量達到最大的流（流量為5），截集{(υ_s，υ₁)，(υ₂，υ₄)}是一個最小截集（截量為5），這裡x＝{υ_s，υ₂}。

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

取最小值。這裡∑是對所有的弧求和， α _ij可理解為從υ _i沿弧（υ _i，υ _j）運輸單位物資到υ _j的費用， 是總的運輸費用。這類問題的解法，一種是從一個流量為υ ₁(υ ₁＜υ ^*)的最小費用流 f ₁出發尋求關於流 f ₁的增廣鏈 M，使得沿 M可以把 f ₁調整為流量是 的最小費用流，反復進行，直到得出流量為υ ^*的流 f，或者判明網絡中不存在流量為υ ^*的流。另一種解法是，從流量為υ ^*的流出發，在不改變流量的情況下，逐步調整，使總費用減少到不能再減少為止。1961年，富爾克森還提出一個求解更一般的最小費用流問題的方法。80年代，一些學者提出瞭更有效的最小費用流算法。

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

的網絡最大流得到解答，圖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.