GraphDefinitionandGraphand圖的術 Glossaryof路徑與回 Pathand連通性Setsin樹CombinatorialExpressionsofAdjacency關聯矩陣IncidenceAdjacencyArc星形表示圖的遍歷Travelingin深度優先搜索DepthsearchFindingbridgesinundirected廣度優先搜索 searchTopologicalPathsand歐拉路徑或回路Eulerian無權圖Weighed—TheChinesepostHamiltonianCycle無權圖Weighed—ThetravellingsalesmanNetworkMinimumspanning基本算法BasicExtendedMinimumdegree-boundedspanningkThekminimumspanningtreeproblem(k-ShortestSingle-sourceshortest基本算法BasicShortestpathfasterSystemofdifferenceShortestpathsinAll-pairsshortest基本算法Basicalgorithms Flow最大 um基本算法Basicalgorithms Ford-FulkersonmethodEdmonds-KarpMinimumlength umcapabilityPreflowpushDinic1.6.3.1.2.擴展模型Extendedmodels MinimumcostFindingminimumcostFindingnegativeNetworksimplex二分圖Bipartite無權圖-UnweightedHopcroftandKarp帶權圖-KMWeightedKuhn-Munkres(KMGeneral無權圖-UnweightedBlossomGraph定義與術語Definitionand圖與網絡Graphand二元組VE稱為圖(graph)。V為結點(node)或頂點(vertex)集。E為V中結點之間的邊的點對uv稱為邊(edge)或稱弧(arc)，其中uvV，稱u,v是相鄰的(adjacent)u,vu,v相關聯(incident)或相若邊的點對u,v有序則稱為有向(directed)邊，其中u稱為頭(head)，v稱為尾(tail)成的圖稱有向圖(directedgraph)對于u來說uv是出邊(outgoingarc)；對于v來說uv ingarc)。反之，若邊的點對無序則稱為無向(undirected)邊，所形成的圖稱無向圖(undirectedgraph)。若圖的邊有一個權值(weight)，則稱為賦權邊，所形成的圖稱賦權圖(weightedgraph)或網滿足|E||V|log|V|的圖，稱為稀疏(sparse)圖；反之，稱為稠密(dense)圖的術語Glossaryof階(order)GVG簡單圖(simplegraph)：沒有環、且沒有多重弧的圖稱作簡單圖。定向圖G的每條無向邊指定一個方向得到的有向圖。競賽圖(tournament)：有向圖的底圖是無向完全圖，則此有向圖是競賽圖鄰域(neighborhood)u相鄰的點的集合{v|vVuvE}u的鄰域，記N(u。度(degree)vdeg(v)deg(v)2|E|degv)degv 的條數，記作degv出度(outdegree)：在有向圖中，一個頂點的出度是指與該邊相關聯的出邊(即邊的頭是的條數，記作degv孤立點(isolatedvertex)0的點。葉(leaf)1源(source)degv=0的點。匯(sink)degv=0的點。奇點(oddvertex)：度為奇數的點。偶點(evenvertex)：度為偶數的點。子圖(sub-graph)：G'G的子圖如果V(G')V(GE(G')E(G生成子圖(spanningsub-graph)：即包含G的所有頂點的連通子圖，即滿足條件V(G')V(GGG’TGG點導出子圖(inducedsubgraph)：設VV(G，以V為頂點集，以兩端點均在V中的邊的全體為邊集所組成的子圖，稱為G的由頂點集V導出的子圖，簡稱為G的點導出子圖，記為G[V]。邊導出子圖(edge-inducedsubgraph)EE(G，以EE中GEG的邊導出子圖，記為G[E]。圖的補圖(complement)：設G是一個圖，以V(G為頂點集，以{(uv|uvE(G為邊G的補圖，記為G。點集的補集

VVV為點集V零圖(nullgraph)E，即只有孤立點的圖。nNn平凡圖(trivialgraph)空圖(emptygraph)：VE有向無環圖(directedacyclicgraph(DAG))Kn。二分圖（bipartitegraph）：GXY，即VXYXYXY中，那么這樣的圖稱作完全二分圖(completebipartitegraph)GXY中的頂點都有邊相連，則這樣的圖稱作完全二分圖。若|X|m,|Y|nGKm,n。正則圖(regulargraph)路徑與回路Pathand途徑(walk)Gpvieivi

ei

，滿足

V,

Ei e vi 路(path)：頂點不重復的跡Pvivi

011 k 。0 p1pm，稱閉的(closed)；反之，稱為開的(open)。閉途徑(closedwalk)：起點和終點相同的途徑。閉跡(closedtrail)：起點和終點相同的跡，也稱為回路(circuit)。G中長度為奇數和偶數的圈分別稱為奇圈(oddcycle)和偶圈(evencycle)。對任意uvV(G)xyxy的最短路(shortestpath)，其xy的距離(distance)，記為dG(uv。G的直徑(diameter)Dmax{dG(uv|uvV(G)}簡單圖G中最短圈的長度稱為圖G的圍長(girth)，最長圈的長度稱為圖G的周長連通連通(connected)：在圖G中，兩個頂點間，至少存在一條路徑，稱兩個頂點連通的(connected)；反之，稱非連通(unconnected)弱連通(weaklyconnected)GG中邊的方向的圖才連通圖(connectedgraph)G連通分量或連通分支(connectedbranch,component)：非連通無向圖的極大連通子圖(allyconnectedsub-graph)。具體說，若圖G的頂點集V(G)可劃分為若干非空子V1,V2,,VGG[Vi的通分支（i1,2,,）。圖G的連通分支是G的一個極大連通子圖。圖G連通當且僅當＝1。強連通分量(stronglyconnectedbranch)割點割集(vertexcut)：點集V'VG刪除了V后不連通，但刪除了V的任意真子集后G仍然連通。則稱V點割集。若某一結點就構成就了點割集，則稱此結點割點(cutvertex)。點數最少的點割集稱為點連通k(G)。邊割集(edgecutset)：邊集E'E，若G刪除了E后不連通，但刪除了E的任意真子集后G仍然連通。則稱E'點割集。若某一邊就構成就了邊割集，則稱此結點割邊(cutedge)或橋(bridge)。邊數最少的邊割集稱為邊連通k’(G)。記號[S,S]表示一端在S中另一端在S中的所有邊的集合。圖論中特殊的集合Setsin點覆蓋(集)(vertexcovering(set))：V'V，滿足對于eE，有vV'v關聯e。即一covering)number)邊覆蓋(集)(edgecovering(set))E'E，滿足對于vV，有eE'，e關聯v。即一個邊集，使得所有點都與集合里的邊鄰接?；蛘哒f是“邊”覆蓋了所有“點”。極小邊覆蓋(minimaledgecovering)：本身是邊覆蓋，其真子集都不是。最小邊覆蓋(minimumcovering)number)獨立集(independentset)：V'V，滿足對于uvV，有(uvE大獨立集(alindependentset)：本身為獨立集，再加入任何點都不是。最大獨立集 umindependentset)：點最多的獨立集。獨立數(independentnumber)：最大獨立集的數，記為V(G團(clique)：V'V，滿足對于uvV，有(uvE相鄰?；蛘哒f是導出的子圖是完全圖的點集。極大團(alclique)：本身為團，再加入任何點都不是。最大團(umclique)：點最多的團。團數(cliquenumber)：最大團的點數記為(G)邊獨立集(edgeindependentset)E'E，滿足對于e,fE，有e,f aledgeindependentset)：本身為邊獨立集，再加入任何邊都不是。最大邊獨立集 umedgeindependentset)：邊最多的邊獨集。邊獨立數(edgeindependentnumber)：最大邊獨立集的邊數，記為E(Gmatching)，匹配數(matchingnumber)。支配集(dominatingset)：V'V，滿足對于uVV，有vV'，(uvE極小支配集(minimaldominatingset)：本身為支配集，其真子集都不是。最小支配集(minimumset)number)邊支配集(edgedominatingset)E'E，滿足對于eEE，有fE'e,f極小邊支配集(minimaledgedominatingset)：本身是邊支配集，其真子集都不是。最小邊支配集(minimumedgedominatingset)：邊最少的邊支配集。邊支配數(edge dominatingnumber)：最小邊支配集的邊數，記為E(G)G中無孤立點，DD=V(G)-D也是一個支配集。G無孤立點，V1是極小支配集，則存在V2是極小支配集，且V1V2。定理：無向圖G無孤立點，V'是極大獨立集，則V'是極小支配集。逆命題不成立。V(G)V(G)定理：連通圖中，V是點覆蓋，則V是支配集。極小點覆蓋不一定是極小支配集。支配G無孤立點，V是(極，最小)點覆蓋，充要于VV是(極，最大)V(GV(G|V|GV是G的()V是G的()(GV(G由上述定理知，V(G)，V(G)，(G)三者互相確定，但都是的。但是二分圖中M是匹配，W是邊覆蓋，N是點覆蓋，Y是點獨立集。G無孤立點，|M|<=|N|,|Y|<=|W|剩下的一個未蓋點要用一條邊來覆蓋，邊覆蓋數=|M|+(|V|-2|M|)=|V|-|M|。GE(GV(GV(GE(GG(GV(GP最小路徑覆蓋(pathcovering)：是“路徑”覆蓋“點”，即用盡量少的不相交簡單路徑覆G0(單個點)最小路徑覆蓋數＝G的點數－最小路徑覆蓋中的邊數。應該使得最小路徑覆蓋中的邊數盡量多，但是又不能讓兩條邊在同一個頂點相交。拆點：將每一個頂點i拆成兩個頂點Xi和YiXYXY部。因覆蓋數＝G的頂點數－二分圖的最大匹配數便可以得解。匹配(matching)是一個邊集，滿足邊集中的邊兩兩不鄰接。匹配又稱邊獨立集(edgeindependentset)。在匹配中的點稱為匹配點(matchedvertex)未匹配點(unmatched交錯軌(alternatingpath)是圖的一條簡單路徑，滿足任意相鄰的兩條邊，一條在匹配內，增廣軌(augmentingpath)：是一個始點與終點都為未匹配點的交錯軌。最大匹配(ummatching)是具有最多邊的匹配。匹配數(matchingnumber)完美匹配(perfectmatching)完備匹配(completematching)是匹配了二分圖較小部份的所有點的匹配。綜上，在二分圖中，最小覆蓋數=最大匹配數。邊覆蓋數=最大獨立數=|V|-最大匹配數且|E|=|V|-1；(4)G的任何兩個頂點之間存在唯一的一條路；(5)GG的任何一條弧nCayleynK中，不同生成樹的個數為nn2n組合優化Combinatorial(最)優化(optimization)問題所謂組合(最)優化(combinatorialoptimization)又稱離散優化(discreteoptimization)，它是通過數學方法去尋找離散事件的最優編排、分組、次序或篩選等.這類問題可用數學模型描述minfs.t.g(x)0,x其中D表示有限個點組成的集合(定義域)f為目標函數Fx|xDg(x0}網絡優化(networkoptimization)就是研究與(賦權)NP[1]DictionaryofAlgorithmsandDataStructuresNIST， 數學科學系<<網絡優化>>講/~jxie/courses/netopt圖的表示Expressionsof下面介紹幾種表示圖的數據結構。 用下圖做例子311431145623758鄰接矩陣AdjacencyA(uv)，來表示圖。這種表示法一般用于稠密圖。當圖不是簡單圖，鄰接矩在無權圖中，若邊(uvA(uv=1A(uv=0A

(u,v)

u,v

(u,v)110001100010011在圖中,若邊(u,v)存在,則A(u,v)為它的權值；否則人為的規定A(u,v)=∞或-∞?！轆

w(u, (u,v)u,v

(u,v)關聯矩陣IncidenceB(ukkukuB(uk=1kuB(uk=-1B(uk=0B

vV,k(u,v)vV,k(v,u)

u,k u

10000000100000100000000110000011 鄰接Adjacency82825543210363Arc0363

終 權 指 390390460240530470所謂圖的弧表,43343權84376069星形表示按定位方式，又分前向星形(forwardsstar)與反向星形(reversestar)。前向星形：通過起點間的快速排序O(mlogm)或用額外空間O(m)的計數排序O(m)均可。之后用數組last(u)記錄以結點u為起點的最后一條邊的，并規定last(0)=0。這樣以結點u為起點的邊就是last(u-1)+1到last(u)。圖的例子：01234502346812345678112344552342353489640367鏈表法：給每條邊(u,v)加一個前趨，表示以u為起點的邊鏈表的前一條邊。直觀的講，就是將相同結點的邊用鏈表串起來last(u)存以u為起點的最后一條邊的圖的例子123456527801234567853412145425243337438690600000431，黃亮，<<算法藝術與信息學競賽圖的遍歷Travelingin深度優先搜索Depthsearch概求無向連通圖中Findingbridgesinundirected圈是由一條后向邊(u,v)DFSuv的路徑組成。也就是說uv的路徑上的邊都不可能是橋，應該給以標記。記f(x)為x與其子孫的后向邊所連到的最老祖先(深度最淺)，表示x到f(x)上的邊均不為橋。然而f(x)比較麻煩，其實只要知道f(x)的拓撲序數就可以深度d，或者使用時間戳(TimeStamp)DFN（DFS的次序）。下面以深度為例：g(x)d(f(xDFS樹中從x開始通過前向弧和后向弧所能到達的最小的d。有以下的g(x)

dmind(

c第一次x時，記錄g(c)gg(x)=d(x)，即(father,x)不在圈中，則(father,x)廣度優先搜索 search拓撲排序Topological滿足序中u在v前。拓撲排序就是由一種偏序(particalorder)得到一個全序(稱為拓撲有序(topologicalorder))。偏序是滿足自反性，稱性，傳遞性的序。0的點輸出，并把這個點以及與這把所有入度=0QQuu4u相關的邊(u,v)v0vQ，2。算法復雜度:O(m)。習題：MIPT012CorrectR為非空集合A上的二元關系，如果R滿足自反性(對于每一個x∈A，(x,x)∈R)，反偏序關系，記作≤。如果(x,y)∈R，則記作x≤y，讀作“x小于等于y”。存在偏序關系的集A稱為偏序集(particalorder)。AOV(activityonvertexAOE(activityonedgenetwork)event路徑與回路Pathsand歐拉路徑或回路EulerianGG的所有邊一次且僅一次，則這回路著名的問題：TheK?nigsberg下面有向性無向習題：Ural1124有向習題：CEOI2005Depot混合LRJP324下面在性上的擴展無權Weighed—中國郵路問題TheChinesepost這就是一個經典的問題中國郵路問題：給出通的無向的可重邊的圖G，求最1次。題就等價于找一個奇點構成的完全圖G’(V,E)的最小權匹配(PerfectMatchinginGeneralGraph)。V(G’)G中的奇點，每條邊為兩奇點對應原圖的最短路長度。GG’G’GG’G中被重復遍歷一次,G’’HamiltonianCycle哈氏路徑與回無權圖Weighed 旅行商問題The 網絡優化Network最小生成樹MinimumspanningGT， 基本算Basic基本思想：不斷擴展一棵子樹T(SE'),EE，直到S生成樹T。每次增加一條邊，使得這條邊是由當前子樹結點集S及其補集S所形成的邊割集d(v)vS的最小距離。SvE,d(v0)=0(這里v0是任意一個結點d(v,(vv0若|S|N3找補集Sd最小的節點vSvwdd(w)W(vw則d(w)W(vw2FibonacciHeap實現(O(logn)O(1))O(nlognm?；舅枷耄壕褪且粋€生成森林。每次將一條權最小的邊加入子圖T中，不形T,i0，將E中的邊按權從小到大排序，W(e1)W(e2) W(em)TTei。若|T|=NTG分離集合(disjointset)，可用并查集實現。由于排序是O(mlogm)的。所以復雜度為O(mlogmma(n基本思想：前面介紹的兩種算法的綜合。每次迭代同時擴展多棵子樹，直到得到最小生成樹T。對于所有vV,Gv{v}。T v的邊割G,G中的最小弧e* v對T中所有子樹集合G及其邊割最小弧e*pq，將G與q vTTe*2vi次迭代每個分量大小至少為2i。所以，循環迭代的總次O(logn)2O(m)3步，合并O(n2i個子樹。所以總的復雜度為O(mlogn擴展模Extended度限制生成樹Minimumdegree-boundedspanning單點度限制(onenodedegreebounded)。若v0已滿足度限制，結束；否則轉3對于刪去v0后的每通分支Ti(為一棵樹)，求添加邊割[Ti,Ti{v0}]中的最小弧2。3步v0的度少1習題：NOI2005Hk小生成Thekminimumspanningtreeproblem(k-Tfe的操作稱為交換此交換稱為可行交換。若生成樹T可通過一次交換成為生成樹T’，則稱它們互為鄰樹。對于生成樹集合S，生成樹T，若T不在S中，且在S中存在某生成樹是T的鄰樹，稱為TS定理：設T1,T2, ,Tk為圖的前k小生成樹，則生成圖集合{T1,T2, ,Tk}的鄰樹中的邊權和最小者可作為第k+1小生成樹(可能有邊權和相同的情況)。下面一個特例：次小生成樹(ThesecondMST,2-T的每一個鄰樹，即枚舉被添加與被刪除的邊。由于在樹中添加一條邊(uv(uvT)，一定形成了一個環，環是由(uvuv路徑(P(uv))P(uv)P(uvf(uv)f(uv)min{w(e|eP(uv)}。TT’的權值的最小值w(Tr，DFSf(rv|vVw(Tw(rvf(r更新次小生成樹的權值的最小值w(T輸出w(T2步O(n2，故總算法復雜度為O(n2。習題：Ural1416最短Shortest單源最Single-sourceshortests為起點，tG=(V,E,W)st的一d(v)sv的最短路長度上界。單源最短 d(t)d(v)d(u)w(u, (u,v)d(s)sj都存在最短路，它們構成以起點s為根的樹形圖（稱為最短路樹（TreeofShortestPaths））。當某弧(u,v)位于最短時，一定有d(vd(u)w(uv)Bellman（最短路方程d(s)d(v)min{d(u)w(u,d(v)d(u)w(uv)(u,v)

d(v)d(u)w(u,

d(vd(uw(uv。直觀的講，就是路徑最后通過(u,v)svsv的Vv，設置一個標號：距離標號svv前面的那個直接前趨。算法基本算Basic采用了標號設定算abel-ttin)。在迭代進行計算的過程中，所有頂點實際上被分成s因此其標號不會在以后的迭代中再被改變（稱為標號）；一類是離起點較遠的頂點，它們的距離標號表示的只是從點到該頂點的最短路長度的上界，因此其標號還可能會在以后的迭代中再被改變（稱為臨時標號）。下文稱標號為已檢查。d(s0d(v,(vs，已檢查Uu，即uU，使得d(uud(u)=∞則結束；否則標記為已檢查，即UU{u。u的臨邊(uvvvU(uvd(v)d(uw(uv)則改進d(v)d(uw(uv)，pred(v)=u2d可以用優先隊列實現，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。FibonacciHeap實現(O(logn)O(1))O(nlognm。BinaryHeap則O((nmlogn。d(1)(s)d(1)(v)w(s,

,n,nd(k1)(v)min{d(k)(v),min{d(k)(u)w(u,

u,vV,k1,kk+1的情況.svk+1k

d(kvk+1

min{d(kuw(uv)}k+1k次的迭代結果，dO(n)的空間即可。d(s)0，d(v),(v松弛所有邊(u,v)，即若d(v)d(uw(uv)，則改進d(v)d(uw(uv)，pred(v)=u2n-12n-1O(nm)。ShortestpathfasterSPFABellman-Ford的一種隊列實現，減少了冗余，即松馳的邊至少不會以一d為∞的點為起點。Q={s}d(s)0d(v),(vuu的臨邊(u

d(vd(uw(u

d(vd(uw(uv，pred(v)=u，由于d(v減少了，vQv2Q為空(正常結束)，或有的點的入隊次數>=n（含有負圈）A在形式上和寬度優先搜索非常類似，不同的是寬度優先搜索中一個點出了隊列就不A中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復迭代下去。設一個點用來作為迭代點對其它點進行改進的平均次數為k，有辦法證明對于（k2Bellmadm)，)。習題：Ural1254DieHard（可斜走的網格最短路）。差分約束系統Systemofdifferencenximxjxibk,1i,jn,1kAxB。mnA1一個-10。 0 0 3

x1x3xx 注意到單源最短路模型中的。d(v)d(uw(uv)，即d(vd(u)w(uv)。很像差分約G=(V,E,W)，稱為約束圖(constraintsgraph)。V{v0v1v2 vn}E{(vivj|xjxibk}{(v0vi|1iW：w(i,j)bk|xjxibk，w(v0,vi)對v0Bellman-Ford算法，可以得到d(vixid(viCC是任xixiCxi習題：NOI199901有向無環圖上的最短路Shortestpathsind(s)0d(v),(vsGO(m)u枚舉所有u的臨邊(u,v)，對(u,v)進行松弛操作，即若d(v)d(uw(uv)，則改進d(v)d(uw(uv)，pred(v)=u2。O(m)所有頂點對間最All-pairsshortest基本算Basic本質就是用迭代法（動態規劃d(1)(u,u) ud(1)(u,v)w(u, u,v,nd(k1)(u,v)min{d(k)(u,v),d(k)(u,k)d(k)(k, u,vV,k,nd(kuv表示uv的不經過k,k+1,…,n結點(u,v外)u,v的最短路長。下面用歸節點的最短路有兩種可能：(1)不經過kd(kuv；(2)經過k節點，即為d(kukd(kkv)k+1k次的迭代結果，d用O(n2p(uvuvk的迭代。k=1u,vd(uv)w(uv),p(uv)k=k+1u,v，若d(uv)d(uk)d(kv)d(uv)d(uk)d(kv)，p(uv)ku使得d(ku,u0,O(n3)DijkstraBellman-Ford本算法用了權值改造(rin)straWW’，WstravovoBellman-Fordh(v即vo到v的最短路長。對于所有邊(uv)，權值改造，即令w'(uv)w(uvh(uh(v)。對于每個結點vFibonacciHeapDijkstra算法，可求出v與其算法總復雜度O(n2lognnm權值改造滿足兩個原則：(1)W’非負；(2)u,v，pWuv的最pW’uv的最短路。下證w'(uv)w(uvh(uh(v，滿足以上由于h是v0到v的最短路長，h(uw(uv)h(v)w'(uv)w(uvh(uh(v)0令路徑p(v1,v2 ,vn)， w'(p)w'(vi1,vi)w(vi1,vi)h(vi1)h(vi w(p)h(v1)h(vkwp只與wphwpwp僅當wpp。[1]25.3Johnson'salgorithmforsparsegraphs，IntroductiontoAlgorithms，MIT網絡Flow最大流um個流值(flow)f(uv)st。最大流問題的數學模型描述如下：

f(s,

f(u,v)c(u,

u,vf(u,v)f(v, u,vf(u,v)

uV{s,其中(2)f(uv)c(uv，為容量限制條件：邊的流量不超過邊上的容量。f(u,w)f(w, wV st外的結點流入等于流出。最小切割最大流定理：s-t最大流流值=s-t習題：Ural1277CopsandThieves(最小切割最大流基本算BasicFord-FulkersonEdmonds-Karpalgorithm1.6.3.1.1.1.1.1.Minimumlengthpath1.6.3.1.1.1.1.2.umcapabilitypath1.6.3.1.1.2預流推進算法Preflowpushmethod1.6.3.1.1.3.DinicDINIC&O(mn)O(m)O(m^2n)。下面試著降到O(n^3)。想法：假設d=d(t)，試著的找到很多到t的長度為d的路徑。為了做到這個，看前面得到的層次圖（不考慮所有的后向邊以及兩個端點在同一層的邊）?，F在嘗試著在這個圖中執行盡量多的流量，然后才重新計算剩余因此的目標就是在這個剩余圖中在O(n^2)的時間內找到一個塊流c(v)=vc_in[v],c_out[v]c_in[v]是所有vc_out[v]類似。-找到具有最小容量c的頂點v。如果他的容量是0，ohyeah--就可以把他和與-如果c不為0，那么從s運送c個單位流到v，然后從v運送到t。你可能覺得這v具有最小的容量，c的流量而不會被堵住。這一點意味著，可以在O(m)的時間內充滿v。（*daizi首先，為了從s運送c到v，從v開始向上考慮，把任意一條從v向上的邊給充滿，為什么一定能夠找到這樣一條邊呢然后假設剛才填充的這條邊是u->v，那么就有一些流量需要在u繼續往上進行處理，使用剛才在v點同樣的辦法，直到一直處理到了s，一肯定是不會然后c從v運送到t，在構造這個層次圖的時候很容易就可以保證所有從st終結，這樣就好辦了，使用上面同樣的辦法，只是處理的方vt了。這樣，剛才處理的過程就容易得到下面的下面所謂的性質了為了得到需要的界，需要這樣一個性質：當在上面的對每個新的頂點執行算法的步驟中，保證對每條 只檢查一次，對其做完所有需要的操 a）花在被充滿的邊上的時間b）花在沒有被充滿的邊上的時間。對于a），因為每次充滿一條邊就會把它從圖中刪除，所以a）的總時間是O(m)。因此的時間主要由b）來決定，而b）對應的邊在對每個新的頂點v的執行過程中至多出現O(n)次，因此總的時間是O(n^2)。而可以在O(m)的時間內重新計算新的層次圖，所以就可以在O(nm+nn^2)時間完成整個算法，也就是O(n^3)。擴展模Extended有上下界的流問給定一個的有向圖G(V,E,B,C)，滿足b(uv)f(uv)c(uf(uw

f(w, (2)中的wV{st，即除了源匯外，所有點都滿足流量平衡條件，則稱G為有源匯否則wVG為無源匯網絡。問題[1]ss12t將原弧(u,v)c'(uv)nesb(uv。（紅色表示c'(uv)c(uvb(uv4414s12t 4414s12t233x