圖論總結(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中國郵路問題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所有頂點對間最短路All-pairsshortestpaths基本算法BasicalgorithmsFloyd-WarshallJohnson網(wǎng)絡(luò)流Flownetwork最大流MaximumflowFord-FulkersonmethodEdmonds-KarpalgorithmMinimumlengthpathMaximumcapabilitypath預(yù)流推

5、進(jìn)算法PreflowpushmethodPush-relabelRelabel-to-front基本算法BasicalgorithmsDinicmethod擴(kuò)展模型Extendedmodels.2.1.有上下界的流問題最小費用流Minimumcostflow找最小費用路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é)點(node)或頂點(vertex)集。E為V中結(jié)點之間的邊的集合。點對(u,v)稱為邊(edge)或稱弧(arc),其中u,veV，稱u,v是相鄰的(adjacent)，稱u,v與邊(u,v)相關(guān)聯(lián)(incident)或相鄰。若邊的點對(u,v)有序則稱為有向(directed)邊，其中

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

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

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

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

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

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

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

14、的情況)。按這個定理設(shè)計算法，很難得到有滿意的時間復(fù)雜度的算法。下面討論一個特例：次小生成樹(ThesecondMST,2-MST)基本思想：枚舉最小生成樹T的每一個鄰樹，即枚舉被添加與被刪除的邊。由于在樹中添加一條邊(u,v)(u,v)電T)，一定形成了一個環(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。以每個結(jié)點為根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為起點，t為終點。單源最短路問題定義為：對于網(wǎng)絡(luò)G=(V,E,W)，尋找s到t的一條簡單路徑，使得路徑上的所有邊權(quán)和最少。令d(v)為s到v的最短路長度上界。單源最短路問題的規(guī)劃模型如下：mind(t)s.t.d(v)d(u)+w(u,v)(u,v)eEd(s

16、)=0對于只含正有向圈的連通有向網(wǎng)絡(luò)，從起點s到任一頂點j都存在最短路，它們構(gòu)成以起點s為根的樹形圖(稱為最短路樹(TreeofShortestPaths)。當(dāng)某弧(u,v)位于最短路上時,一定有d(v)-d(u)=w(u,v)。所以最短路的長度可以由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)號規(guī)

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

18、號仍然都是臨時標(biāo)號；只有在所有迭代終止時，所有頂點標(biāo)號同時轉(zhuǎn)變?yōu)橛谰脴?biāo)號。最長路問題可以轉(zhuǎn)化為最短路問題，把弧上的費用反號即可。基本算法BasicalgorithmsDijkstra采用了標(biāo)號設(shè)定算法(Label-Setting)。在迭代進(jìn)行計算的過程中，所有頂點實際上被分成了兩類：一類是離起點較近的頂點，它們的距離標(biāo)號表示的是從點s到該頂點的最短路長度,因此其標(biāo)號不會在以后的迭代中再被改變(稱為永久標(biāo)號)；一類是離起點較遠(yuǎn)的頂點，它們的距離標(biāo)號表示的只是從點到該頂點的最短路長度的上界，因此其標(biāo)號還可能會在以后的迭代中再被改變(稱為臨時標(biāo)號)。下文稱永久標(biā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)先隊列實現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。假設(shè)用FibonacciHeap實現(xiàn)(刪除最小O(logn)，減值O(l),則算法復(fù)雜度：O(nlogn+m)。若用BinaryHeap則O(n+m)logn)。適用范圍：非負(fù)權(quán)圖。Be

20、llman-Ford采用了標(biāo)號修正算法(Label-Correcting)。本質(zhì)就是用迭代法(動態(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條時的最短路路長。下面用歸納法證明：k=1顯然成立。假設(shè)對k成立，下面考慮k+1的情況.從起點s到頂點V且所經(jīng)過的弧數(shù)不超過k+1條時的最短路有兩種可能：含有不超過k條弧，即d(k)(v)；含有k+1條弧，即mind(k)(u)+w(u,v)。u工v由

21、于第k+1次迭代過程中，不會影響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ù)迭代。可以證明算法一定在n-1步迭代后收斂；否則一定有負(fù)權(quán)圈。所以算法復(fù)雜度為O(nm)。適用范圍：一般圖。.1.2.1.Shortestpathfasteralgorithm(SPFA)SPFA其實就是Bellman-Ford的一種隊列實現(xiàn)，減少了冗余，即松馳的邊至少不會以一個d

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

23、也就是一個點改進(jìn)過其它的點之后，過了一段時間可能本身被改進(jìn)，于是再次用來改進(jìn)其它的點，這樣反復(fù)迭代下去。設(shè)一個點用來作為迭代點對其它點進(jìn)行改進(jìn)的平均次數(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ù)x，滿足m個不等式：ix一xb,1i,jn,1kmj

24、ik若描述為線形規(guī)劃模型：AxB。mxn矩陣A每行含一個1一個-1，其他都是0。如線形規(guī)劃模型(10一10、(-2010-1(x)14100-11x5201一10 x-3-10013lxj421一100丿i3丿等價于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)造一個有向網(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)所有頂點對間最短路All-pairsshortestpaths基本算法BasicalgorithmsFloyd-Warshall本質(zhì)就是用迭代法(動態(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é)點(除u,v外)時，從u

26、,v的最短路長。下面用歸納法證明：k=1顯然成立。假設(shè)對k成立，下面考慮k+1的情況；從u到v且不通過k+1,n節(jié)點的最短路有兩種可能：(1)不經(jīng)過k節(jié)點,即為d(k)(u,v)；(2)經(jīng)過k節(jié)點,即為d(k)(u,k)+d(k)(k,v)。由于第k+1次迭代過程中，不會影響k次的迭代結(jié)果，d用O(n2)的空間即可。二維數(shù)組p(u,v),記錄u到V,最后經(jīng)過哪個k的迭代。算法：k=1，對于所有u,v，d(u,v)=w(u,v),p(u,v)=vk=k+1，對于所有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)某個節(jié)點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有關(guān)，不影響w(p)的決策。所以w(p)是最短路長當(dāng)且僅當(dāng)W(p)是最短路長，且不影響最短路p。參考文獻(xiàn)：125.3Johnsonsalgorithmforsparsegraphs，IntroductiontoAlgorithms，MITPress網(wǎng)絡(luò)流Flownetwork最大流Maximumflow在有向無權(quán)圖

28、G(V,E,C)中，其中C為每條邊的容量(capability)c(u,v),再給每條邊賦予個流值(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點同樣的辦法，直到一直處理到了S，一路上肯定是不會出現(xiàn)什么障礙的。然后我們將c從V運送到t,我們在構(gòu)造這個層次圖的時候很容易就可以保證所有從S出發(fā)的路徑都會在t終結(jié)，這樣就好辦了，使用上面同樣的

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