圖論總結(jié)(超強(qiáng)大)解讀

1、ADN.cnlibrarysummary圖論總結(jié)2022323 /33 /33圖論GraphTheory定義與術(shù)語DefinitionandGlossary圖與網(wǎng)絡(luò)GraphandNetwork圖的術(shù)語GlossaryofGraph路徑與回路PathandCycle連通性Connectivity圖論中特殊的集合Setsingraph匹配Matching樹Tree組合優(yōu)化Combinatorialoptimization圖的表示Expressionsofgraph鄰接矩陣Adjacencymatrix關(guān)聯(lián)矩陣Incidencematrix鄰接表Adjacencylist弧表Arclist星形表示

2、Star圖的遍歷Travelingingraph深度優(yōu)先搜索Depthfirstsearch(DFS)概念求無向連通圖中的橋Findingbridgesinundirectedgraph廣度優(yōu)先搜索Breadthfirstsearch(BFS)拓?fù)渑判騎opologicalsort路徑與回路Pathsandcircuits1.5.1.歐拉路徑或回路Eulerianpath.無向圖.有向圖.混合圖.無權(quán)圖Unweighted.有權(quán)圖Weighed中國(guó)郵路問題TheChinesepostproblemHamiltonianCycle哈氏路徑與回路無權(quán)圖Unweighted有權(quán)圖Weighed旅行商

3、問題Thetravellingsalesmanproblem網(wǎng)絡(luò)優(yōu)化Networkoptimization最小生成樹Minimumspanningtrees基本算法BasicalgorithmsPrimKruskalSollin(Boruvka)擴(kuò)展模型Extendedmodels度限制生成樹Minimumdegree-boundedspanningtreesk小生成樹Thekminimumspanningtreeproblem(k-MST)最短路Shortestpaths單源最短路Single-sourceshortestpaths基本算法BasicalgorithmsDijkstraBel

4、lman-FordShortestpathfasteralgorithm(SPFA)應(yīng)用Applications差分約束系統(tǒng)Systemofdifferenceconstraints有向無環(huán)圖上的最短路ShortestpathsinDAG所有頂點(diǎn)對(duì)間最短路All-pairsshortestpaths基本算法BasicalgorithmsFloyd-WarshallJohnson網(wǎng)絡(luò)流Flownetwork最大流MaximumflowFord-FulkersonmethodEdmonds-KarpalgorithmMinimumlengthpathMaximumcapabilitypath預(yù)流推

5、進(jìn)算法PreflowpushmethodPush-relabelRelabel-to-front基本算法BasicalgorithmsDinicmethod擴(kuò)展模型Extendedmodels.2.1.有上下界的流問題最小費(fèi)用流Minimumcostflow找最小費(fèi)用路Findingminimumcostpath找負(fù)權(quán)圈Findingnegativecircle網(wǎng)絡(luò)單純形Networksimplexalgorithm匹配Matching二分圖BipartiteGraph無權(quán)圖-匈牙利算法Unweighted-HopcroftandKarpalgorithm帶權(quán)圖-KM算法WeightedKuh

6、n-Munkres(KM)algorithm一般圖GeneralGraph無權(quán)圖-帶花樹算法Unweighted-Blossom(Edmonds)1.圖論GraphTheory定義與術(shù)語DefinitionandGlossary圖與網(wǎng)絡(luò)GraphandNetwork二元組(V,E)稱為圖(graph)。V為結(jié)點(diǎn)(node)或頂點(diǎn)(vertex)集。E為V中結(jié)點(diǎn)之間的邊的集合。點(diǎn)對(duì)(u,v)稱為邊(edge)或稱弧(arc),其中u,veV，稱u,v是相鄰的(adjacent)，稱u,v與邊(u,v)相關(guān)聯(lián)(incident)或相鄰。若邊的點(diǎn)對(duì)(u,v)有序則稱為有向(directed)邊，其中

7、u稱為頭(head),v稱為尾(tail)。所形成的圖稱有向圖(directedgraph)。為對(duì)于u來說(u,v)是出邊(outgoingarc)；對(duì)于v來說(u,v)是入邊(incomingarc)。反之，若邊的點(diǎn)對(duì)無序則稱為無向(undirected)邊，所形成的圖稱無向圖(undirectedgraph)。若圖的邊有一個(gè)權(quán)值(weight)，貝V稱為賦權(quán)邊，所形成的圖稱賦權(quán)圖(weightedgraph)或網(wǎng)絡(luò)(network)。用三元組G(V,E,W)表示網(wǎng)絡(luò)。其中W表示權(quán)集，它的元素與邊集E對(duì)應(yīng)。滿足|E1Y(G)。VV定理：連通圖中，V是點(diǎn)覆蓋，則V是支配集。極小點(diǎn)覆蓋不一定是極

8、小支配集。支配集不一定是點(diǎn)覆蓋。定理：無向圖G無孤立點(diǎn)，V是(極，最小)點(diǎn)覆蓋，充要于V-V是(極，最大)獨(dú)立集。a(G)+0(G)=|V|。VV定理:無向圖G,V是G的(極,最大)團(tuán),充要于V是G的(極,最大)獨(dú)立集。co(G)=0v(G)。由上述定理知，a(G),P(G),譏G)三者互相確定，但都是NPC的。但是二分圖中，VV點(diǎn)覆蓋數(shù)是匹配數(shù)。M是匹配，W是邊覆蓋，N是點(diǎn)覆蓋，Y是點(diǎn)獨(dú)立集。定理：無向圖G無孤立點(diǎn)，|M|=|N|,|Y|W(v,w)，則d(w)=W(v,w)，轉(zhuǎn)2。這里的d可以用優(yōu)先隊(duì)列實(shí)現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。假設(shè)用

9、FibonacciHeap實(shí)現(xiàn)(刪除最小O(logn)，減值O)，算法復(fù)雜度：O(nlogn+m)。Kruskal基本思想：就是維護(hù)一個(gè)生成森林。每次將一條權(quán)最小的邊加入子圖T中，并保證不形成圈。如果當(dāng)前弧加入后不形成圈，則加入這條弧，如果當(dāng)前弧加入后會(huì)形成圈，則不加入這條弧，并考慮下一條弧。算法：T=0,i=0，將E中的邊按權(quán)從小到大排序，W(e)W(e)m，結(jié)束，此時(shí)G沒有生成樹；否則判斷Tue是否含圈，是則轉(zhuǎn)2,否則轉(zhuǎn)3。iT=Tue。若ITI=N，結(jié)束，此時(shí)T為G的最小生成樹。i分離集合(disjointset)，可用并查集實(shí)現(xiàn)。由于排序是O(mlogm)的。所以復(fù)雜度為O(mlogm

10、+ma(n)。Sollin(Boruvka)基本思想：前面介紹的兩種算法的綜合。每次迭代同時(shí)擴(kuò)展多棵子樹，直到得到最小生成樹T。算法：對(duì)于所有veV,G=v。T=0。v若|T|=N，結(jié)束，此時(shí)T為G的最小生成樹；否則，對(duì)于T中所有的子樹集合G，計(jì)算它v的邊割G,G中的最小弧e*(有的書稱連接兩個(gè)連通分量的最小弧“安全邊”)。vvv對(duì)T中所有子樹集合G及其邊割最小弧e*=(p,q)，將G與q所在的子樹集合合并。vvvT=Tue*。轉(zhuǎn)2。v由于每次循環(huán)迭代時(shí)，每棵樹都會(huì)合并成一棵較大的子樹，因此每次循環(huán)迭代都會(huì)使子樹的數(shù)量至少減少一半，或者說第i次迭代每個(gè)分量大小至少為2i。所以，循環(huán)迭代的總次數(shù)

11、為O(logn)。每次循環(huán)迭代所需要的計(jì)算時(shí)間：對(duì)于第2步，每次檢查所有邊O(m)，去更新每個(gè)連通分量的最小?。粚?duì)于第3步，合并O(n/2i)個(gè)子樹。所以總的復(fù)雜度為O(mlogn)。RindSafhEdghs(VE):Bdruvka(YE):T=(V,0whileFhasmorethanonecamponentdiooseleadersusingDFSFindSabEdgbsCYE)foreadileadervaddsafe(v)tcFforeach,leadervsafe(v)coforcacLedge(u,)Euleader(u)vleader(u)if遼爭(zhēng)方ifwfsafefiL)sa

12、fe(u)if)safe(5)1(叫訶1612擴(kuò)展模型Extendedmodels16121度限制生成樹Minimumdegree-boundedspanningtrees由于這個(gè)問題是NP-Hard的，一般用搜索算法解決。本文就只討論一種特殊多項(xiàng)式情況:單點(diǎn)度限制(onenodedegreebounded)。把度限制的點(diǎn)記為v，滿足度限制deg(v)k。一種貪心的思路：在最小生成樹T的基礎(chǔ)00上，通過添刪邊來改造樹，使之逐漸滿足度限制條件。算法：求圖的最小生成樹T。若v已滿足度限制，結(jié)束；否則轉(zhuǎn)3。0對(duì)于刪去v后的每一個(gè)連通分支T(為一棵樹)，求添加邊割T,T-v中的最小弧，0iii0刪除邊

13、割T,v0里的最大弧后的生成樹中的邊權(quán)和最小的一個(gè)。更新最小生成樹T。i轉(zhuǎn)2。第3步，v的度少1。0習(xí)題：NOI2005小H的聚會(huì)16122k小生成樹Thekminimumspanningtreeproblem(k-MST)生成樹T刪除一條邊f(xié)并加入一條新邊e的操作稱為交換。若交換后的圖仍是一顆樹，則此交換稱為可行交換。若生成樹T可通過一次交換成為生成樹T,則稱它們互為鄰樹。對(duì)于生成樹集合S,生成樹T,若T不在S中，且在S中存在某生成樹是T的鄰樹，稱為T為S的鄰樹。定理：設(shè)T,T,T為圖的前k小生成樹，則生成圖集合T,T的鄰樹中的邊權(quán)和12k12k最小者可作為第k+1小生成樹(可能有邊權(quán)和相同

14、的情況)。按這個(gè)定理設(shè)計(jì)算法，很難得到有滿意的時(shí)間復(fù)雜度的算法。下面討論一個(gè)特例：次小生成樹(ThesecondMST,2-MST)基本思想：枚舉最小生成樹T的每一個(gè)鄰樹，即枚舉被添加與被刪除的邊。由于在樹中添加一條邊(u,v)(u,v)電T)，一定形成了一個(gè)環(huán)，環(huán)是由(u,v)與從u到v的生成樹上的唯一路徑(記為P(u,v)組成的。所以被刪除的邊一定在P(u,v)上。由于要求最小邊權(quán)和，所以被刪除的邊一定是P(u,v)上最小者，其權(quán)值記為f(u,v):f(u,v)=minw(e)|eeP(u,v)。算法：求圖的最小生成樹T。次小生成樹T的權(quán)值的最小值w(T)=x。以每個(gè)結(jié)點(diǎn)為根r，DFS遍歷

15、樹。在遍歷過程中求出f(r,v)|veV，用w(T)+w(r,v)-f(r,v)更新次小生成樹的權(quán)值的最小值w(T)。輸出w(T)。算法復(fù)雜度的瓶頸在第2步O(n2)，故總算法復(fù)雜度為O(n2)。習(xí)題：Ural1416Confidential最短路Shortestpaths單源最短路Single-sourceshortestpaths令s為起點(diǎn)，t為終點(diǎn)。單源最短路問題定義為：對(duì)于網(wǎng)絡(luò)G=(V,E,W)，尋找s到t的一條簡(jiǎn)單路徑，使得路徑上的所有邊權(quán)和最少。令d(v)為s到v的最短路長(zhǎng)度上界。單源最短路問題的規(guī)劃模型如下：mind(t)s.t.d(v)d(u)+w(u,v)(u,v)eEd(s

16、)=0對(duì)于只含正有向圈的連通有向網(wǎng)絡(luò)，從起點(diǎn)s到任一頂點(diǎn)j都存在最短路，它們構(gòu)成以起點(diǎn)s為根的樹形圖(稱為最短路樹(TreeofShortestPaths)。當(dāng)某弧(u,v)位于最短路上時(shí),一定有d(v)-d(u)=w(u,v)。所以最短路的長(zhǎng)度可以由Bellman方程(最短路方程)唯一確定:d(s)二0d(v)二mind(u)+w(u,v)u豐v在規(guī)劃模型與最短路方程中都出現(xiàn)了d(v)d(u)+w(u,v)，則改進(jìn)d(v)=d(u)+w(u,v)。直觀的講，就是路徑最后通過(u,v)，使得s到v的距離比原來s到v的方案的距離短。松弛操作是最短路算法求解的基本方式。最短路算法求解過程中的標(biāo)號(hào)規(guī)

17、定：對(duì)于V中每一個(gè)頂點(diǎn)v,設(shè)置一個(gè)標(biāo)號(hào)：距離標(biāo)號(hào)d(v),記錄的是從起點(diǎn)到該頂點(diǎn)的最短路長(zhǎng)度的上界；再設(shè)置一個(gè)是前趨pred(v)，記錄的是當(dāng)起點(diǎn)s到該頂點(diǎn)v的一條路長(zhǎng)取到該上界時(shí)，該條路中頂點(diǎn)v前面的那個(gè)直接前趨。算法通過不斷修改這些標(biāo)號(hào)，進(jìn)行迭代計(jì)算。當(dāng)算法結(jié)束時(shí)，距離標(biāo)號(hào)表示的是從起點(diǎn)到該頂點(diǎn)的最短路長(zhǎng)度。標(biāo)號(hào)設(shè)定算法(Label-Setting):在通過迭代過程對(duì)標(biāo)號(hào)進(jìn)行逐步修正的過程中，每次迭代將一個(gè)頂點(diǎn)從臨時(shí)標(biāo)號(hào)集合中移入永久標(biāo)號(hào)集合中。標(biāo)號(hào)修正算法(Label-Correcting)：每次迭代時(shí)并不一定將任何頂點(diǎn)標(biāo)號(hào)從臨時(shí)標(biāo)號(hào)轉(zhuǎn)變?yōu)橛谰脴?biāo)號(hào)，只是對(duì)臨時(shí)標(biāo)號(hào)進(jìn)行一次修正，所有頂點(diǎn)標(biāo)

18、號(hào)仍然都是臨時(shí)標(biāo)號(hào)；只有在所有迭代終止時(shí)，所有頂點(diǎn)標(biāo)號(hào)同時(shí)轉(zhuǎn)變?yōu)橛谰脴?biāo)號(hào)。最長(zhǎng)路問題可以轉(zhuǎn)化為最短路問題，把弧上的費(fèi)用反號(hào)即可?；舅惴˙asicalgorithmsDijkstra采用了標(biāo)號(hào)設(shè)定算法(Label-Setting)。在迭代進(jìn)行計(jì)算的過程中，所有頂點(diǎn)實(shí)際上被分成了兩類：一類是離起點(diǎn)較近的頂點(diǎn)，它們的距離標(biāo)號(hào)表示的是從點(diǎn)s到該頂點(diǎn)的最短路長(zhǎng)度,因此其標(biāo)號(hào)不會(huì)在以后的迭代中再被改變(稱為永久標(biāo)號(hào))；一類是離起點(diǎn)較遠(yuǎn)的頂點(diǎn)，它們的距離標(biāo)號(hào)表示的只是從點(diǎn)到該頂點(diǎn)的最短路長(zhǎng)度的上界，因此其標(biāo)號(hào)還可能會(huì)在以后的迭代中再被改變(稱為臨時(shí)標(biāo)號(hào))。下文稱永久標(biāo)號(hào)為已檢查。算法：d(s)=0，d(v

19、)=8,(v豐s)，已檢查U=0取未檢查的u，即uU，使得d(u)最小。若u取不到，即d(u)=g則結(jié)束；否則標(biāo)記為已檢查，即U=Uuu。枚舉所有的u的臨邊(u,v)，滿足v未檢查，即v笑U。松弛(u,v)，即若d(v)d(u)+w(u,v)，則改進(jìn)d(v)=d(u)+w(u,v),pred(v)=u。轉(zhuǎn)2。這里的d可以用優(yōu)先隊(duì)列實(shí)現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。假設(shè)用FibonacciHeap實(shí)現(xiàn)(刪除最小O(logn)，減值O(l),則算法復(fù)雜度：O(nlogn+m)。若用BinaryHeap則O(n+m)logn)。適用范圍：非負(fù)權(quán)圖。Be

20、llman-Ford采用了標(biāo)號(hào)修正算法(Label-Correcting)。本質(zhì)就是用迭代法(動(dòng)態(tài)規(guī)劃)解Bellman-Ford方程：d(l)(s)=0,d(1)(v)=w(s,v),v豐sd(k+1)(v)=mind(k)(v),mind(k)(u)+w(u,v),u,vgV,k=1,2,，n一2u工vd(k)(v)表示s到V的且邊數(shù)不超過k條時(shí)的最短路路長(zhǎng)。下面用歸納法證明：k=1顯然成立。假設(shè)對(duì)k成立，下面考慮k+1的情況.從起點(diǎn)s到頂點(diǎn)V且所經(jīng)過的弧數(shù)不超過k+1條時(shí)的最短路有兩種可能：含有不超過k條弧，即d(k)(v)；含有k+1條弧，即mind(k)(u)+w(u,v)。u工v由

21、于第k+1次迭代過程中，不會(huì)影響k次的迭代結(jié)果，d用O(n)的空間即可。算法：d(s)=0，d(v)=8,(v主s)松弛所有邊(u,v)，即若d(v)d(u)+w(u,v)，則改進(jìn)d(v)=d(u)+w(u,v)，pred(v)=u。若沒有邊被松弛，則算法結(jié)束。若2的迭代次數(shù)超過n-1，則有負(fù)權(quán)圈，結(jié)束；否則轉(zhuǎn)2繼續(xù)迭代?？梢宰C明算法一定在n-1步迭代后收斂；否則一定有負(fù)權(quán)圈。所以算法復(fù)雜度為O(nm)。適用范圍：一般圖。.1.2.1.Shortestpathfasteralgorithm(SPFA)SPFA其實(shí)就是Bellman-Ford的一種隊(duì)列實(shí)現(xiàn)，減少了冗余，即松馳的邊至少不會(huì)以一個(gè)d

22、為a的點(diǎn)為起點(diǎn)。算法：隊(duì)列Q=s，d(s)=0，d(v)=8,(v豐s)取出隊(duì)頭u，枚舉所有的u的臨邊(u,v)。若d(v)d(u)+w(u,v)，則改進(jìn)d(v)=d(u)+w(u,v),pred(v)=u,由于d(v)減少了，v可能在以后改進(jìn)其他的點(diǎn)，所以若v不在Q中，則將v入隊(duì)。一直迭代2，直到隊(duì)列Q為空(正常結(jié)束)，或有的點(diǎn)的入隊(duì)次數(shù)=n(含有負(fù)圈)。由于點(diǎn)可能多次入隊(duì)，但隊(duì)列中同時(shí)不會(huì)超過n個(gè)點(diǎn)。所以用一個(gè)長(zhǎng)度為n的循環(huán)隊(duì)列來實(shí)現(xiàn)這個(gè)隊(duì)。SPFA在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，

23、也就是一個(gè)點(diǎn)改進(jìn)過其它的點(diǎn)之后，過了一段時(shí)間可能本身被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。設(shè)一個(gè)點(diǎn)用來作為迭代點(diǎn)對(duì)其它點(diǎn)進(jìn)行改進(jìn)的平均次數(shù)為k有辦法證明對(duì)于通常的(不含負(fù)圈，較稀疏)情況,k在2左右。算法復(fù)雜度理論上同Bellman-Ford，O(nm)，但實(shí)際上卻是O(km)。一般用于找負(fù)圈(效率高于Bellman-Ford)，稀疏圖的最短路。習(xí)題：Ural1254DieHard(可斜走的網(wǎng)格最短路)。應(yīng)用Applications差分約束系統(tǒng)Systemofdifferenceconstraints差分約束系統(tǒng)：求解n個(gè)未知數(shù)x，滿足m個(gè)不等式：ix一xb,1i,jn,1kmj

24、ik若描述為線形規(guī)劃模型：AxB。mxn矩陣A每行含一個(gè)1一個(gè)-1，其他都是0。如線形規(guī)劃模型(10一10、(-2010-1(x)14100-11x5201一10 x-3-10013lxj421一100丿i3丿等價(jià)于x一x一2TOC o 1-5 h z13x一x424x一x514x一x一323x一x241x一x312注意到單源最短路模型中的。d(v)d(u)+w(u,v),即d(v)-d(u)w(u,v)。很像差分約束系統(tǒng)模型。于是可以構(gòu)造一個(gè)有向網(wǎng)絡(luò)G=(V,E,W),稱為約束圖(constraintsgraph)。V=v,v,v，,v。E=(v,v)|x一xb+(v,v)11inTOC o

25、 1-5 h z012nijjik0iW：w(i,j)=b|x-xd(u)+w(u,v),則改進(jìn)d(v)=d(u)+w(u,v)，pred(v)=u。轉(zhuǎn)2。復(fù)雜度：O(m)所有頂點(diǎn)對(duì)間最短路All-pairsshortestpaths基本算法BasicalgorithmsFloyd-Warshall本質(zhì)就是用迭代法(動(dòng)態(tài)規(guī)劃)：d(1)(u,u)=0,ugVd(1)(u,v)=w(u,v),u,vgVd(k+1)(u,v)=mind(k)(u,v),d(k)(u,k)+d(k)(k,v),u,vgV,k=1,2，n-1d(k)(u,v)表示u到v的不經(jīng)過k,k+1,n結(jié)點(diǎn)(除u,v外)時(shí)，從u

26、,v的最短路長(zhǎng)。下面用歸納法證明：k=1顯然成立。假設(shè)對(duì)k成立，下面考慮k+1的情況；從u到v且不通過k+1,n節(jié)點(diǎn)的最短路有兩種可能：(1)不經(jīng)過k節(jié)點(diǎn),即為d(k)(u,v)；(2)經(jīng)過k節(jié)點(diǎn),即為d(k)(u,k)+d(k)(k,v)。由于第k+1次迭代過程中，不會(huì)影響k次的迭代結(jié)果，d用O(n2)的空間即可。二維數(shù)組p(u,v),記錄u到V,最后經(jīng)過哪個(gè)k的迭代。算法：k=1，對(duì)于所有u,v，d(u,v)=w(u,v),p(u,v)=vk=k+1，對(duì)于所有u,v,若d(u,v)d(u,k)+d(k,v)，則d(u,v)=d(u,k)+d(k,v)，p(u,v)=k。若發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)u使得

27、d(k)(u,u)h(v)，所以w(u,v)=w(u,v)+h(u)-h(v)0。令路徑p=(v,v，,v)，貝912ni-1iw(p)=工w(v,v)=w(v,v)+h(v)-h(v)i-1ii-1ii=2i=2=w(p)+h(v)一h(v)1kw(p)只與w(p)以及首尾的標(biāo)號(hào)h有關(guān)，不影響w(p)的決策。所以w(p)是最短路長(zhǎng)當(dāng)且僅當(dāng)W(p)是最短路長(zhǎng)，且不影響最短路p。參考文獻(xiàn)：125.3Johnsonsalgorithmforsparsegraphs，IntroductiontoAlgorithms，MITPress網(wǎng)絡(luò)流Flownetwork最大流Maximumflow在有向無權(quán)圖

28、G(V,E,C)中，其中C為每條邊的容量(capability)c(u,v),再給每條邊賦予個(gè)流值(flow)f(u,v)，并規(guī)定源s和匯t。最大流問題的數(shù)學(xué)模型描述如下:(1)max工f(s,v)veVs.t.f(u,v)c(u,v)u,veVf(u,v)=-f(v,u)u,veV工f(u,v)=0ueV-s,tveV其中(2)f(u,v)V,那么我們就有一些流量需要在u繼續(xù)往上進(jìn)行處理，使用剛才在V點(diǎn)同樣的辦法，直到一直處理到了S，一路上肯定是不會(huì)出現(xiàn)什么障礙的。然后我們將c從V運(yùn)送到t,我們?cè)跇?gòu)造這個(gè)層次圖的時(shí)候很容易就可以保證所有從S出發(fā)的路徑都會(huì)在t終結(jié)，這樣就好辦了，使用上面同樣的

29、辦法，只是處理的方向是從V到t了。這樣，我們剛才處理的過程就容易得到下面的下面所謂的性質(zhì)了。*)上面的算法給了我們一個(gè)可以在0(mn)的時(shí)間內(nèi)充滿這個(gè)層次圖的算法，下面進(jìn)一步分析。為了得到我們需要的界，我們需要這樣一個(gè)性質(zhì)：當(dāng)我們?cè)谏厦娴膶?duì)每個(gè)新的頂點(diǎn)V執(zhí)行算法的步驟中，保證對(duì)每條邊我們只檢查一次，對(duì)其做完所有需要的操作之后才會(huì)去做下一條邊。這點(diǎn)意味著，我們可以把運(yùn)行時(shí)間分成兩個(gè)部分來考慮：a)花在被充滿的邊上的時(shí)間b)花在沒有被充滿的邊上的時(shí)間。對(duì)于a),因?yàn)槲覀兠看纬錆M一條邊就會(huì)把它從圖中刪除，所以a)的總時(shí)間是0(m)。因此我們的時(shí)間主要由b)來決定，而b)對(duì)應(yīng)的邊在對(duì)每個(gè)新的頂點(diǎn)v的執(zhí)行過程中至多出現(xiàn)0(n)次，因此總的時(shí)間是0(22)。而我們可以在0(m)的時(shí)間內(nèi)重新計(jì)算新的層次圖，所以我們就可以在O(nm+nnA2)時(shí)間完成整個(gè)算法，也就是0(3)。擴(kuò)展模型Extendedmodels有上下界的流問題問題模型：給定一個(gè)加權(quán)的有向圖G(V,E,B,C)，滿足:容量限制條件：b(u,v)f(u,v)a的弧(t,maxmaxs),則從在這個(gè)改造后的圖中一定沒有無源匯的可行流：否則將這個(gè)可行流中的弧(t,s)除去，就