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

1、.1.圖論 Graph Theory1.1.定義與術(shù)語 Definition and Glossary1.1.1.圖與網(wǎng)絡(luò) Graph and Network1.1.2.圖的術(shù)語 Glossary of Graph1.1.3.路徑與回路 Path and Cycle1.1.4.連通性 Connectivity1.1.5.圖論中特殊的集合 Sets in graph1.1.6.匹配 Matching1.1.7.樹 Tree1.1.8.組合優(yōu)化 Combinatorial optimization1.2.圖的表示 Expressions of graph1.2.1.鄰接矩陣 Adjacency m

2、atrix1.2.2.關(guān)聯(lián)矩陣 Incidence matrix1.2.3.鄰接表 Adjacency list1.2.4.弧表 Arc list1.2.5.星形表示 Star1.3.圖的遍歷 Traveling in graph1.3.1.深度優(yōu)先搜索 Depth first search (DFS)1.3.1.1.概念1.3.1.2.求無向連通圖中的橋 Finding bridges in undirected graph1.3.2.廣度優(yōu)先搜索 Breadth first search (BFS)1.4.拓?fù)渑判?Topological sort1.5.路徑與回路 Paths and c

3、ircuits1.5.1.歐拉路徑或回路 Eulerian path1.5.1.1.無向圖1.5.1.2.有向圖1.5.1.3.混合圖1.5.1.4.無權(quán)圖 Unweighted1.5.1.5.有權(quán)圖 Weighed 中國郵路問題The Chinese post problem1.5.2.Hamiltonian Cycle 哈氏路徑與回路1.5.2.1.無權(quán)圖 Unweighted1.5.2.2.有權(quán)圖 Weighed 旅行商問題The travelling salesman problem1.6.網(wǎng)絡(luò)優(yōu)化 Network optimization1.6.1.最小生成樹 Minimum spa

4、nning trees1.6.1.1.基本算法 Basic algorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3.Sollin（Boruvka）1.6.1.2.擴(kuò)展模型 Extended models1.6.1.2.1.度限制生成樹 Minimum degree-bounded spanning trees1.6.1.2.2.k小生成樹 The k minimum spanning tree problem(k-MST)1.6.2.最短路Shortest paths1.6.2.1.單源最短路 Single-source shortest path

5、s1.6.2.1.1.基本算法 Basic algorithms1.6.2.1.1.1.Dijkstra1.6.2.1.1.2.Bellman-Ford1.6.2.1.1.2.1.Shortestpathfasteralgorithm(SPFA)1.6.2.1.2.應(yīng)用Applications1.6.2.1.2.1.差分約束系統(tǒng) System of difference constraints1.6.2.1.2.2.有向無環(huán)圖上的最短路 Shortest paths in DAG1.6.2.2.所有頂點(diǎn)對間最短路 All-pairs shortest paths1.6.2.2.1.基本算法 B

6、asic algorithms1.6.2.2.1.1.Floyd-Warshall1.6.2.2.1.2.Johnson1.6.3.網(wǎng)絡(luò)流 Flow network1.6.3.1.最大流 Maximum flow1.6.3.1.1.基本算法 Basic algorithms1.6.3.1.1.1.Ford-Fulkerson method1.6.3.1.1.1.1.Edmonds-Karp algorithm1.6.3.1.1.1.1.1.Minimum length path1.6.3.1.1.1.1.2.Maximum capability path1.6.3.1.1.2.預(yù)流推進(jìn)算法 P

7、reflow push method1.6.3.1.1.2.1.Push-relabel1.6.3.1.1.2.2.Relabel-to-front1.6.3.1.1.3.Dinic method1.6.3.1.2.擴(kuò)展模型 Extended models1.6.3.1.2.1.有上下界的流問題1.6.3.2.最小費(fèi)用流 Minimum cost flow1.6.3.2.1.找最小費(fèi)用路 Finding minimum cost path1.6.3.2.2.找負(fù)權(quán)圈 Finding negative circle1.6.3.2.3.網(wǎng)絡(luò)單純形 Network simplex algorithm

8、1.6.4.匹配 Matching1.6.4.1.二分圖 Bipartite Graph1.6.4.1.1.無權(quán)圖-匈牙利算法 Unweighted - Hopcroft and Karp algorithm1.6.4.1.2.帶權(quán)圖-KM算法 Weighted Kuhn-Munkres(KM) algorithm1.6.4.2.一般圖General Graph1.6.4.2.1.無權(quán)圖-帶花樹算法 Unweighted - Blossom (Edmonds)1. 圖論 Graph Theory1.1. 定義與術(shù)語 Definition and Glossary1.1.1. 圖與網(wǎng)絡(luò) Grap

9、h and Network二元組稱為圖(graph)。為結(jié)點(diǎn)(node)或頂點(diǎn)(vertex)集。為中結(jié)點(diǎn)之間的邊的集合。點(diǎn)對稱為邊(edge)或稱弧(arc)，其中，稱是相鄰的(adjacent)，稱u,v與邊相關(guān)聯(lián)(incident)或相鄰。若邊的點(diǎn)對有序則稱為有向(directed)邊，其中u稱為頭(head)，v稱為尾(tail)。所形成的圖稱有向圖(directed graph)。為對于u來說是出邊(outgoing arc)；對于v來說是入邊(incoming arc)。反之，若邊的點(diǎn)對無序則稱為無向(undirected)邊，所形成的圖稱無向圖(undirected graph)

10、。若圖的邊有一個(gè)權(quán)值(weight)，則稱為賦權(quán)邊，所形成的圖稱賦權(quán)圖(weighted graph)或網(wǎng)絡(luò)(network)。用三元組G(V,E,W)表示網(wǎng)絡(luò)。其中W表示權(quán)集，它的元素與邊集E一一對應(yīng)。滿足的圖，稱為稀疏(sparse)圖；反之，稱為稠密(dense)圖。1.1.2. 圖的術(shù)語 Glossary of Graph階(order)：圖G中頂點(diǎn)集V的大小稱作圖G的階。環(huán)(loop)：若一條邊的兩個(gè)頂點(diǎn)為同一頂點(diǎn)，則此邊稱作環(huán)。簡單圖(simple graph)：沒有環(huán)、且沒有多重弧的圖稱作簡單圖。定向圖：對無向圖G的每條無向邊指定一個(gè)方向得到的有向圖。底圖：把一個(gè)有向圖的每一條有

11、向邊的方向都去掉得到的無向圖。逆圖：把一個(gè)有向圖的每條邊都反向由此得到的有向圖。競賽圖(tournament)：有向圖的底圖是無向完全圖，則此有向圖是競賽圖。鄰域(neighborhood)：在圖中與u相鄰的點(diǎn)的集合，稱為u的鄰域，記為。度：度(degree)：一個(gè)頂點(diǎn)的度是指與該邊相關(guān)聯(lián)的邊的條數(shù)，頂點(diǎn)v的度記作deg(v)。握手定理：無向圖：；有向圖：。入度(indegree)：在有向圖中，一個(gè)頂點(diǎn)v的入度是指與該邊相關(guān)聯(lián)的入邊(即邊的尾是v)的條數(shù)，記作。出度(outdegree)：在有向圖中，一個(gè)頂點(diǎn)的出度是指與該邊相關(guān)聯(lián)的出邊(即邊的頭是v)的條數(shù)，記作。孤立點(diǎn)(isolated v

12、ertex)：度為0的點(diǎn)。葉(leaf)：度為1的點(diǎn)。源(source)：有向圖中，=0 的點(diǎn)。匯(sink)：有向圖中，=0的點(diǎn)。奇點(diǎn)(odd vertex)：度為奇數(shù)的點(diǎn)。偶點(diǎn)(even vertex)：度為偶數(shù)的點(diǎn)。子圖：子圖(sub-graph)：G稱作圖G的子圖如果以及。生成子圖(spanning sub-graph)：即包含G 的所有頂點(diǎn)的連通子圖，即滿足條件的G的子圖G。生成樹(spanning tree)：設(shè)T是圖G的一個(gè)子圖，如果T是一棵樹，且，則稱T是G的一個(gè)生成樹。即G的生成子圖，且子圖為樹。點(diǎn)導(dǎo)出子圖(induced subgraph)：設(shè)，以為頂點(diǎn)集，以兩端點(diǎn)均在中的

13、邊的全體為邊集所組成的子圖，稱為G的由頂點(diǎn)集導(dǎo)出的子圖，簡稱為G的點(diǎn)導(dǎo)出子圖，記為。邊導(dǎo)出子圖(edge-induced subgraph)：設(shè)，以為頂點(diǎn)集，以兩端點(diǎn)均在中的邊的全體為邊集所組成的子圖，稱為G的由邊集導(dǎo)出的子圖，簡稱為G的邊導(dǎo)出子圖，記為。圖的補(bǔ)圖(complement)：設(shè)G是一個(gè)圖，以為頂點(diǎn)集，以為邊集的圖稱為G的補(bǔ)圖，記為。點(diǎn)集的補(bǔ)集：記 為點(diǎn)集的補(bǔ)集。特殊的圖：零圖(null graph)：，即只有孤立點(diǎn)的圖。n階零圖記為。平凡圖(trivial graph)：一階零圖?？請D(empty graph)：的圖。有向無環(huán)圖(directed acyclic graph(DA

14、G)：有向的無環(huán)的圖。完全圖(complete graph)：完全圖是指每一對不同頂點(diǎn)間都有邊相連的的無向圖，n階完全圖常記作。二分圖（bipartite graph）：若圖G的頂點(diǎn)集可劃分為兩個(gè)非空子集X和Y，即且，且每一條邊都有一個(gè)頂點(diǎn)在X中，而另一個(gè)頂點(diǎn)在Y中，那么這樣的圖稱作二分圖。完全二分圖(complete bipartite graph)：二分圖G中若任意兩個(gè)X和Y中的頂點(diǎn)都有邊相連，則這樣的圖稱作完全二分圖。若，則完全二分圖G記作。正則圖(regular graph)：如果圖中所有頂點(diǎn)的度皆相等，則此圖稱為正則圖。1.1.3. 路徑與回路 Path and Cycle途徑(wa

15、lk)：圖G中一個(gè)點(diǎn)邊交替出現(xiàn)的序列，滿足，。跡(trail)：邊不重復(fù)的途徑。路(path)：頂點(diǎn)不重復(fù)的跡。簡單圖中的路可以完全用頂點(diǎn)來表示，。若，稱閉的(closed)；反之，稱為開的(open)。閉途徑(closed walk)：起點(diǎn)和終點(diǎn)相同的途徑。閉跡(closed trail)：起點(diǎn)和終點(diǎn)相同的跡，也稱為回路(circuit)。圈(cycle)：起點(diǎn)和終點(diǎn)相同的路。途徑（閉途徑）、跡（閉跡）、路（圈）上所含的邊的個(gè)數(shù)稱為它的長度(length)。簡單圖G中長度為奇數(shù)和偶數(shù)的圈分別稱為奇圈(odd cycle)和偶圈(even cycle)。對任意，從x到y(tǒng)的具有最小長度的路稱為x

16、到y(tǒng)的最短路(shortest path)，其長度稱為x到y(tǒng)的距離(distance)，記為。圖G的直徑(diameter)：。簡單圖G中最短圈的長度稱為圖G的圍長(girth)，最長圈的長度稱為圖G的周長(perimeter)。1.1.4. 連通性 Connectivity連通(connected)：在圖G中，兩個(gè)頂點(diǎn)間，至少存在一條路徑，稱兩個(gè)頂點(diǎn)連通的(connected)；反之，稱非連通(unconnected)。強(qiáng)連通(strongly connected)：在有向圖G中，兩個(gè)頂點(diǎn)間，至少存在一條路徑，稱兩個(gè)頂點(diǎn)強(qiáng)連通。弱連通(weakly connected)：在有向圖G中，兩個(gè)頂

17、點(diǎn)間，若不考慮G中邊的方向的圖才連通的，稱原有向圖為弱連通。連通圖(connected graph)：圖G中任二頂點(diǎn)都連通。連通分量或連通分支(connected branch, component)：非連通無向圖的極大連通子圖(maximally connected sub-graph)。具體說，若圖G的頂點(diǎn)集V(G)可劃分為若干非空子集，使得兩頂點(diǎn)屬于同一子集當(dāng)且僅當(dāng)它們在G中連通，則稱每個(gè)子圖為圖G的一個(gè)連通分支（）。圖G的連通分支是G的一個(gè)極大連通子圖。圖G連通當(dāng)且僅當(dāng)。強(qiáng)連通分量(strongly connected branch)：非強(qiáng)連通圖有向圖的極大強(qiáng)連通子圖。割(cut)：點(diǎn)

18、割集(vertex cut)：點(diǎn)集，若G刪除了后不連通，但刪除了的任意真子集后G仍然連通。則稱點(diǎn)割集。若某一結(jié)點(diǎn)就構(gòu)成就了點(diǎn)割集，則稱此結(jié)點(diǎn)割點(diǎn)(cut vertex)。點(diǎn)數(shù)最少的點(diǎn)割集稱為點(diǎn)連通度k(G)。邊割集(edge cut set)：邊集，若G刪除了后不連通，但刪除了的任意真子集后G仍然連通。則稱點(diǎn)割集。若某一邊就構(gòu)成就了邊割集，則稱此結(jié)點(diǎn)割邊(cut edge)或橋(bridge)。邊數(shù)最少的邊割集稱為邊連通度k(G)。記號表示一端在S中另一端在中的所有邊的集合。塊(block)是指沒有割點(diǎn)的極大連通子圖。1.1.5. 圖論中特殊的集合 Sets in graph點(diǎn)覆蓋(集)(ve

19、rtex covering (set)：，滿足對于，有，關(guān)聯(lián)。即一個(gè)點(diǎn)集，使得所有邊至少有一個(gè)端點(diǎn)在集合里。或者說是“點(diǎn)” 覆蓋了所有“邊”。極小點(diǎn)覆蓋(minimal vertex covering)：本身為點(diǎn)覆蓋，其真子集都不是。最小點(diǎn)覆蓋(minimum vertex covering)：點(diǎn)最少的點(diǎn)覆蓋。點(diǎn)覆蓋數(shù)(vertex covering number)：最小點(diǎn)覆蓋的點(diǎn)數(shù)，記為一般說覆蓋集就是指點(diǎn)覆蓋集。邊覆蓋(集)(edge covering (set)：，滿足對于，有，關(guān)聯(lián)。即一個(gè)邊集，使得所有點(diǎn)都與集合里的邊鄰接。或者說是“邊” 覆蓋了所有“點(diǎn)”。 極小邊覆蓋(minimal

20、 edge covering)：本身是邊覆蓋，其真子集都不是。最小邊覆蓋(minimum edge covering)：邊最少的邊覆蓋。邊覆蓋數(shù)(edge covering number)：最小邊覆蓋的邊數(shù)，記為。獨(dú)立集(independent set)：，滿足對于，有。即一個(gè)點(diǎn)集，集合中任兩個(gè)結(jié)點(diǎn)不相鄰，則稱為獨(dú)立集?；蛘哒f是導(dǎo)出的子圖是零圖（沒有邊）的點(diǎn)集。極大獨(dú)立集(maximal independent set)：本身為獨(dú)立集，再加入任何點(diǎn)都不是。最大獨(dú)立集(maximum independent set)：點(diǎn)最多的獨(dú)立集。獨(dú)立數(shù)(independent number)：最大獨(dú)立集的點(diǎn)

21、數(shù)，記為。團(tuán)(clique)：，滿足對于，有。即一個(gè)點(diǎn)集，集合中任兩個(gè)結(jié)點(diǎn)相鄰?；蛘哒f是導(dǎo)出的子圖是完全圖的點(diǎn)集。極大團(tuán)(maximal clique)：本身為團(tuán)，再加入任何點(diǎn)都不是。最大團(tuán)(maximum clique)：點(diǎn)最多的團(tuán)。團(tuán)數(shù)(clique number)：最大團(tuán)的點(diǎn)數(shù)，記為。邊獨(dú)立集(edge independent set)：，滿足對于，有不鄰接。即一個(gè)邊集，滿足邊集中的任兩邊不鄰接。極大邊獨(dú)立集(maximal edge independent set)：本身為邊獨(dú)立集，再加入任何邊都不是。最大邊獨(dú)立集(maximum edge independent set)：邊最多的邊

22、獨(dú)立集。邊獨(dú)立數(shù)(edge independent number)：最大邊獨(dú)立集的邊數(shù)，記為。邊獨(dú)立集又稱匹配(matching)，相應(yīng)的有極大匹配(maximal matching)，最大匹配(maximum matching)，匹配數(shù)(matching number)。支配集(dominating set)：，滿足對于，有，。即一個(gè)點(diǎn)集，使得所有其他點(diǎn)至少有一個(gè)相鄰點(diǎn)在集合里。或者說是一部分的“點(diǎn)”支配了所有“點(diǎn)”。 極小支配集(minimal dominating set)：本身為支配集，其真子集都不是。最小支配集(minimum dominating set)：點(diǎn)最少的支配集。支配數(shù)(

23、dominating number)：最小支配集的點(diǎn)數(shù)，記為。邊支配集(edge dominating set)：，滿足對于，有，鄰接。即一個(gè)邊集，使得所有邊至少有一條鄰接邊在集合里?；蛘哒f是一部分的“邊”支配了所有“邊”。極小邊支配集(minimal edge dominating set)：本身是邊支配集，其真子集都不是。最小邊支配集(minimum edge dominating set)：邊最少的邊支配集。邊支配數(shù)(edgedominating number)：最小邊支配集的邊數(shù)，記為。 定理：若G中無孤立點(diǎn)，D為支配集，則D=V(G)-D也是一個(gè)支配集。定理：一個(gè)獨(dú)立集是極大獨(dú)立集，

24、當(dāng)且僅當(dāng)它是支配集。關(guān)系：定理：無向圖G無孤立點(diǎn)，是極小支配集，則存在是極小支配集，且。定理：無向圖G無孤立點(diǎn)，是極大獨(dú)立集，則是極小支配集。逆命題不成立。定理：連通圖中，是點(diǎn)覆蓋，則是支配集。極小點(diǎn)覆蓋不一定是極小支配集。支配集不一定是點(diǎn)覆蓋。定理：無向圖G無孤立點(diǎn)，是(極，最小)點(diǎn)覆蓋，充要于是(極，最大)獨(dú)立集。定理：無向圖G，是G的(極，最大)團(tuán)，充要于是的(極，最大)獨(dú)立集。由上述定理知，三者互相確定，但都是NPC的。但是二分圖中，點(diǎn)覆蓋數(shù)是匹配數(shù)。M是匹配，W是邊覆蓋，N是點(diǎn)覆蓋，Y是點(diǎn)獨(dú)立集。定理：無向圖G無孤立點(diǎn)，|M|=|N|,|Y|=|W|定理：無向圖G無孤立點(diǎn)，。先取一個(gè)

25、最大匹配M，1條邊蓋兩個(gè)點(diǎn)；剩下的一個(gè)未蓋點(diǎn)要用一條邊來覆蓋，邊覆蓋數(shù)=|M| +(|V|-2|M|)= |V|-|M|。定理：無向圖G無孤立點(diǎn)，=，=。定理：無向圖G無孤立點(diǎn)，=。求匹配數(shù)是P的，所以邊覆蓋和匹配都是易求的。最小路徑覆蓋(path covering)：是“路徑” 覆蓋“點(diǎn)”，即用盡量少的不相交簡單路徑覆蓋有向無環(huán)圖G的所有頂點(diǎn)，即每個(gè)頂點(diǎn)嚴(yán)格屬于一條路徑。路徑的長度可能為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)Xi和Yi。然后根據(jù)原圖中邊的信息，從X部往Y

26、部引邊。所有邊的方向都是由X部到Y(jié)部。因此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。因此由最小路徑覆蓋數(shù)原圖G的頂點(diǎn)數(shù)二分圖的最大匹配數(shù)便可以得解。1.1.6. 匹配 Matching匹配(matching)是一個(gè)邊集，滿足邊集中的邊兩兩不鄰接。匹配又稱邊獨(dú)立集(edge independent set)。在匹配中的點(diǎn)稱為匹配點(diǎn)(matched vertex)或飽和點(diǎn)；反之，稱為未匹配點(diǎn)(unmatched vertex)或未飽和點(diǎn)。交錯(cuò)軌(alternating path)是圖的一條簡單路徑，滿足任意相鄰的兩條邊，一條在匹配內(nèi)，一條不在匹配內(nèi)。增廣軌(augmentin

27、g path)：是一個(gè)始點(diǎn)與終點(diǎn)都為未匹配點(diǎn)的交錯(cuò)軌。最大匹配(maximum matching)是具有最多邊的匹配。匹配數(shù)(matching number)是最大匹配的大小。完美匹配(perfect matching)是匹配了所有點(diǎn)的匹配。完備匹配(complete matching)是匹配了二分圖較小部份的所有點(diǎn)的匹配。增廣軌定理：一個(gè)匹配是最大匹配當(dāng)且僅當(dāng)沒有增廣軌。綜上，在二分圖中，最小覆蓋數(shù)=最大匹配數(shù)。邊覆蓋數(shù)=最大獨(dú)立數(shù)=|V|-最大匹配數(shù)。1.1.7. 樹 TreeG=(V, E)為一個(gè)圖，則下列命題等價(jià)：(1)G是一棵樹；(2)G連通，且|E|=|V|-1；(3)G無圈，且|

28、E|=|V|-1；(4)G的任何兩個(gè)頂點(diǎn)之間存在唯一的一條路；(5)G連通，且將G的任何一條弧刪去之后，該圖成為非連通圖；(6)G無圈，且在G的任何兩個(gè)不相鄰頂點(diǎn)之間加入一條弧之后，該圖正好含有一個(gè)圈。Cayley公式：在n階完全圖中，不同生成樹的個(gè)數(shù)為。1.1.8. 組合優(yōu)化 Combinatorial optimization從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為(最)優(yōu)化(optimization)問題。所謂組合(最)優(yōu)化(combinatorial optimization)又稱離散優(yōu)化(discrete optimization)，它是通過數(shù)學(xué)方

29、法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等. 這類問題可用數(shù)學(xué)模型描述為：其中D表示有限個(gè)點(diǎn)組成的集合(定義域)，f為目標(biāo)函數(shù),為可行域。網(wǎng)絡(luò)優(yōu)化(network optimization)就是研究與(賦權(quán))圖有關(guān)的組合優(yōu)化問題。常見的P類網(wǎng)絡(luò)優(yōu)化問題：最小生成樹，最短路，最大流，最小費(fèi)用最大流，最大匹配，中國郵路問題。常見的NP類網(wǎng)絡(luò)優(yōu)化問題：旅行商問題。參考文獻(xiàn)：1Dictionary of Algorithms and Data Structures NIST，2Wikipedia，3謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系講義1.2. 圖的表示 Expressions of graph下面介紹幾

30、種表示圖的數(shù)據(jù)結(jié)構(gòu)。并統(tǒng)一用下圖做例子：12345123786541.2.1. 鄰接矩陣 Adjacency matrix用二元數(shù)組，來表示圖。這種表示法一般用于稠密圖。當(dāng)圖不是簡單圖，鄰接矩陣法不能用。在無權(quán)圖中，若邊存在，=1；否則=0。無權(quán)圖的例子：在有權(quán)圖中, 若邊存在,則為它的權(quán)值；否則人為的規(guī)定=或-。是一個(gè)足夠大的數(shù)。無向圖中，鄰接矩陣是按矩陣副對角線對稱的。1.2.2. 關(guān)聯(lián)矩陣 Incidence matrix用二元數(shù)組，來表示無權(quán)有向圖。一般不用這種表示法。若邊k與點(diǎn)u關(guān)聯(lián)，若k是u的出邊，則=1；若k是u的入邊=-1；否則=0。無權(quán)圖的例子：1.2.3. 鄰接表 Adja

31、cency list圖的鄰接表是圖的所有節(jié)點(diǎn)的鄰接表的集合；而對每個(gè)節(jié)點(diǎn)，它的鄰接表就是它的所有出弧的集合，含有終點(diǎn)，權(quán)值等信息。對于有向圖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,412345283904602403053036470終點(diǎn)權(quán)值指針起點(diǎn)1.2.4. 弧表 Arc list所謂圖的弧表, 也就是圖的弧集合中的所有有序?qū)σ员砀竦姆绞絹肀硎?。弧?/p>

32、表示法直接列出所有弧的起點(diǎn)和終點(diǎn)，以及權(quán)值。一般用于稀疏圖。缺點(diǎn)是無法通過一些信息(起點(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)值843760691.2.5. 星形表示 Star星形表示法就是對弧表的缺點(diǎn)的改進(jìn)，使之可以通過起點(diǎn)或終點(diǎn)定位邊。由于很多時(shí)候，算法只需事先知道起點(diǎn)，通過枚舉邊擴(kuò)展，而不需要事先知道終點(diǎn)；如圖的遍歷，松弛操作。按定位方式，又分前向星形(forwards star)與反向星形(reverse star)。前向星形：通過起點(diǎn)定位邊。反向星形：通過終點(diǎn)定位邊。實(shí)際上，反向星形幾乎沒用

33、。故本文只討論前向星形。通常有兩種方法實(shí)現(xiàn)這種對弧表改進(jìn)：邊排序法，鏈表法。邊排序法：把弧表按起點(diǎn)為第一關(guān)鍵字，終點(diǎn)為第二關(guān)鍵字來排序。排序用不用額外空間的快速排序O(mlogm)或用額外空間O(m)的計(jì)數(shù)排序O(m)均可。之后用數(shù)組last(u)記錄以結(jié)點(diǎn)u為起點(diǎn)的最后一條邊的編號，并規(guī)定last(0)=0。這樣以結(jié)點(diǎn)u為起點(diǎn)的邊編號就是last(u-1)+1到last(u)。有權(quán)圖的例子：作為起點(diǎn)的點(diǎn)012345最后邊的編號023468編號12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)值89640367鏈表法：給每條邊(u,v)加一個(gè)前趨，表示以u為起點(diǎn)的邊鏈表的前一條邊。直觀

34、的講，就是將相同結(jié)點(diǎn)的邊用鏈表串起來。last(u)存以u為起點(diǎn)的最后一條邊的編號。有權(quán)圖的例子：作為起點(diǎn)的點(diǎn)12345最后邊的編號65278編號012345678起點(diǎn)nil53412145終點(diǎn)nil42524333權(quán)值nil74386906前趨nil00000431星形表示法的優(yōu)點(diǎn)是占用的存貯空間較少。一般圖都適用。邊排序法的優(yōu)點(diǎn)是已知起點(diǎn)和終點(diǎn)的情況下可以精確定位邊，容易在起點(diǎn)定位的范圍內(nèi)二分查找終點(diǎn)，在反向邊的定位中常用；缺點(diǎn)是代碼麻煩，時(shí)間抑或空間上都有額外開銷。鏈表法的優(yōu)點(diǎn)很多，不僅代碼簡單，而且沒有太多的時(shí)空開銷，對于反向邊的定位只要多加一個(gè)數(shù)據(jù)項(xiàng)紀(jì)錄下反向邊即可；除了終點(diǎn)定位性，

35、幾乎沒缺點(diǎn)。參考文獻(xiàn)：1謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系講義2劉汝佳，黃亮，P601.3. 圖的遍歷 Traveling in graph1.3.1. 深度優(yōu)先搜索 Depth first search (DFS)1.3.1.1. 概念1.3.1.2. 求無向連通圖中的橋 Finding bridges in undirected graph在無向連通的條件下，邊是橋的充要條件是：1.橋一定是DFS樹中的邊；2.橋一定不在圈中。圈是由一條后向邊(u,v)與DFS樹中u到v的路徑組成。也就是說u到v的路徑上的邊都不可能是橋，應(yīng)該給以標(biāo)記。記f(x)為x與其子孫的后向邊所連到的最老祖先(深度最淺)，表示

36、x 到f(x) 上的邊均不為橋。然而維護(hù)f(x)比較麻煩，其實(shí)只要知道f(x)的拓?fù)湫驍?shù)就可以了。所謂拓?fù)湫驍?shù)就是滿足兒子的序數(shù)總比父親大的一個(gè)編號方式。這個(gè)拓?fù)湫颍Ｓ檬褂蒙疃萪，或者使用時(shí)間戳(TimeStamp) DFN（DFS訪問的次序）。下面以深度為例：記，在DFS樹中從x開始通過前向弧和后向弧所能到達(dá)的最小的d。有以下的動態(tài)規(guī)劃：這里：1.第一次訪問x時(shí)，記錄d(x)2. d(y)自己發(fā)出去的后向邊所達(dá)到的深度。3. g(c)就是其子孫中的g最小值。最后，若g(x)=d(x)，即(father,x)不在圈中，則(father, x)就是橋。1.3.2. 廣度優(yōu)先搜索 Breadth

37、 first search (BFS)1.4. 拓?fù)渑判?Topological sort拓?fù)渑判蚴菍τ邢驘o圈圖(DAG)頂點(diǎn)的一種排序，它使得如果存在u,v的有向路徑，那么滿足序中u在v前。拓?fù)渑判蚓褪怯梢环N偏序(partical order)得到一個(gè)全序(稱為拓?fù)溆行?topological order)。偏序是滿足自反性，反對稱性，傳遞性的序。拓補(bǔ)排序的思路很簡單，就是每次任意找一個(gè)入度為0的點(diǎn)輸出，并把這個(gè)點(diǎn)以及與這個(gè)點(diǎn)相關(guān)的邊刪除。實(shí)際算法中，用一個(gè)隊(duì)列實(shí)現(xiàn)。算法：1. 把所有入度=0的點(diǎn)入隊(duì)Q。2. 若隊(duì)Q非空，則點(diǎn)u出隊(duì)，輸出u；否則轉(zhuǎn)4。3. 把所有與點(diǎn)u相關(guān)的邊(u,v)刪除

38、，若此過程中有點(diǎn)v的入度變?yōu)?，則把v入隊(duì)Q，轉(zhuǎn)2。4. 若出隊(duì)點(diǎn)數(shù)m，結(jié)束，此時(shí)G沒有生成樹；否則判斷是否含圈，是則轉(zhuǎn)2，否則轉(zhuǎn)3。3. 。若|T|=N，結(jié)束，此時(shí)T為G的最小生成樹。分離集合(disjoint set)，可用并查集實(shí)現(xiàn)。由于排序是的。所以復(fù)雜度為。1.6.1.1.3. Sollin（Boruvka）基本思想：前面介紹的兩種算法的綜合。每次迭代同時(shí)擴(kuò)展多棵子樹，直到得到最小生成樹 T。算法：1. 對于所有。2. 若|T|=N，結(jié)束，此時(shí)T為G的最小生成樹；否則，對于T中所有的子樹集合，計(jì)算它的邊割中的最小?。ㄓ械臅Q連接兩個(gè)連通分量的最小弧“安全邊”）。3. 對T中所有子樹集

39、合及其邊割最小弧，將與q所在的子樹集合合并。轉(zhuǎn)2。由于每次循環(huán)迭代時(shí)，每棵樹都會合并成一棵較大的子樹，因此每次循環(huán)迭代都會使子樹的數(shù)量至少減少一半，或者說第i次迭代每個(gè)分量大小至少為。所以，循環(huán)迭代的總次數(shù)為O(logn)。每次循環(huán)迭代所需要的計(jì)算時(shí)間：對于第2步，每次檢查所有邊O(m)，去更新每個(gè)連通分量的最小弧；對于第3步，合并個(gè)子樹。所以總的復(fù)雜度為。1.6.1.2. 擴(kuò)展模型 Extended models1.6.1.2.1. 度限制生成樹 Minimum degree-bounded spanning trees由于這個(gè)問題是NP-Hard的，一般用搜索算法解決。本文就只討論一種特殊

40、多項(xiàng)式情況：單點(diǎn)度限制(one node degree bounded)。把度限制的點(diǎn)記為，滿足度限制。一種貪心的思路：在最小生成樹T的基礎(chǔ)上，通過添刪邊來改造樹，使之逐漸滿足度限制條件。算法：1. 求圖的最小生成樹T。2. 若已滿足度限制，結(jié)束；否則轉(zhuǎn)3。3. 對于刪去后的每一個(gè)連通分支(為一棵樹)，求添加邊割中的最小弧，刪除邊割里的最大弧后的生成樹中的邊權(quán)和最小的一個(gè)。更新最小生成樹T。轉(zhuǎn)2。第3步，的度少1。習(xí)題：NOI 2005 小H的聚會1.6.1.2.2. k小生成樹 The k minimum spanning tree problem(k-MST)生成樹T刪除一條邊f(xié)并加入一條

41、新邊e的操作稱為交換。若交換后的圖仍是一顆樹，則此交換稱為可行交換。若生成樹T可通過一次交換成為生成樹T，則稱它們互為鄰樹。對于生成樹集合S，生成樹T，若T不在S中，且在S中存在某生成樹是T的鄰樹，稱為T為S的鄰樹。定理：設(shè)為圖的前k小生成樹，則生成圖集合的鄰樹中的邊權(quán)和最小者可作為第k+1小生成樹(可能有邊權(quán)和相同的情況)。按這個(gè)定理設(shè)計(jì)算法，很難得到有滿意的時(shí)間復(fù)雜度的算法。下面討論一個(gè)特例：次小生成樹(The second MST, 2-MST)基本思想：枚舉最小生成樹T的每一個(gè)鄰樹，即枚舉被添加與被刪除的邊。由于在樹中添加一條邊()，一定形成了一個(gè)環(huán)，環(huán)是由與從u到v的生成樹上的唯一路

42、徑(記為)組成的。所以被刪除的邊一定在上。由于要求最小邊權(quán)和，所以被刪除的邊一定是上最小者，其權(quán)值記為：。算法：1. 求圖的最小生成樹T。次小生成樹T的權(quán)值的最小值。2. 以每個(gè)結(jié)點(diǎn)為根r，DFS遍歷樹。在遍歷過程中求出，用更新次小生成樹的權(quán)值的最小值。3. 輸出。算法復(fù)雜度的瓶頸在第2步，故總算法復(fù)雜度為。習(xí)題：Ural 1416 Confidential1.6.2. 最短路Shortest paths1.6.2.1. 單源最短路 Single-source shortest paths令s為起點(diǎn)，t為終點(diǎn)。單源最短路問題定義為：對于網(wǎng)絡(luò)G=(V,E,W)，尋找s到t的一條簡單路徑，使得路徑

43、上的所有邊權(quán)和最少。令d(v)為s到v的最短路長度上界。單源最短路問題的規(guī)劃模型如下：對于只含正有向圈的連通有向網(wǎng)絡(luò)，從起點(diǎn)s到任一頂點(diǎn)j都存在最短路，它們構(gòu)成以起點(diǎn)s為根的樹形圖（稱為最短路樹（Tree of Shortest Paths）。當(dāng)某弧(u,v)位于最短路上時(shí)，一定有。所以最短路的長度可以由Bellman方程（最短路方程）唯一確定：在規(guī)劃模型與最短路方程中都出現(xiàn)了形式的式子，下面引入松弛操作：松弛操作是對于邊(u,v)進(jìn)行的改進(jìn)操作：若，則改進(jìn)。直觀的講，就是路徑最后通過(u,v)，使得s到v的距離比原來s到v的方案的距離短。松弛操作是最短路算法求解的基本方式。最短路算法求解過程

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

45、修正，所有頂點(diǎn)標(biāo)號仍然都是臨時(shí)標(biāo)號；只有在所有迭代終止時(shí)，所有頂點(diǎn)標(biāo)號同時(shí)轉(zhuǎn)變?yōu)橛谰脴?biāo)號。最長路問題可以轉(zhuǎn)化為最短路問題，把弧上的費(fèi)用反號即可。1.6.2.1.1. 基本算法 Basic algorithms1.6.2.1.1.1. Dijkstra采用了標(biāo)號設(shè)定算法(Label-Setting)。在迭代進(jìn)行計(jì)算的過程中，所有頂點(diǎn)實(shí)際上被分成了兩類：一類是離起點(diǎn)較近的頂點(diǎn)，它們的距離標(biāo)號表示的是從點(diǎn)s到該頂點(diǎn)的最短路長度，因此其標(biāo)號不會在以后的迭代中再被改變（稱為永久標(biāo)號）；一類是離起點(diǎn)較遠(yuǎn)的頂點(diǎn)，它們的距離標(biāo)號表示的只是從點(diǎn)到該頂點(diǎn)的最短路長度的上界，因此其標(biāo)號還可能會在以后的迭代中再被改變

46、（稱為臨時(shí)標(biāo)號）。下文稱永久標(biāo)號為已檢查。算法：1. ，已檢查2. 取未檢查的u，即，使得最小。若u取不到，即d(u)=則結(jié)束；否則標(biāo)記為已檢查，即。3. 枚舉所有的u的臨邊，滿足v未檢查，即。松弛，即若，則改進(jìn)，pred(v)=u。轉(zhuǎn)2。這里的d可以用優(yōu)先隊(duì)列實(shí)現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。假設(shè)用Fibonacci Heap實(shí)現(xiàn)(刪除最小O(logn)，減值O(1)，則算法復(fù)雜度：。若用Binary Heap則。適用范圍：非負(fù)權(quán)圖。1.6.2.1.1.2. Bellman-Ford采用了標(biāo)號修正算法(Label-Correcting)。本質(zhì)就

47、是用迭代法（動態(tài)規(guī)劃）解Bellman-Ford方程：表示s到v的且邊數(shù)不超過k條時(shí)的最短路路長。下面用歸納法證明：k=1顯然成立。假設(shè)對k成立，下面考慮k+1的情況.從起點(diǎn)s到頂點(diǎn)v且所經(jīng)過的弧數(shù)不超過k+1條時(shí)的最短路有兩種可能：含有不超過k條弧，即；含有k+1條弧，即。由于第k+1次迭代過程中，不會影響k次的迭代結(jié)果，d用O(n)的空間即可。算法：1. ，2. 松弛所有邊(u,v)，即若，則改進(jìn)，pred(v)=u。若沒有邊被松弛，則算法結(jié)束。3. 若2的迭代次數(shù)超過n-1，則有負(fù)權(quán)圈，結(jié)束；否則轉(zhuǎn)2繼續(xù)迭代?？梢宰C明算法一定在n-1步迭代后收斂；否則一定有負(fù)權(quán)圈。所以算法復(fù)雜度為O(n

48、m)。適用范圍：一般圖。1.6.2.1.1.2.1. Shortestpathfasteralgorithm(SPFA)SPFA 其實(shí)就是Bellman-Ford的一種隊(duì)列實(shí)現(xiàn)，減少了冗余，即松馳的邊至少不會以一個(gè)d為的點(diǎn)為起點(diǎn)。算法：1. 隊(duì)列Q=s，2. 取出隊(duì)頭u，枚舉所有的u的臨邊。若，則改進(jìn)，pred(v)=u，由于減少了，v可能在以后改進(jìn)其他的點(diǎn)，所以若v不在Q中，則將v入隊(duì)。3. 一直迭代2，直到隊(duì)列Q為空(正常結(jié)束)，或有的點(diǎn)的入隊(duì)次數(shù)=n（含有負(fù)圈）。由于點(diǎn)可能多次入隊(duì)，但隊(duì)列中同時(shí)不會超過n個(gè)點(diǎn)。所以用一個(gè)長度為n的循環(huán)隊(duì)列來實(shí)現(xiàn)這個(gè)隊(duì)。SPFA在形式上和寬度優(yōu)先搜索非常類

49、似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過其它的點(diǎn)之后，過了一段時(shí)間可能本身被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。設(shè)一個(gè)點(diǎn)用來作為迭代點(diǎn)對其它點(diǎn)進(jìn)行改進(jìn)的平均次數(shù)為k，有辦法證明對于通常的（不含負(fù)圈，較稀疏）情況，k在2左右。算法復(fù)雜度理論上同Bellman-Ford，O(nm)，但實(shí)際上卻是O(km)。一般用于找負(fù)圈(效率高于Bellman-Ford)，稀疏圖的最短路。習(xí)題：Ural 1254 Die Hard （可斜走的網(wǎng)格最短路）。1.6.2.1.2. 應(yīng)用Applications1.6.2.1.2.1. 差分約束系統(tǒng) System of difference constraints差分約束系統(tǒng)：求解n個(gè)未知數(shù)，滿足m個(gè)不等式：若描述為線形規(guī)劃模型：。矩陣A每行含一個(gè)1一個(gè)-1，其他都是0。如線形規(guī)劃模型等價(jià)于注意到單源最短路模型中的。，即。很像差分約束系統(tǒng)模型。于是可以構(gòu)造一個(gè)有向網(wǎng)絡(luò)G=(V,E,W)，稱為約束圖(constraints graph)。W：，對進(jìn)行Bellman-Ford算法，可以得到，令，即為所求，其中C是任意一個(gè)常數(shù)，均滿足原不等式組。當(dāng)有為負(fù)數(shù)且題