圖論總結(jié)超強大

-.z.TOC\o\n\h\z\u1.圖論GraphTheory1.1.定義與術(shù)語DefinitionandGlossary1.1.1.圖與網(wǎng)絡(luò)GraphandNetwork1.1.2.圖的術(shù)語GlossaryofGraph1.1.3.路徑與回路PathandCycle1.1.4.連通性Connectivity1.1.5.圖論中特殊的集合Setsingraph1.1.6.匹配Matching1.1.7.樹Tree1.1.8.組合優(yōu)化binatorialoptimization1.2.圖的表示E*pressionsofgraph1.2.1.鄰接矩陣Adjacencymatri*1.2.2.關(guān)聯(lián)矩陣Incidencematri*1.2.3.鄰接表Adjacencylist1.2.4.弧表Arclist1.2.5.星形表示Star1.3.圖的遍歷Travelingingraph1.3.1.深度優(yōu)先搜索Depthfirstsearch(DFS).概念.求無向連通圖中的橋Findingbridgesinundirectedgraph1.3.2.廣度優(yōu)先搜索Breadthfirstsearch(BFS)1.4.拓?fù)渑判騎opologicalsort1.5.路徑與回路Pathsandcircuits1.5.1.歐拉路徑或回路Eulerianpath.無向圖.有向圖.混合圖.無權(quán)圖Unweighted.有權(quán)圖Weighed—中國郵路問題TheChinesepostproblem1.5.2.HamiltonianCycle哈氏路徑與回路.無權(quán)圖Unweighted.有權(quán)圖Weighed—旅行商問題Thetravellingsalesmanproblem1.6.網(wǎng)絡(luò)優(yōu)化Networkoptimization1.6.1.最小生成樹Minimumspanningtrees.根本算法Basicalgorithms〔Boruvka〕.擴展模型E*tendedmodels.1.度限制生成樹Minimumdegree-boundedspanningtrees小生成樹Thekminimumspanningtreeproblem(k-MST)1.6.2.最短路Shortestpaths.單源最短路Single-sourceshortestpaths.1.根本算法Basicalgorithms.1.2.1.Shortest

path

faster

algorithm(SPFA).2.應(yīng)用Applications.2.1.差分約束系統(tǒng)Systemofdifferenceconstraints.2.2.有向無環(huán)圖上的最短路ShortestpathsinDAG.所有頂點對間最短路All-pairsshortestpaths.1.根本算法Basicalgorithms1.6.3.網(wǎng)絡(luò)流Flownetwork.最大流Ma*imumflow.1.根本算法Basicalgorithms.1.1.Ford-Fulkersonmethod.1.1.1.Edmonds-Karpalgorithm..Minimumlengthpath..Ma*imumcapabilitypath.1.2.預(yù)流推進算法Preflowpushmethod.1.3.Dinicmethod.2.擴展模型E*tendedmodels.2.1.有上下界的流問題.最小費用流Minimumcostflow.1.找最小費用路Findingminimumcostpath.2.找負(fù)權(quán)圈Findingnegativecircle.3.網(wǎng)絡(luò)單純形Networksimple*algorithm1.6.4.匹配Matching.二分圖BipartiteGraph.1.無權(quán)圖-匈牙利算法Unweighted-HopcroftandKarpalgorithm.2.帶權(quán)圖-KM算法Weighted–Kuhn-Munkres(KM)algorithm.一般圖GeneralGraph.1.無權(quán)圖-帶花樹算法Unweighted-Blossom(Edmonds)圖論GraphTheory定義與術(shù)語DefinitionandGlossary圖與網(wǎng)絡(luò)GraphandNetwork二元組稱為圖(graph)。為結(jié)點(node)或頂點(verte*)集。為中結(jié)點之間的邊的集合。點對稱為邊(edge)或稱弧(arc)，其中，稱是相鄰的(adjacent)，稱u,v與邊相關(guān)聯(lián)(incident)或相鄰。假設(shè)邊的點對有序則稱為有向(directed)邊，其中u稱為頭(head)，v稱為尾(tail)。所形成的圖稱有向圖(directedgraph)。為對于u來說是出邊(outgoingarc)；對于v來說是入邊(iningarc)。反之，假設(shè)邊的點對無序則稱為無向(undirected)邊，所形成的圖稱無向圖(undirectedgraph)。假設(shè)圖的邊有一個權(quán)值(weight)，則稱為賦權(quán)邊，所形成的圖稱賦權(quán)圖(weightedgraph)或網(wǎng)絡(luò)(network)。用三元組G(V,E,W)表示網(wǎng)絡(luò)。其中W表示權(quán)集，它的元素與邊集E一一對應(yīng)。滿足的圖，稱為稀疏(sparse)圖；反之，稱為稠密(dense)圖。圖的術(shù)語GlossaryofGraph階(order)：圖G中頂點集V的大小稱作圖G的階。環(huán)(loop)：假設(shè)一條邊的兩個頂點為同一頂點，則此邊稱作環(huán)。簡單圖(simplegraph)：沒有環(huán)、且沒有多重弧的圖稱作簡單圖。定向圖：對無向圖G的每條無向邊指定一個方向得到的有向圖。底圖：把一個有向圖的每一條有向邊的方向都去掉得到的無向圖。逆圖：把一個有向圖的每條邊都反向由此得到的有向圖。競賽圖(tournament)：有向圖的底圖是無向完全圖，則此有向圖是競賽圖。鄰域(neighborhood)：在圖中與u相鄰的點的集合，稱為u的鄰域，記為。度：度(degree)：一個頂點的度是指與該邊相關(guān)聯(lián)的邊的條數(shù)，頂點v的度記作deg(v)。握手定理：無向圖：；有向圖：。入度(indegree)：在有向圖中，一個頂點v的入度是指與該邊相關(guān)聯(lián)的入邊(即邊的尾是v)的條數(shù)，記作。出度(outdegree)：在有向圖中，一個頂點的出度是指與該邊相關(guān)聯(lián)的出邊(即邊的頭是v)的條數(shù)，記作。孤立點(isolatedverte*)：度為0的點。葉(leaf)：度為1的點。源(source)：有向圖中，=0的點。匯(sink)：有向圖中，=0的點。奇點(oddverte*)：度為奇數(shù)的點。偶點(evenverte*)：度為偶數(shù)的點。子圖：子圖(sub-graph)：G'稱作圖G的子圖如果以及。生成子圖(spanningsub-graph)：即包含G的所有頂點的連通子圖，即滿足條件的G的子圖G’。生成樹(spanningtree)：設(shè)T是圖G的一個子圖，如果T是一棵樹，且，則稱T是G的一個生成樹。即G的生成子圖，且子圖為樹。點導(dǎo)出子圖(inducedsubgraph)：設(shè)，以為頂點集，以兩端點均在中的邊的全體為邊集所組成的子圖，稱為G的由頂點集導(dǎo)出的子圖，簡稱為G的點導(dǎo)出子圖，記為。邊導(dǎo)出子圖(edge-inducedsubgraph)：設(shè)，以為頂點集，以兩端點均在中的邊的全體為邊集所組成的子圖，稱為G的由邊集導(dǎo)出的子圖，簡稱為G的邊導(dǎo)出子圖，記為。圖的補圖(plement)：設(shè)G是一個圖，以為頂點集，以為邊集的圖稱為G的補圖，記為。點集的補集：記為點集的補集。特殊的圖：零圖(nullgraph)：，即只有孤立點的圖。n階零圖記為。平凡圖(trivialgraph)：一階零圖?？請D(emptygraph)：的圖。有向無環(huán)圖(directedacyclicgraph(DAG))：有向的無環(huán)的圖。完全圖(pletegraph)：完全圖是指每一對不同頂點間都有邊相連的的無向圖，n階完全圖常記作。二分圖〔bipartitegraph〕：假設(shè)圖G的頂點集可劃分為兩個非空子集*和Y，即且，且每一條邊都有一個頂點在*中，而另一個頂點在Y中，則這樣的圖稱作二分圖。完全二分圖(pletebipartitegraph)：二分圖G中假設(shè)任意兩個*和Y中的頂點都有邊相連，則這樣的圖稱作完全二分圖。假設(shè)，則完全二分圖G記作。正則圖(regulargraph)：如果圖中所有頂點的度皆相等，則此圖稱為正則圖。路徑與回路PathandCycle途徑(walk)：圖G中一個點邊交替出現(xiàn)的序列，滿足，。跡(trail)：邊不重復(fù)的途徑。路(path)：頂點不重復(fù)的跡。簡單圖中的路可以完全用頂點來表示，。假設(shè)，稱閉的(closed)；反之，稱為開的(open)。閉途徑(closedwalk)：起點和終點一樣的途徑。閉跡(closedtrail)：起點和終點一樣的跡，也稱為回路(circuit)。圈(cycle)：起點和終點一樣的路。途徑〔閉途徑〕、跡〔閉跡〕、路〔圈〕上所含的邊的個數(shù)稱為它的長度(length)。簡單圖G中長度為奇數(shù)和偶數(shù)的圈分別稱為奇圈(oddcycle)和偶圈(evencycle)。對任意，從*到y(tǒng)的具有最小長度的路稱為*到y(tǒng)的最短路(shortestpath)，其長度稱為*到y(tǒng)的距離(distance)，記為。圖G的直徑(diameter)：。簡單圖G中最短圈的長度稱為圖G的圍長(girth)，最長圈的長度稱為圖G的周長(perimeter)。連通性Connectivity連通(connected)：在圖G中，兩個頂點間，至少存在一條路徑，稱兩個頂點連通的(connected)；反之，稱非連通(unconnected)。強連通(stronglyconnected)：在有向圖G中，兩個頂點間，至少存在一條路徑，稱兩個頂點強連通。弱連通(weaklyconnected)：在有向圖G中，兩個頂點間，假設(shè)不考慮G中邊的方向的圖才連通的，稱原有向圖為弱連通。連通圖(connectedgraph)：圖G中任二頂點都連通。連通分量或連通分支(connectedbranch,ponent)：非連通無向圖的極通子圖(ma*imallyconnectedsub-graph)。具體說，假設(shè)圖G的頂點集V(G)可劃分為假設(shè)干非空子集，使得兩頂點屬于同一子集當(dāng)且僅當(dāng)它們在G中連通，則稱每個子圖為圖G的一個連通分支〔〕。圖G的連通分支是G的一個極通子圖。圖G連通當(dāng)且僅當(dāng)。強連通分量(stronglyconnectedbranch)：非強連通圖有向圖的極大強連通子圖。割(cut)：點割集(verte*cut)：點集，假設(shè)G刪除了后不連通，但刪除了的任意真子集后G仍然連通。則稱點割集。假設(shè)*一結(jié)點就構(gòu)成就了點割集，則稱此結(jié)點割點(cutverte*)。點數(shù)最少的點割集稱為點連通度k(G)。邊割集(edgecutset)：邊集，假設(shè)G刪除了后不連通，但刪除了的任意真子集后G仍然連通。則稱點割集。假設(shè)*一邊就構(gòu)成就了邊割集，則稱此結(jié)點割邊(cutedge)或橋(bridge)。邊數(shù)最少的邊割集稱為邊連通度k’(G)。記號表示一端在S中另一端在中的所有邊的集合。塊(block)是指沒有割點的極通子圖。圖論中特殊的集合Setsingraph點覆蓋(集)(verte*covering(set))：，滿足對于，有，關(guān)聯(lián)。即一個點集，使得所有邊至少有一個端點在集合里?；蛘哒f是“點〞覆蓋了所有“邊〞。極小點覆蓋(minimalverte*covering)：本身為點覆蓋，其真子集都不是。最小點覆蓋(minimumverte*covering)：點最少的點覆蓋。點覆蓋數(shù)(verte*coveringnumber)：最小點覆蓋的點數(shù)，記為一般說覆蓋集就是指點覆蓋集。邊覆蓋(集)(edgecovering(set))：，滿足對于，有，關(guān)聯(lián)。即一個邊集，使得所有點都與集合里的邊鄰接?；蛘哒f是“邊〞覆蓋了所有“點〞。極小邊覆蓋(minimaledgecovering)：本身是邊覆蓋，其真子集都不是。最小邊覆蓋(minimumedgecovering)：邊最少的邊覆蓋。邊覆蓋數(shù)(edgecoveringnumber)：最小邊覆蓋的邊數(shù)，記為。獨立集(independentset)：，滿足對于，有。即一個點集，集合中任兩個結(jié)點不相鄰，則稱為獨立集?；蛘哒f是導(dǎo)出的子圖是零圖〔沒有邊〕的點集。極大獨立集(ma*imalindependentset)：本身為獨立集，再參加任何點都不是。最大獨立集(ma*imumindependentset)：點最多的獨立集。獨立數(shù)(independentnumber)：最大獨立集的點數(shù)，記為。團(clique)：，滿足對于，有。即一個點集，集合中任兩個結(jié)點相鄰?；蛘哒f是導(dǎo)出的子圖是完全圖的點集。極大團(ma*imalclique)：本身為團，再參加任何點都不是。最大團(ma*imumclique)：點最多的團。團數(shù)(cliquenumber)：最大團的點數(shù)，記為。邊獨立集(edgeindependentset)：，滿足對于，有不鄰接。即一個邊集，滿足邊集中的任兩邊不鄰接。極大邊獨立集(ma*imaledgeindependentset)：本身為邊獨立集，再參加任何邊都不是。最大邊獨立集(ma*imumedgeindependentset)：邊最多的邊獨立集。邊獨立數(shù)(edgeindependentnumber)：最大邊獨立集的邊數(shù)，記為。邊獨立集又稱匹配(matching)，相應(yīng)的有極大匹配(ma*imalmatching)，最大匹配(ma*imummatching)，匹配數(shù)(matchingnumber)。支配集(dominatingset)：，滿足對于，有，。即一個點集，使得所有其他點至少有一個相鄰點在集合里?；蛘哒f是一局部的“點〞支配了所有“點〞。極小支配集(minimaldominatingset)：本身為支配集，其真子集都不是。最小支配集(minimumdominatingset)：點最少的支配集。支配數(shù)(dominatingnumber)：最小支配集的點數(shù)，記為。邊支配集(edgedominatingset)：，滿足對于，有，鄰接。即一個邊集，使得所有邊至少有一條鄰接邊在集合里?；蛘哒f是一局部的“邊〞支配了所有“邊〞。極小邊支配集(minimaledgedominatingset)：本身是邊支配集，其真子集都不是。最小邊支配集(minimumedgedominatingset)：邊最少的邊支配集。邊支配數(shù)(edgedominatingnumber)：最小邊支配集的邊數(shù)，記為。定理：假設(shè)G中無孤立點，D為支配集，則D=V(G)-D也是一個支配集。定理：一個獨立集是極大獨立集，當(dāng)且僅當(dāng)它是支配集。關(guān)系：定理：無向圖G無孤立點，是極小支配集，則存在是極小支配集，且。定理：無向圖G無孤立點，是極大獨立集，則是極小支配集。逆命題不成立。。定理：連通圖中，是點覆蓋，則是支配集。極小點覆蓋不一定是極小支配集。支配集不一定是點覆蓋。定理：無向圖G無孤立點，是(極，最小)點覆蓋，充要于是(極，最大)獨立集。。定理：無向圖G，是G的(極，最大)團，充要于是的(極，最大)獨立集。。由上述定理知，，，三者互相確定，但都是NPC的。但是二分圖中，點覆蓋數(shù)是匹配數(shù)。M是匹配，W是邊覆蓋，N是點覆蓋，Y是點獨立集。定理：無向圖G無孤立點，|M|<=|N|,|Y|<=|W|定理：無向圖G無孤立點，。先取一個最大匹配M，1條邊蓋兩個點；剩下的一個未蓋點要用一條邊來覆蓋，邊覆蓋數(shù)=|M|+(|V|-2|M|)=|V|-|M|。定理：無向圖G無孤立點，=，=。定理：無向圖G無孤立點，=。求匹配數(shù)是P的，所以邊覆蓋和匹配都是易求的。最小路徑覆蓋(pathcovering)：是“路徑〞覆蓋“點〞，即用盡量少的不相交簡單路徑覆蓋有向無環(huán)圖G的所有頂點，即每個頂點嚴(yán)格屬于一條路徑。路徑的長度可能為0(單個點)。最小路徑覆蓋數(shù)＝G的點數(shù)－最小路徑覆蓋中的邊數(shù)。應(yīng)該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個頂點相交。拆點：將每一個頂點i拆成兩個頂點*i和Yi。然后根據(jù)原圖中邊的信息，從*部往Y部引邊。所有邊的方向都是由*部到Y(jié)部。因此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。因此由最小路徑覆蓋數(shù)＝原圖G的頂點數(shù)－二分圖的最大匹配數(shù)便可以得解。匹配Matching匹配(matching)是一個邊集，滿足邊集中的邊兩兩不鄰接。匹配又稱邊獨立集(edgeindependentset)。在匹配中的點稱為匹配點(matchedverte*)或飽和點；反之，稱為未匹配點(unmatchedverte*)或未飽和點。交織軌(alternatingpath)是圖的一條簡單路徑，滿足任意相鄰的兩條邊，一條在匹配，一條不在匹配。增廣軌(augmentingpath)：是一個始點與終點都為未匹配點的交織軌。最大匹配(ma*imummatching)是具有最多邊的匹配。匹配數(shù)(matchingnumber)是最大匹配的大小。完美匹配(perfectmatching)是匹配了所有點的匹配。完備匹配(pletematching)是匹配了二分圖較小部份的所有點的匹配。增廣軌定理：一個匹配是最大匹配當(dāng)且僅當(dāng)沒有增廣軌。綜上，在二分圖中，最小覆蓋數(shù)=最大匹配數(shù)。邊覆蓋數(shù)=最大獨立數(shù)=|V|-最大匹配數(shù)。樹TreeG=(V,E)為一個圖，則以下命題等價：(1)G是一棵樹；(2)G連通，且|E|=|V|-1；(3)G無圈，且|E|=|V|-1；(4)G的任何兩個頂點之間存在唯一的一條路；(5)G連通，且將G的任何一條弧刪去之后，該圖成為非連通圖；(6)G無圈，且在G的任何兩個不相鄰頂點之間參加一條弧之后，該圖正好含有一個圈。Cayley公式：在n階完全圖中，不同生成樹的個數(shù)為。組合優(yōu)化binatorialoptimization從假設(shè)干可能的安排或方案中尋求*種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為(最)優(yōu)化(optimization)問題。所謂組合(最)優(yōu)化(binatorialoptimization)又稱離散優(yōu)化(discreteoptimization)，它是通過數(shù)學(xué)方法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等.這類問題可用數(shù)學(xué)模型描述為：其中D表示有限個點組成的集合(定義域)，f為目標(biāo)函數(shù),為可行域。網(wǎng)絡(luò)優(yōu)化(networkoptimization)就是研究與(賦權(quán))圖有關(guān)的組合優(yōu)化問題。常見的P類網(wǎng)絡(luò)優(yōu)化問題：最小生成樹，最短路，最大流，最小費用最大流，最大匹配，中國郵路問題。常見的NP類網(wǎng)絡(luò)優(yōu)化問題：旅行商問題。參考文獻：[1]DictionaryofAlgorithmsandDataStructuresNIST，./dads/[2]Wikipedia，[3]金星，清華大學(xué)數(shù)學(xué)科學(xué)系<<網(wǎng)絡(luò)優(yōu)化>>講義./~j*ie/courses/netopt圖的表示E*pressionsofgraph下面介紹幾種表示圖的數(shù)據(jù)構(gòu)造。并統(tǒng)一用以下圖做例子：11234512378654鄰接矩陣Adjacencymatri*用二元數(shù)組，來表示圖。這種表示法一般用于稠密圖。當(dāng)圖不是簡單圖，鄰接矩陣法不能用。在無權(quán)圖中，假設(shè)邊存在，=1；否則=0。無權(quán)圖的例子：在有權(quán)圖中,假設(shè)邊存在,則為它的權(quán)值；否則人為的規(guī)定=∞或-∞。∞是一個足夠大的數(shù)。無向圖中，鄰接矩陣是按矩陣副對角線對稱的。關(guān)聯(lián)矩陣Incidencematri*用二元數(shù)組，來表示無權(quán)有向圖。一般不用這種表示法。假設(shè)邊k與點u關(guān)聯(lián)，假設(shè)k是u的出邊，則=1；假設(shè)k是u的入邊=-1；否則=0。無權(quán)圖的例子：鄰接表Adjacencylist圖的鄰接表是圖的所有節(jié)點的鄰接表的集合；而對每個節(jié)點，它的鄰接表就是它的所有出弧的集合，含有終點，權(quán)值等信息。對于有向圖G=(V,E)，一般用A(v)表示節(jié)點v的鄰接表，即節(jié)點v的所有出弧構(gòu)成的集合或鏈表(實際上只需要列出弧的另一個端點，即弧的尾)。一般圖都適用。鄰接表方法增加或刪除一條弧所需的計算工作量很少。有權(quán)圖的例子：A(1)={2,3}，A(2)={4}，A(3)={2}，A(4)={3,5}，A(5)={3,4}112345283904602403053036470終點權(quán)值指針起點弧表Arclist所謂圖的弧表,也就是圖的弧集合中的所有有序?qū)σ员砀竦姆绞絹肀硎??；”肀硎痉ㄖ苯恿谐鏊谢〉钠瘘c和終點，以及權(quán)值。一般用于稀疏圖。缺點是無法通過一些信息(起點，終點)定位一條邊。用S(i),F(i),W(i)分別表示起點，終點，權(quán)值。有權(quán)圖的例子：起點13455421終點22543343權(quán)值84376069星形表示Star星形表示法就是對弧表的缺點的改良，使之可以通過起點或終點定位邊。由于很多時候，算法只需事先知道起點，通過枚舉邊擴展，而不需要事先知道終點；如圖的遍歷，松弛操作。按定位方式，又分前向星形(forwardsstar)與反向星形(reversestar)。前向星形：通過起點定位邊。反向星形：通過終點定位邊。實際上，反向星形幾乎沒用。故本文只討論前向星形。通常有兩種方法實現(xiàn)這種對弧表改良：邊排序法，鏈表法。邊排序法：把弧表按起點為第一關(guān)鍵字，終點為第二關(guān)鍵字來排序。排序用不用額外空間的快速排序O(mlogm)或用額外空間O(m)的計數(shù)排序O(m)均可。之后用數(shù)組last(u)記錄以結(jié)點u為起點的最后一條邊的編號，并規(guī)定last(0)=0。這樣以結(jié)點u為起點的邊編號就是last(u-1)+1到last(u)。有權(quán)圖的例子：作為起點的點作為起點的點012345最后邊的編號023468編號12345678起點11234455終點23423534權(quán)值89640367鏈表法：給每條邊(u,v)加一個前趨，表示以u為起點的邊鏈表的前一條邊。直觀的講，就是將一樣結(jié)點的邊用鏈表串起來。last(u)存以u為起點的最后一條邊的編號。有權(quán)圖的例子：作為起點的點作為起點的點12345最后邊的編號65278編號012345678起點nil53412145終點nil42524333權(quán)值nil74386906前趨nil00000431星形表示法的優(yōu)點是占用的存貯空間較少。一般圖都適用。邊排序法的優(yōu)點是起點和終點的情況下可以準(zhǔn)確定位邊，容易在起點定位的圍二分查找終點，在反向邊的定位中常用；缺點是代碼麻煩，時間抑或空間上都有額外開銷。鏈表法的優(yōu)點很多，不僅代碼簡單，而且沒有太多的時空開銷，對于反向邊的定位只要多加一個數(shù)據(jù)項紀(jì)錄下反向邊即可；除了終點定位性，幾乎沒缺點。參考文獻：[1]金星，清華大學(xué)數(shù)學(xué)科學(xué)系<<網(wǎng)絡(luò)優(yōu)化>>講義

./~j*ie/courses/netopt[2]汝佳，黃亮，<<算法藝術(shù)與信息學(xué)競賽>>，P60圖的遍歷Travelingingraph深度優(yōu)先搜索Depthfirstsearch(DFS)概念求無向連通圖中的橋Findingbridgesinundirectedgraph在無向連通的條件下，邊是橋的充要條件是：1.橋一定是DFS樹中的邊；2.橋一定不在圈中。圈是由一條后向邊(u,v)與DFS樹中u到v的路徑組成。也就是說u到v的路徑上的邊都不可能是橋，應(yīng)該給以標(biāo)記。記f(*)為*與其子的后向邊所連到的最老祖先(深度最淺)，表示*到f(*)上的邊均不為橋。然而維護f(*)比擬麻煩，其實只要知道f(*)的拓?fù)湫驍?shù)就可以了。所謂拓?fù)湫驍?shù)就是滿足兒子的序數(shù)總比父親大的一個編號方式。這個拓?fù)湫?，常用使用深度d，或者使用時間戳(TimeStamp)DFN〔DFS訪問的次序〕。下面以深度為例：記，在DFS樹中從*開場通過前向弧和后向弧所能到達的最小的d。有以下的動態(tài)規(guī)劃：這里：1.第一次訪問*時，記錄d(*)2.d(y)自己發(fā)出去的后向邊所到達的深度。3.g(c)就是其子中的g最小值。最后，假設(shè)g(*)=d(*)，即(father,*)不在圈中，則(father,*)就是橋。廣度優(yōu)先搜索Breadthfirstsearch(BFS)拓?fù)渑判騎opologicalsort拓?fù)渑判蚴菍τ邢驘o圈圖(DAG)頂點的一種排序，它使得如果存在u,v的有向路徑，則滿足序中u在v前。拓?fù)渑判蚓褪怯梢环N偏序(particalorder)得到一個全序(稱為拓?fù)溆行?topologicalorder))。偏序是滿足自反性，反對稱性，傳遞性的序。拓補排序的思路很簡單，就是每次任意找一個入度為0的點輸出，并把這個點以及與這個點相關(guān)的邊刪除。實際算法中，用一個隊列實現(xiàn)。算法：把所有入度=0的點入隊Q。假設(shè)隊Q非空，則點u出隊，輸出u；否則轉(zhuǎn)4。把所有與點u相關(guān)的邊(u,v)刪除，假設(shè)此過程中有點v的入度變?yōu)?，則把v入隊Q，轉(zhuǎn)2。假設(shè)出隊點數(shù)<N，則有圈；否則輸出結(jié)果。算法復(fù)雜度:O(m)。習(xí)題：MIPT012Correctdictionary設(shè)R為非空集合A上的二元關(guān)系，如果R滿足自反性(對于每一個*∈A，(*,*)∈R)，反對稱性((*,y)∈R∧(y,*)∈R→*=y)和傳遞性((*,y)∈R∧(y,*)∈R→(*,z)∈R)，則稱R為A上的偏序關(guān)系，記作≤。如果(*,y)∈R，則記作*≤y，讀作“*小于等于y〞。存在偏序關(guān)系的集合A稱為偏序集(particalorder)。拓?fù)渑判虻挠嫈?shù)。？？？？？？？？？？？？？？？？？？？？？？？？？？？？？AOV(activityonverte*network)AOE(activityonedgenetwork)，其中頂點表示事件event，權(quán)表示時間。路徑與回路Pathsandcircuits歐拉路徑或回路Eulerianpath對于連通的可重邊的圖G，假設(shè)存在一回路，它通過G的所有邊一次且僅一次，則這回路稱為歐拉路徑或回路。著名的問題：TheK?nigsbergBridges下面討論有向性：無向圖習(xí)題：Ural1124Mosaic有向圖習(xí)題：CEOI2005DepotRearrangement混合圖混合圖是指有的邊是有向的，有的邊是無向的圖。由于無向邊只能經(jīng)過一次，所以不能拆成兩條方向相反的有向邊，只能給無向邊定向，使得定向后的圖滿足“入度等于出度〞。見LRJP324。下面討論在有權(quán)性上的擴展：無權(quán)圖Unweighted有權(quán)圖Weighed—中國郵路問題TheChinesepostproblem這就是一個經(jīng)典的問題中國郵路問題：給出一個連通的無向的可重邊的有權(quán)圖G，求最短的回路，使得每邊至少遍歷1次。由于每邊至少遍歷一次，所以最短路的瓶頸就在于重復(fù)遍歷。由于圖一直保持連通性，所以兩兩奇點之間都存在歐拉路；又兩兩奇點之間的最短路可求；奇點個數(shù)為偶數(shù)。所以問題就等價于找一個奇點構(gòu)成的完全圖G’(V,E)的最小權(quán)匹配(PerfectMatchinginGeneralGraph)。V(G’)為原圖G中的奇點，每條邊為兩奇點對應(yīng)原圖的最短路長度。算法：確定G中的奇點，構(gòu)成G’。確定G’兩兩結(jié)點在G中的最短路作為它們在G’中的邊權(quán)。對G’進展最小權(quán)匹配。最小權(quán)匹配里的各匹配邊所對應(yīng)的路徑在G中被重復(fù)遍歷一次,得到歐拉圖G’’。對G’’找一條歐拉路即可。有向的中國郵路問題，比擬復(fù)雜。HamiltonianCycle哈氏路徑與回路分支限界搜索模擬退火無權(quán)圖Unweighted有權(quán)圖Weighed—旅行商問題Thetravellingsalesmanproblem動態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化Networkoptimization最小生成樹Minimumspanningtrees最小生成樹是指連通圖中所有生成樹中邊權(quán)和最小的一個。即：求G的一棵生成樹T，使得根本算法BasicalgorithmsPrim根本思想：不斷擴展一棵子樹，直到包括原圖的全部頂點，得到最小生成樹T。每次增加一條邊，使得這條邊是由當(dāng)前子樹結(jié)點集及其補集所形成的邊割集的最小邊。令d(v)為v到結(jié)點集S的最小距離。算法：,d()=0(這里是任意一個結(jié)點),假設(shè)，則完畢；否則，轉(zhuǎn)3。找補集中的d最小的節(jié)點，參加。更新與相鄰的結(jié)點的d值，即假設(shè)，則，轉(zhuǎn)2。這里的d可以用優(yōu)先隊列實現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。假設(shè)用FibonacciHeap實現(xiàn)(刪除最小O(logn)，減值O(1))，算法復(fù)雜度：。Kruskal根本思想：就是維護一個生成森林。每次將一條權(quán)最小的邊參加子圖T中，并保證不形成圈。如果當(dāng)前弧參加后不形成圈，則參加這條弧，如果當(dāng)前弧參加后會形成圈，則不參加這條弧，并考慮下一條弧。算法：，將E中的邊按權(quán)從小到大排序，。i=i+1，假設(shè)i>m，完畢，此時G沒有生成樹；否則判斷是否含圈，是則轉(zhuǎn)2，否則轉(zhuǎn)3。。假設(shè)|T|=N，完畢，此時T為G的最小生成樹。別離集合(disjointset)，可用并查集實現(xiàn)。由于排序是的。所以復(fù)雜度為。Sollin〔Boruvka〕根本思想：前面介紹的兩種算法的綜合。每次迭代同時擴展多棵子樹，直到得到最小生成樹T。 算法：對于所有。。假設(shè)|T|=N，完畢，此時T為G的最小生成樹；否則，對于T中所有的子樹集合，計算它的邊割中的最小弧〔有的書稱連接兩個連通分量的最小弧“平安邊〞〕。對T中所有子樹集合及其邊割最小弧，將與q所在的子樹集合合并。。轉(zhuǎn)2。由于每次循環(huán)迭代時，每棵樹都會合并成一棵較大的子樹，因此每次循環(huán)迭代都會使子樹的數(shù)量至少減少一半，或者說第i次迭代每個分量大小至少為。所以，循環(huán)迭代的總次數(shù)為O(logn)。每次循環(huán)迭代所需要的計算時間：對于第2步，每次檢查所有邊O(m)，去更新每個連通分量的最小??；對于第3步，合并個子樹。所以總的復(fù)雜度為。擴展模型E*tendedmodels度限制生成樹Minimumdegree-boundedspanningtrees由于這個問題是NP-Hard的，一般用搜索算法解決。本文就只討論一種特殊多項式情況：單點度限制(onenodedegreebounded)。把度限制的點記為，滿足度限制。一種貪心的思路：在最小生成樹T的根底上，通過添刪邊來改造樹，使之逐漸滿足度限制條件。算法：求圖的最小生成樹T。假設(shè)已滿足度限制，完畢；否則轉(zhuǎn)3。對于刪去后的每一個連通分支(為一棵樹)，求添加邊割中的最小弧，刪除邊割里的最大弧后的生成樹中的邊權(quán)和最小的一個。更新最小生成樹T。轉(zhuǎn)2。第3步，的度少1。習(xí)題：NOI2005小H的聚會k小生成樹Thekminimumspanningtreeproblem(k-MST)生成樹T刪除一條邊f(xié)并參加一條新邊e的操作稱為交換。假設(shè)交換后的圖仍是一顆樹，則此交換稱為可行交換。假設(shè)生成樹T可通過一次交換成為生成樹T’，則稱它們互為鄰樹。對于生成樹集合S，生成樹T，假設(shè)T不在S中，且在S中存在*生成樹是T的鄰樹，稱為T為S的鄰樹。定理：設(shè)為圖的前k小生成樹，則生成圖集合的鄰樹中的邊權(quán)和最小者可作為第k+1小生成樹(可能有邊權(quán)和一樣的情況)。 按這個定理設(shè)計算法，很難得到有滿意的時間復(fù)雜度的算法。下面討論一個特例：次小生成樹(ThesecondMST,2-MST)根本思想：枚舉最小生成樹T的每一個鄰樹，即枚舉被添加與被刪除的邊。由于在樹中添加一條邊()，一定形成了一個環(huán)，環(huán)是由與從u到v的生成樹上的唯一路徑(記為)組成的。所以被刪除的邊一定在上。由于要求最小邊權(quán)和，所以被刪除的邊一定是上最小者，其權(quán)值記為：。算法：求圖的最小生成樹T。次小生成樹T’的權(quán)值的最小值。以每個結(jié)點為根r，DFS遍歷樹。在遍歷過程中求出，用更新次小生成樹的權(quán)值的最小值。輸出。算法復(fù)雜度的瓶頸在第2步，故總算法復(fù)雜度為。習(xí)題：Ural1416Confidential最短路Shortestpaths單源最短路Single-sourceshortestpaths令s為起點，t為終點。單源最短路問題定義為：對于網(wǎng)絡(luò)G=(V,E,W)，尋找s到t的一條簡單路徑，使得路徑上的所有邊權(quán)和最少。令d(v)為s到v的最短路長度上界。單源最短路問題的規(guī)劃模型如下：對于只含正有向圈的連通有向網(wǎng)絡(luò)，從起點s到任一頂點j都存在最短路，它們構(gòu)成以起點s為根的樹形圖〔稱為最短路樹〔TreeofShortestPaths〕〕。當(dāng)*弧(u,v)位于最短路上時，一定有。所以最短路的長度可以由Bellman方程〔最短路方程〕唯一確定：在規(guī)劃模型與最短路方程中都出現(xiàn)了形式的式子，下面引入松弛操作：松弛操作是對于邊(u,v)進展的改良操作：假設(shè)，則改良。直觀的講，就是路徑最后通過(u,v)，使得s到v的距離比原來s到v的方案的距離短。松弛操作是最短路算法求解的根本方式。最短路算法求解過程中的標(biāo)號規(guī)定：對于V中每一個頂點v，設(shè)置一個標(biāo)號：距離標(biāo)號d(v)，記錄的是從起點到該頂點的最短路長度的上界；再設(shè)置一個是前趨pred(v)，記錄的是當(dāng)起點s到該頂點v的一條路長取到該上界時，該條路中頂點v前面的那個直接前趨。算法通過不斷修改這些標(biāo)號，進展迭代計算。當(dāng)算法完畢時，距離標(biāo)號表示的是從起點到該頂點的最短路長度。標(biāo)號設(shè)定算法(Label-Setting)：在通過迭代過程對標(biāo)號進展逐步修正的過程中，每次迭代將一個頂點從臨時標(biāo)號集合中移入永久標(biāo)號集合中。標(biāo)號修正算法(Label-Correcting)：每次迭代時并不一定將任何頂點標(biāo)號從臨時標(biāo)號轉(zhuǎn)變?yōu)橛谰脴?biāo)號，只是對臨時標(biāo)號進展一次修正，所有頂點標(biāo)號仍然都是臨時標(biāo)號；只有在所有迭代終止時，所有頂點標(biāo)號同時轉(zhuǎn)變?yōu)橛谰脴?biāo)號。最長路問題可以轉(zhuǎn)化為最短路問題，把弧上的費用反號即可。根本算法BasicalgorithmsDijkstra采用了標(biāo)號設(shè)定算法(Label-Setting)。在迭代進展計算的過程中，所有頂點實際上被分成了兩類：一類是離起點較近的頂點，它們的距離標(biāo)號表示的是從點s到該頂點的最短路長度，因此其標(biāo)號不會在以后的迭代中再被改變〔稱為永久標(biāo)號〕；一類是離起點較遠的頂點，它們的距離標(biāo)號表示的只是從點到該頂點的最短路長度的上界，因此其標(biāo)號還可能會在以后的迭代中再被改變〔稱為臨時標(biāo)號〕。下文稱永久標(biāo)號為已檢查。算法：1.，，已檢查2.取未檢查的u，即，使得最小。假設(shè)u取不到，即d(u)=∞則完畢；否則標(biāo)記為已檢查，即。3.枚舉所有的u的臨邊，滿足v未檢查，即。松弛，即假設(shè)，則改良，pred(v)=u。轉(zhuǎn)2。這里的d可以用優(yōu)先隊列實現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。假設(shè)用FibonacciHeap實現(xiàn)(刪除最小O(logn)，減值O(1))，則算法復(fù)雜度：。假設(shè)用BinaryHeap則。適用圍：非負(fù)權(quán)圖。Bellman-Ford采用了標(biāo)號修正算法(Label-Correcting)。本質(zhì)就是用迭代法〔動態(tài)規(guī)劃〕解Bellman-Ford方程：表示s到v的且邊數(shù)不超過k條時的最短路路長。下面用歸納法證明：k=1顯然成立。假設(shè)對k成立，下面考慮k+1的情況.從起點s到頂點v且所經(jīng)過的弧數(shù)不超過k+1條時的最短路有兩種可能：含有不超過k條弧，即；含有k+1條弧，即。由于第k+1次迭代過程中，不會影響k次的迭代結(jié)果，d用O(n)的空間即可。算法：，松弛所有邊(u,v)，即假設(shè)，則改良，pred(v)=u。假設(shè)沒有邊被松弛，則算法完畢。假設(shè)2的迭代次數(shù)超過n-1，則有負(fù)權(quán)圈，完畢；否則轉(zhuǎn)2繼續(xù)迭代?？梢宰C明算法一定在n-1步迭代后收斂；否則一定有負(fù)權(quán)圈。所以算法復(fù)雜度為O(nm)。適用圍：一般圖。Shortest

path

faster

algorithm(SPFA)SPFA其實就是Bellman-Ford的一種隊列實現(xiàn)，減少了冗余，即松馳的邊至少不會以一個d為∞的點為起點。算法：隊列Q={s}，，取出隊頭u，枚舉所有的u的臨邊。假設(shè)，則改良，pred(v)=u，由于減少了，v可能在以后改良其他的點，所以假設(shè)v不在Q中，則將v入隊。一直迭代2，直到隊列Q為空(正常完畢)，或有的點的入隊次數(shù)>=n〔含有負(fù)圈〕。由于點可能屢次入隊，但隊列中同時不會超過n個點。所以用一個長度為n的循環(huán)隊列來實現(xiàn)這個隊。SPFA在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改良過其它的點之后，過了一段時間可能本身被改良，于是再次用來改良其它的點，這樣反復(fù)迭代下去。設(shè)一個點用來作為迭代點對其它點進展改良的平均次數(shù)為k，有方法證明對于通常的〔不含負(fù)圈，較稀疏〕情況，k在2左右。算法復(fù)雜度理論上同Bellman-Ford，O(nm)，但實際上卻是O(km)。一般用于找負(fù)圈(效率高于Bellman-Ford)，稀疏圖的最短路。習(xí)題：Ural1254DieHard〔可斜走的網(wǎng)格最短路〕。應(yīng)用Applications差分約束系統(tǒng)Systemofdifferenceconstraints差分約束系統(tǒng)：求解n個未知數(shù)，滿足m個不等式：假設(shè)描述為線形規(guī)劃模型：。矩陣A每行含一個1一個-1，其他都是0。如線形規(guī)劃模型等價于注意到單源最短路模型中的。，即。很像差分約束系統(tǒng)模型。于是可以構(gòu)造一個有向網(wǎng)絡(luò)G=(V,E,W)，稱為約束圖(constraintsgraph)。。W：， 對進展Bellman-Ford算法，可以得到，令，即為所求，其中C是任意一個常數(shù)，均滿足原不等式組。當(dāng)有為負(fù)數(shù)且題目要求非負(fù)時，常常令C為最小的的相反數(shù)。習(xí)題：NOI199901串有向無環(huán)圖上的最短路ShortestpathsinDAG算法：1.，。對有向無環(huán)圖G，拓?fù)渑判騉(m)。2.按拓?fù)湫蛎杜eu。假設(shè)枚舉完，則完畢。3.枚舉所有u的臨邊(u,v)，對(u,v)進展松弛操作，即假設(shè)，則改良，pred(v)=u。轉(zhuǎn)2。復(fù)雜度：所有頂點對間最短路All-pairsshortestpaths根本算法BasicalgorithmsFloyd-Warshall本質(zhì)就是用迭代法〔動態(tài)規(guī)劃〕：表示u到v的不經(jīng)過k,k+1,…,n結(jié)點(除u,v外)時，從u,v的最短路長。下面用歸納法證明：k=1顯然成立。假設(shè)對k成立,下面考慮k+1的情況；從u到v且不通過k+1,…,n節(jié)點的最短路有兩種可能：(1)不經(jīng)過k節(jié)點，即為；(2)經(jīng)過k節(jié)點，即為。由于第k+1次迭代過程中，不會影響k次的迭代結(jié)果，d用的空間即可。二維數(shù)組，記錄u到v，最后經(jīng)過哪個k的迭代。算法：k=1，對于所有u,v，k=k+1，對于所有u,v，假設(shè)，則，。假設(shè)發(fā)現(xiàn)*個節(jié)點u使得,則說明網(wǎng)絡(luò)本來就含有負(fù)有向圈，完畢。假設(shè)k=n，完畢；否則轉(zhuǎn)2。算法復(fù)雜度：Johnson本算法適用于稀疏圖。它是Dijkstra和Bellman-Ford算法的綜合應(yīng)用。本算法用了權(quán)值改造(reweighting)技術(shù)。假設(shè)圖的權(quán)值非負(fù)，則對于每個結(jié)點用一次Dijkstra算法，就可以求出所有頂點對間最短路。假設(shè)圖中有負(fù)權(quán)，但沒有負(fù)圈，則可以把權(quán)值W改造成W’，W’非負(fù)，使得能夠使用Dijkstra算法。算法：給圖G，加一個新結(jié)點。對用Bellman-Ford，假設(shè)有負(fù)圈，則完畢；否則可以得到，即到的最短路長。O(nm)對于所有邊，權(quán)值改造，即令。O(m)對于每個結(jié)點，用一次以FibonacciHeap為優(yōu)先隊列的Dijkstra算法，可求出與其他頂點的最短路。O(nlogn+m)*O(n) 算法總復(fù)雜度。權(quán)值改造滿足兩個原則：(1)W’非負(fù)；(2)對于任意頂點u,v，p是在W上的u到v的最短路當(dāng)且僅當(dāng)p是在W’上的u到v的最短路。下證，滿足以上兩個原則：(1)由于h是v0到v的最短路長，，所以。(2)令路徑，則只與以及首尾的標(biāo)號h有關(guān)，不影響的決策。所以是最短路長當(dāng)且僅當(dāng)是最短路長，且不影響最短路p。參考文獻：[1]25.3Johnson'salgorithmforsparsegraphs，IntroductiontoAlgorithms，MITPress網(wǎng)絡(luò)流Flownetwork最大流Ma*imumflow在有向無權(quán)圖G(V,E,C)中，其中C為每條邊的容量(capability)，再給每條邊賦予一個流值(flow)，并規(guī)定源s和匯t。最大流問題的數(shù)學(xué)模型描述如下：其中(2)，為容量限制條件：邊的流量不超過邊上的容量。其中(3)規(guī)定反向邊的流量為正向邊的流量的相反數(shù)。其中(4)可以改寫成：稱為流量平衡條件。它表示除了源s和匯t外的結(jié)點流入等于流出。 其中(1)表示要求從源流出的流量要最大。最小切割最大流定理：s-t最大流流值=s-t最小切割容量。習(xí)題：Ural1277CopsandThieves(最小切割最大流)根本算法BasicalgorithmsFord-Fulkersonmethod增廣軌定理：Edmonds-KarpalgorithmMinimumlengthpathMa*imumcapabilitypath預(yù)流推進算法PreflowpushmethodPush-relabelRelabel-to-frontDinicmethodDINIC&MPM===========我們能夠做的更快一些么？？前面的算法需要O(mn)次迭代，而每次需要O(m)的時間，因此總共需要O(m^2n)。下面我們試著降到O(n^3)。想法：假設(shè)d=d(t)，我們將試著一次性的找到很多到t的長度為d的路徑。為了做到這個，我們看前面得到的層次圖〔我們不考慮所有的后向邊以及兩個端點在同一層的邊〕。我們現(xiàn)在嘗試著在這個圖中執(zhí)行盡量多的流量，然后我們才重新計算剩余圖。術(shù)語：一個充滿了這個剩余圖的流稱之為塊流。因此我們的目標(biāo)就是在這個剩余圖中在O(n^2)的時間找到一個塊流。我們定義c(v)=頂點v的容量：也就c_in[v],c_out[v]的最小值，這里c_in[v]是所有v的入邊的容量的和，而c_out[v]類似。算法：-找到具有最小容量c的頂點v。如果他的容量是0，ohyeah--我們就可以把他和與他相關(guān)聯(lián)的邊都刪除掉，并且更新他的鄰居的容量值。-如果c不為0，則我們將從s運送c個單位流到v，然后從v運送到t。你可能覺得這不又回到原來的問題了么？但是，這里有點值得注意：因為v具有最小的容量，我們可以使用任何的貪心策略來從其他頂點流入流出c的流量而不會被堵住。這一點意味著，我們可以在O(m)的時間充滿v。〔*daizinnd，想了好久才明白具體怎么做的首先，為了從s運送c到v，我們從v開場向上考慮，把任意一條從v向上的邊給充滿，如果不能夠充滿，說明還沒有安置的流量就這些了，全部扔在這條邊上就是了，為什么一定能夠找到這樣一條邊呢，：〕然后假設(shè)我們剛剛填充的這條邊是u->v，則我們就有一些流量需要在u繼續(xù)往上進展處理，使用剛剛在v點同樣的方法，直到一直處理到了s，一路上肯定是不會出現(xiàn)什么障礙的。然后我們將c從v運送到t，我們在構(gòu)造這個層次圖的時候很容易就可以保證所有從s出發(fā)的路徑都會在t終結(jié)，這樣就好辦了，使用上面同樣的方法，只是處理的方向是從v到t了。這樣，我們剛剛處理的過程就容易得到下面的下面所謂的性質(zhì)了。*〕上面的算法給了我們一個可以在O(mn)的時間充滿這個層次圖的算法，下面進一步分析。為了得到我們需要的界，我們需要這樣一個性質(zhì)：當(dāng)我們在上面的對每個新的頂點v執(zhí)行算法的步驟中，保證對每條邊我們只檢查一次，對其做完所有需要的操作之后才會去做下一條邊。這點意味著，我們可以把運行時間分成兩個局部來考慮：a〕花在被充滿的邊上的時間b〕花在沒有被充滿的邊上的時間。對于a〕，因為我們每次充滿一條邊就會把它從圖中刪除，所以a〕的總時間是O(m)。因此我們的時間主要由b〕來決定，而b〕對應(yīng)的邊在對每個新的頂點v的執(zhí)行過程中至多出現(xiàn)O(n)次，因此總的時間是O(n^2)。而我們可以在O(m)的時間重新計算新的層次圖，所以我們就可以在O(nm+nn^2)時間完成整個算法，也就是O(n^3)。擴展模型E*tendedmodels有上下界的流問題問題模型：給定一個加權(quán)的有向圖，滿足：(1)容量限制條件：(2)流量平衡條件：(2)中的，即除了源匯外，所有點都滿足流量平衡條件，則稱G為有源匯網(wǎng)絡(luò)；否則，即不存在源匯，所有點都滿足流量平衡條件，則稱G為無源匯網(wǎng)絡(luò)。將這類問題由易到難一一解決：問題[1]求無源匯的網(wǎng)絡(luò)有上下界的可行流112st2,63,73,4+∞由于下界是一條弧上的流必需要滿足確實定值。下面引入必要弧的概念：必要弧是一定流要滿的弧。必要弧的構(gòu)造，將容量下界的限制別離開了，從而構(gòu)造了一個沒有下界的網(wǎng)絡(luò)G’：將原弧(u,v)別離出一條必要?。骸！布t色表示〕原?。?。++∞12st441233 由于必要弧的有一定要滿的限制，將必要弧“拉〞出來集中考慮：++∞12st441233 添加附加源*,附加匯y。想像一條不限上界的(y,*)，用必要弧將它們“串〞起來，即對于有向必要弧(u,v)，添加(u,y)，(*,v)，容量為必要弧容量。這樣就建立了一個等價的網(wǎng)絡(luò)。++∞12st441233y*233一個無源匯網(wǎng)絡(luò)的可行流的方案一定是必要弧是滿的。假設(shè)去掉(y,*)后，附加源*到附加匯y的最大流，能使得*的出弧或者y的入弧都滿，充要于原圖有可行流。++∞12st441233y*233算法：按上述方法構(gòu)造新網(wǎng)絡(luò)(別離必要弧，附加源匯)求附加源*到附加匯y的最大流假設(shè)*的出弧或y的入弧都滿，則有解，將必要弧合并回原圖；否則，無解。問題[2]求有源匯的網(wǎng)絡(luò)有上下界的可行流112st2,63,73,4參加邊(t,s)，下界為0(保證不會連上附加源匯*,y)，不限上界，將問題[2]轉(zhuǎn)化為問題[1]來求解。112stT2,63,73,4+∞問題[3]求有源匯的網(wǎng)絡(luò)有上下界的最大流算法：先轉(zhuǎn)化為問題[2]來求解一個可行流。假設(shè)可