基本概念①②③④⑤⑥4844122679容量：在某時期內弧(i，j)上的最大通過能力。記為C(i，j)或Cij

在上圖中，C12=4，C13＝8，C23＝4等，怎樣安排運輸方案，才能使在某一時期內從v1運到v6的物資最多，這樣的問題就是最大流問題，網絡中所有流起源于一個叫做發點的節點（源）所有的流終止于一個叫做收點的節點其余所有的節點叫做中間點（轉運點）通過每一條弧的流只允許沿著弧的箭頭方向流動目標是使得從發點到收點的總流量最大4/8/2025流量：弧(i，j)的實際通過量，記為f(i，j)或fij可行流：如果fij滿足：1.對于所有弧(i，j)有0≤fij≤Cij

2.對于發點vs有：3.對于收點vt有：則稱流量集合｛fij｝為網絡的一個可行流，簡記為f,v稱為可行流的流量或值，記為v(f).以下假設網絡是一個簡單連通圖。4.對于中間點點vm有：4/8/2025截集將圖G＝（V，E）的點集分割成兩部分稱為一個截集，截集中所有弧的容量之和稱為截集的截量。①②③④⑤⑥68441226796411322306下圖所示的截集為請看演示4/8/2025①②③④⑤⑥68441226796401322106又如下圖所示的截集為上圖所示的截集為所有截量中此截量最小且等于最大流量，此截集稱為最小截集。【定理】最大流量等于最小截集的截量。4/8/2025鏈：從發點到收點的一條路線（弧的方向不一定都同向）稱為鏈。從發點到收點的方向規定為鏈的方向。前向弧：與鏈的方向相同的弧稱為前向弧。后向弧：與鏈的方向相反的弧稱為后向弧。增廣鏈

設f

是一個可行流，如果存在一條從vs到vt的鏈，滿足：1.所有前向弧上fij<Cij2.所有后向弧上fij>0則該鏈稱為增廣鏈①②③④⑤⑥前向弧后向弧8446952346容量流量想一想，這是一條增廣鏈嗎？4/8/2025【定理】設網絡G的一個可行流f，如果存在一條從vs到vt的增廣鏈，那么就可改進一個值更大的可行流f1，并且val

f1>valf【證】設valf＝v對改進的可行流f1：4/8/2025最大流的標號算法步驟1.找出第一個可行流，例如所有弧的流量fij=02.用標號的方法找一條增廣鏈

A1：發點標號（∞），

A2：選一個點vi已標號并且另一端未標號的弧沿著某條鏈向收點檢查：如果弧的方向向前并且有fij<Cij，則vj標號（Cij－fij)

如果弧的方向指向vi并且有fji>0，則vj標號（fji)當收點不能得到標號時，說明不存在增廣鏈，計算結束。當收點已得到標號時，說明已找到增廣鏈。【定理】可行流是最大流當且僅當不存在發點到收點的增廣鏈4/8/20254.調整流量得到新的可行流，去掉所有標號，從發點重新標號尋找增廣鏈，直到收點不能標號為止。3.依據vi的第一個標號反向跟蹤得到一條增廣鏈；依據vi的第二個標號求最小值得到調整量θ進入演示和練習4/8/2025∞①②③④⑤⑥684412267942202222046217【例】求下圖v1到v6的最大流及最大流量【解】1.通過觀察得到初始可行流2.標號3.得到增廣鏈4/8/2025∞①②③④⑤⑥68441226794211322304223得到增廣鏈4.求調整量5.調整可行流去掉所有標號，重新標號∞①②③④⑤⑥6844122679422022220462174/8/2025①②③④⑤⑥68441226796411322306求調整量調整可行流去掉所有標號，重新標號∞5標號不能繼續進行，說明不存在從發點到收點的增廣鏈，得到最大流.最大流量v=6+3=914/8/2025TheEndofChapter6作業:教材P285T10.1110.1210.14下一章：網絡計劃Exit1.基本概念容量、流量、可行流、前向弧、后向弧、