---

?

---

目錄

1 最大流問題的數學描述

1.1 網絡中的流 定義? ? ? ? ? ? ? ? ? ?可行流（feasible flow）

1.2 最大流問題? ? ? ? ? ? ?用線性規劃描述最大流問題? ? ? ? ? ? ? ? ?整流定理

1.3 單源和單匯運輸網絡? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?多源多匯網絡?轉化成單源單匯網絡

2 最大流和最小割關系? ? ? ? ? ? ? ? ? ? ? ? ?割的容量

3 最大流的一種算法—標號法? ? ? ? ? ? ??（A）標號過程：? ? ? ? ? ? ?（B）增流過程? ? ? ? ? ? ? ? ??網絡最大流 x 的求解步驟

---

1 最大流問題的數學描述

1.1 網絡中的流 定義

在以V 為節點集， A 為弧集的有向圖G = (V, A) 上定義如下的權函數：

（i） L : A → R 為孤上的權函數，弧 (i, j)∈ A 對應的權 L(i, j) 記為?，稱為孤 (i, j) 的容量下界（lower bound）；

（ii）U : A → R 為弧上的權函數，弧(i, j)∈ A對應的權U(i, j) 記為?，稱為孤 (i, j) 的容量上界或容量（capacity）；

（iii） D :V → R 為頂點上的權函數，節點i ∈V 對應的權 D(i) 記為 ?，稱為頂 點i 的供需量（supply／demand）；

此時所構成的網絡稱為流網絡，可以記為 N = (V, A, L,U,D) 。 由于我們只討論V, A 為有限集合的情況，所以對于弧上的權函數 L,U 和頂點上的 權函數 D ，可以直接用所有孤上對應的權和頂點上的權組成的有限維向量表示，因此 L,U, D 有時直接稱為權向量，或簡稱權。由于給定有向圖G = (V, A) 后，我們總是可 以在它的弧集合和頂點集合上定義各種權函數，所以流網絡一般也直接簡稱為網絡。

在流網絡中，弧(i, j) 的容量下界 和容量上界表示的物理意義分別是：通過該 弧發送某種“物質”時，必須發送的最小數量為 ，而發送的最大數量為 。頂點i ∈V 對應的供需量則表示該頂點從網絡外部獲得的“物質”數量（ > 0時），或從該頂 點發送到網絡外部的“物質”數量（< 0 時）。下面我們給出嚴格定義。

可行流（feasible flow）

可見，當 di > 0時，表示有di 個單位的流量從網絡外部流入該頂點，因此頂點i 稱 為供應點（supply node）或源（source），有時也形象地稱為起始點或發點等；當di < 0 時，表示有|di | 個單位的流量從該頂點流失到網絡外部（或說被該頂點吸收），因此頂 點i 稱為需求點（demand node）或匯（sink），有時也形象地稱為終止點或收點等；當 di = 0時，頂點i 稱為轉運點（transshipment node）或平衡點、中間點等。此外，根據 （1）可知，對于可行網絡，必有

也就是說，所有節點上的供需量之和為 0 是網絡中存在可行流的必要條件

1.2 最大流問題

考慮如下流網絡 N = (V, A,U,D)：節點 s 為網絡中唯一的源點，t 為唯一的匯點， 而其它節點為轉運點。如果網絡中存在可行流 f ，此時稱流 f 的流量（或流值，flow value）為?（根據（3），它自然也等于 ? ?），通常記為v 或v( f ) ，即

對這種單源單匯的網絡，如果我們并不給定 和 ?（即流量不給定），則網絡一 般記為 N = (s,t,V, A,U) 。最大流問題（ maximum flow problem ）就是在 N = (s,t,V, A,U) 中找到流值最大的可行流（即最大流）。我們將會看到，最大流問題 的許多算法也可以用來求解流量給定的網絡中的可行流。也就是說，當我們解決了最大 流問題以后，對于在流量給定的網絡中尋找可行流的問題，通常也就可以解決了。

用線性規劃描述最大流問題

因此，用線性規劃的方法，最大流問題可以形式地描述如下：

【定義】 如果一個矩陣 A 的任何子方陣的行列式的值都等于0，1或 ?1，則稱 A 是 全幺模的(totally unimodular TU，又譯為全單位模的)，或稱 A 是全幺模矩陣。

整流定理

【定理 7】（整流定理） 最大流問題所對應的約束矩陣是全幺模矩陣。若所有弧容量 均為正整數，則問題的最優解為整數解。 最大流問題是一個特殊的線性規劃問題。我們將會看到利用圖的特點，解決這個問 題的方法較之線性規劃的一般方法要方便、直觀得多。

1.3 單源和單匯運輸網絡

多源多匯網絡?轉化成單源單匯網絡

實際問題往往是多源多匯網絡，為了計算的規格化，可將多源多匯網絡G 化成單 源單匯網絡G' 。設 X 是G 的源，Y 是G 的匯，具體轉化方法如下：

（i）在原圖G 中增加兩個新的頂點 x 和 y ，令為新圖G' 中之單源和單匯，則G 中 所有頂點V 成為G' 之中間頂點集。

（ii）用一條容量為∞的弧把 x 連接到 X 中的每個頂點。

（iii）用一條容量為∞的弧把Y 中的每個頂點連接到 y 。 G 和G' 中的流以一個簡單的方式相互對應。若 f 是G 中的流，則由

2 最大流和最小割關系

割的容量

則在這條可增廣軌上每條前向弧的流都可以增加一個量δ ，而相應的后向弧的流可減 少δ ，這樣就可使得網絡的流量獲得增加，同時可以使每條弧的流量不超過它的容量， 而且保持為正，也不影響其它弧的流量。總之，網絡中 f 可增廣軌的存在是有意義的， 因為這意味著 f 不是最大流。

3 最大流的一種算法—標號法

標號法是由 Ford 和 Fulkerson 在 1957 年提出的。用標號法尋求網絡中最大流的基 本思想是尋找可增廣軌，使網絡的流量得到增加，直到最大為止。即首先給出一個初始 流，這樣的流是存在的，例如零流。如果存在關于它的可增廣軌，那么調整該軌上每條 弧上的流量，就可以得到新的流。對于新的流，如果仍存在可增廣軌，則用同樣的方法 使流的值增大，繼續這個過程，直到網絡中不存在關于新得到流的可增廣軌為止，則該 流就是所求的最大流。

這種方法分為以下兩個過程：

A.標號過程：通過標號過程尋找一條可增廣軌。

B.增流過程：沿著可增廣軌增加網絡的流量。

這兩個過程的步驟分述如下。

（A）標號過程：

（B）增流過程

網絡最大流 x 的求解步驟

求網絡 N = (s,t,V, A,U) 中的最大流 x 的算法的程序設計具體步驟如下：

對每個節點 j ，其標號包括兩部分信息 (pred( j),maxf(j))

該節點在可能的增廣路中的前一個節點 pred( j) ，以及沿該可能的增廣路到該節點為止 可以增廣的最大流量 maxf( j)。

并將 j 加入 LIST 中。

例 17 用 Ford-Fulkerson 算法計算如圖 6 網絡中的最大流，每條弧上的兩個數字分 別表示容量和當前流量。

解 編寫程序如下：

clc,clear u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2; u(3,5)=1;u(4,3)=3;u(4,5)=3; f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1; f(3,5)=1;f(4,3)=1;f(4,5)=0; n=length(u);list=[];maxf(n)=1; while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=inf;% list是未檢查鄰接點的標號點，record是已標號點 while (~isempty(list))&(maxf(n)==0)flag=list(1);list(1)=[];label1= find(u(flag,:)-f(flag,:));label1=setdiff(label1,record);list=union(list,label1);pred(label1)=flag;maxf(label1)=min(maxf(flag),u(flag,label1)...-f(flag,label1));record=union(record,label1);label2=find(f(:,flag));label2=label2';label2=setdiff(label2,record);list=union(list,label2);pred(label2)=-flag;maxf(label2)=min(maxf(flag),f(label2,flag));record=union(record,label2);endif maxf(n)>0v2=n; v1=pred(v2);while v2~=1if v1>0f(v1,v2)=f(v1,v2)+maxf(n);elsev1=abs(v1);f(v2,v1)=f(v2,v1)-maxf(n);endv2=v1; v1=pred(v2);endend end f

例18 現需要將城市 s 的石油通過管道運送到城市t ，中間有4個中轉站 ?v1 ,v2 ,v3 和 ?v4 ，城市與中轉站的連接以及管道的容量如圖7所示，求從城市 s 到城市t 的最大流。

解 使用最大流的數學規劃表達式，編寫LINGO程序如下：

model: sets: nodes/s,1,2,3,4,t/; arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f; endsets data: c=8 7 9 5 2 5 9 6 10; enddata n=@size(nodes); !頂點的個數; max=flow; @for(nodes(i)|i #ne#1 #and# i #ne# n:@sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i) @sum(arcs(i,j)|i #eq# 1:f(i,j))=flow; @sum(arcs(i,j)|j #eq# n:f(i,j))=flow; @for(arcs:@bnd(0,f,c)); end

在上面的程序中，采用了稀疏集的編寫方法。下面介紹的程序編寫方法是利用賦權鄰 接矩陣，這樣可以不使用稀疏集的編寫方法，更便于推廣到復雜網絡。

model: sets: nodes/s,1,2,3,4,t/; arcs(nodes,nodes):c,f; endsets data: c=0; @text('fdata.txt')=f; enddata calc: c(1,2)=8;c(1,4)=7; c(2,3)=9;c(2,4)=5; c(3,4)=2;c(3,6)=5; c(4,5)=9;c(5,3)=6;c(5,6)=10; endcalc n=@size(nodes); !頂點的個數; max=flow; @for(nodes(i)|i #ne#1 #and# i #ne# n:@sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i))); @sum(nodes(i):f(1,i))=flow; @sum(nodes(i):f(i,n))=flow; @for(arcs:@bnd(0,f,c)); end

---

?

---

?

?

?

總結

以上是生活随笔為你收集整理的最大流问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。