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

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

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

path

faster

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