【正文】 jjs vvjsvvsjs ?? ????)V( : A),(A),(fffvtjjt vvjtvvtjt ??? ????V( f ) 稱為可行流 f 的流量 ,即發(fā)點(diǎn)的凈輸出量。 如所有 fij=0， 零流。 S T 定義 4 網(wǎng)絡(luò) D=(V,A,C） ,若點(diǎn)集 V被剖分為兩個(gè)非空集 合 V1和 V1,使 vs∈ V1， vt ∈ V1，則把弧集 (V1， V1) 稱為是分離 vs和 vt的截集。 fijcij vi vj (i , l(vj)) l(vj)=min[l(vi),cijfij], f ji0 vi vj (i , l(vj)) l(vj)=min[l(vi),fji] 重復(fù)上述步驟，一旦 vt被標(biāo)號(hào)，則得到一條 vs到 vt的增廣鏈。弧旁的數(shù)字是 ( cij , fij)。已知各倉庫的可供量、各市場(chǎng)的需求量及從 i倉庫至 j倉庫的路徑的運(yùn)輸能力如下表（表中 0代表無路可通），試求從倉庫可運(yùn)往市場(chǎng)的最大流量？ 市場(chǎng) j 倉庫 i 1 2 3 4 可供量 A B C 30 0 20 10 0 10 0 10 40 40 50 5 20 20 100 需求量 20 20 60 20 多源、多匯 的最大流問題。 （ 1）給 vs標(biāo)上（ 0， ∞）； v2 v3 v1 vs v4 vt (3， 3) (4， 3) (1， 1) (5， 3) (5， 1) (2， 2) (2， 1) (1， 1) (3,0) （ 0， ∞） ? ? ? ? 415m i nm i n 111 ??????? ,)fc(),v(l)v(l sss在弧（ vs， v2）上， fs2=cs2=3, 不滿足標(biāo)號(hào)條件 。 （二）調(diào)整過程 從 vt 開始，反向追蹤，找出增廣鏈 181。即 )V,C ( VV ( f ) 11?可行流 f *，截集 (V1*， V1*), 若 V( f *)=C( V1*， V1*）， 則 f *必是最大流， (V1*， V1*) 必是 D的最小截集。是聯(lián)結(jié) vs和 vt的一條鏈，定義鏈的方向是從 vs到 vt 。記為 D=（ V， A， C）。 (vi , vj ) ∈ 181。 （一）標(biāo)號(hào)過程 ????????未標(biāo)號(hào)點(diǎn)未檢查已檢查標(biāo)號(hào)點(diǎn)網(wǎng)絡(luò)中的點(diǎn)標(biāo)號(hào)：（前點(diǎn)標(biāo)記，前點(diǎn)到該點(diǎn)的弧流量可調(diào)整量） 開始， vs 標(biāo)上（ 0， ∞）， vs 是標(biāo)號(hào)未檢查的點(diǎn)，其余點(diǎn)都是未標(biāo)號(hào)點(diǎn)，一般地，取一個(gè)標(biāo)號(hào)未檢查的點(diǎn) vi ，對(duì)一切未標(biāo)號(hào)的點(diǎn) vj 。 （ 2）流量調(diào)整 令調(diào)整量 ?是 l(vt)，構(gòu)造新的可行流 f ′， 令 ????????????????uvv fuvvfuvvffjiijjiijjiij39。每人能力不同各勝其中某幾項(xiàng)，假定每人只做一件工作，每件工作只用一人作，怎樣分配才能使盡量多的工作完成，更多的人有工作？ 記 x1,x2,…,x n表示工人 記 y1,y2,…,y m表示工作 邊（ xi, yj ）表示 xi勝任 yj工作 上述問題構(gòu)成一個(gè)二部圖 G=(X,Y,E) 尋找邊集 E中的子集，使得集中的任何兩條邊沒有公共端點(diǎn)，最好