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

1、1.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 matrix1.2.

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). 概念. 求無向連通圖中的橋 Finding bridges in undirected graph1.3.2. 廣度優(yōu)先搜索 Breadth first search (BFS).拓?fù)渑判?Topological sort1.5.2. Hamiltonian

3、 Cycle 哈氏路徑與回路 無權(quán)圖 Unweighted 有權(quán)圖 Weighed 旅行商問題 The travelling salesman problem路徑與回路 Paths and circuits1.5.1. 歐拉路徑或回路Eulerian path.無向圖.有向圖.混合圖.無權(quán)圖Unweighted.有權(quán)圖Weighed 中國郵路問題The Chinese post problem..1.6.網(wǎng)絡(luò)優(yōu)化 Network optimization1.6.1. 最小生成樹 Minimum s

4、panning trees. 基本算法 Basic algorithms.1. Prim.2. Kruskal.3. Sollin (Boruvka). 擴(kuò)展模型 Extended models.1. 度限制生成樹 Minimum degree-bounded spanning trees.2. k 小生成樹 The k minimum spanning tree problem(k-MST)1.6.2. 最短路 Shortest paths. 單源最短路 Single-source

5、 shortest paths.1. 基本算法 Basic algorithms Dijkstra Bellman-Ford Shortest path faster algorithm(SPFA).1.1 .1.2 .1.2.1 .2. 應(yīng)用 Applications.2.1. 差分約束系統(tǒng) System of difference constraints.2.2. 有向無環(huán)圖上的最短路 Shortest paths in DAG. 所有頂點對間最短路 All-pairs shor

6、test paths.1. 基本算法 Basic algorithmsFloyd-Warshall Johnson.1.1 .1.2 1.6.3. 網(wǎng)絡(luò)流 Flow network. 最大流 Maximum flow Ford-Fulkerson method Edmonds-Karp algorithm M inimum length path Maximum capability path 預(yù)流推進(jìn)算法 Preflow push method Push-relabel Relabel-to-front Dinic method1.6.

7、3.1.1. 基本算法 Basic algorithms.1.1 .1.1.1 . . .1.2 .1.2.1 .1.2.2 .1.3有上下界的流問題.2. 擴(kuò)展模型 Extended models.2.1 . 最小費用流 Minimum cost flow.1. 找最小費用路 Finding minimum cost path.2. 找負(fù)權(quán)圈 Finding negative circ

8、le.3. 網(wǎng)絡(luò)單純形 Network simplex algorithm1.6.4. 匹配 Matching. 二分圖 Bipartite Graph.1. 無權(quán)圖 -匈牙利算法 Unweighted - Hopcroft and Karp algorithm 164.12 帶權(quán)圖-KM 算法 Weighted -Kuhn-Munkres(KM) algorithm. 一般圖 General Graph.1. 無權(quán)圖-帶花樹算法 Unweighted - Blossom (Edmonds)1. 圖論 Graph Theor

9、y1.1. 定義與術(shù)語 Definition and Glossary1.1.1. 圖與網(wǎng)絡(luò) Graph and Network二元組V, E稱為圖(graph)。V為結(jié)點(node)或頂點(vertex)集。E為V中結(jié)點之間的邊的集合。點對u,v稱為邊(edge)或稱弧(arc)，其中u,v V，稱u,v是相鄰的(adjacent),稱u,v與邊u, v相關(guān)聯(lián)(incident)或相鄰。若邊的點對u,v有序則稱為有向(directed)邊，其中u稱為頭(head)，v稱為尾(tail)。所形 成的圖稱有向圖(directed graph)b為對于u來說u,v是出邊(outgoing arc)

10、;對于v來說u,v是入邊(in comi ng arc)。反之，若邊的點對無序則稱為 無向(un directed)邊，所形成的圖稱無向圖 (undirected graph)。若圖的邊有一個權(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)。滿足|E| |V|log |V |的圖，稱為稀疏(sp arse圖；反之，稱為 稠密(de nse)ffl。1.1.2. 圖的術(shù)語 Glossary of Graph階(order):圖G中頂點集V的大小稱作圖

11、G的階。 環(huán)(loo P):若一條邊的兩個頂點為同一頂點，則此邊稱作環(huán)。 簡單圖(simple graph)：沒有環(huán)、且沒有多重弧的圖稱作簡單圖。 定向圖：對無向圖G的每條無向邊指定一個方向得到的有向圖。 底圖 :把一個有向圖的每一條有向邊的方向都去掉得到的無向圖。 逆圖 ：把一個有向圖的每條邊都反向由此得到的有向圖。 競賽圖(tournament):有向圖的底圖是無向完全圖，則此有向圖是競賽圖。鄰域(n eighborhood)：在圖中與u相鄰的點的集合v|v V,(u,v) E，稱為u的鄰域，記為 N(u) 。度：度(degree)： 一個頂點的度是指與該邊相關(guān)聯(lián)的邊的條數(shù)，頂點v的度記作

12、deg(v)。握手定理：無向圖：deg(v) 2 | E | ;有向圖：deg (v) deg (v)。v Vv Vv V入度(indegree)：在有向圖中，一個頂點v的入度是指與該邊相關(guān)聯(lián)的入邊(即邊的尾是v) 的條數(shù)，記作deg (v)。出度(outdegree)：在有向圖中，一個頂點的出度是指與該邊相關(guān)聯(lián)的出邊(即邊的頭是v)的條數(shù)，記作deg (v)。孤立點(isolated vertex)：度為0的點。葉(leaf):度為1的點。源(source)：有向圖中，deg (v) =0的點。匯(sink):有向圖中，deg (v) =0的點。 奇點(odd vertex):度為奇數(shù)的點。

13、偶點(even vertex)：度為偶數(shù)的點。子圖:子圖(sub-graph): G稱作圖G的子圖如果V(G) V(G)以及E(G) E(G)。生成子圖(spanning sub-graph)：即包含G的所有頂點的連通子圖，即滿足條件V(G) V(G)的G的子圖G生成樹(spanning tree):設(shè)T是圖G的一個子圖，如果T是一棵樹，且V(T) V(G)，貝U稱T是G的一個生成樹。即G的生成子圖，且子圖為樹。點導(dǎo)出子圖(induced subgraph)設(shè)VV(G)，以V為頂點集，以兩端點均在V中的邊的全體為邊集所組成的子圖，稱為G的由頂點集V導(dǎo)出的子圖，簡稱為G的點導(dǎo)出子圖，記為GV 。

14、邊導(dǎo)出子圖(edge-induced subgraph)：設(shè)E E(G)，以E為頂點集，以兩端點均在 E中的邊的全體為邊集所組成的子圖，稱為 G的由邊集E導(dǎo)出的子圖，簡稱為G的邊導(dǎo)出子圖,圖的補(bǔ)圖(complement):記為GE。設(shè)G是一個圖，以V(G)為頂點集，以(u,v) |(u,v)E(G)為邊集的圖稱為G的補(bǔ)圖，記為點集的補(bǔ)集：記V VV為點集V的補(bǔ)集。特殊的圖：零圖(null graph)： E，即只有孤立點的圖。n階零圖記為Nn。的圖。平凡圖(trivial graph)： 階零圖。 空圖(empty graph)： V E有向無環(huán)圖(directed acyclic graph

15、(DAG)：有向的無環(huán)的圖。完全圖(complete graph)：完全圖是指每一對不同頂點間都有邊相連的的無向圖，n階完全圖常記作 Kn 。二分圖(bip artite graph)：若圖G的頂點集可劃分為兩個非空子集 X和丫，即V X 丫 且X 丫，且每一條邊都有一個頂點在 X中，而另一個頂點在丫中，那么這樣的圖稱作二分圖。完全二分圖(complete bipartite graph)： 二分圖G中若任意兩個X和丫中的頂點都有邊相 連，則這樣的圖稱作完全二分圖。若|X| m,|Y| n，則完全二分圖G記作Km。正則圖(regular graph)：如果圖中所有頂點的度皆相等，貝U此圖稱為正

16、則圖。1.1.3. 路徑與回路 Path and Cycle途徑(walk):圖G中一個點邊交替出現(xiàn)的序列P VioqvnqL eM，滿足v. V,ej E， eij (vij1,vij)。跡(trail):邊不重復(fù)的途徑。路(P ath):頂點不重復(fù)的跡。ik簡單圖中的路可以完全用頂點來表示， P vi0vi1 vi若PiPm，稱閉的(closed)；反之，稱為開的(open)。閉途徑(closed walk):起點和終點相同的途徑。閉跡(closed trail):起點和終點相同的跡，也稱為 回路(circuit)。圈(cycle):起點和終點相同的路。途徑(閉途徑)、跡(閉跡)、路(圈)

17、上所含的邊的個數(shù)稱為它的長度(le ngth)。簡單圖G中長度為奇數(shù)和偶數(shù)的圈分別稱為 奇圈(odd cycle)和偶圈(even cycle)。對任意u,v V(G)，從x到y(tǒng)的具有最小長度的路稱為x到y(tǒng)的最短路(shortest path)，其長度稱為x到y(tǒng)的距離(distanee),記為dG(u,v)。圖 G 的直徑(diameter)： D maxdG(u,v) | u,v V(G)。簡單圖G中最短圈的長度稱為圖 G的圍長(girth)，最長圈的長度稱為圖G的周長(perimeter)。1.1.4. 連通性 Connectivity連通(connected):在圖G中，兩個頂點間，至少

18、存在一條路徑，稱兩個頂點連通的(connected);反之，稱非連通(unconnected。強(qiáng)連通(strongly connected):在有向圖G中，兩個頂點間，至少存在一條路徑，稱兩個頂 點強(qiáng)連通。弱連通(weakly connected):在有向圖G中，兩個頂點間，若不考慮 G中邊的方向的圖才 連通的，稱原有向圖為弱連通。連通圖(connected graph)圖G中任二頂點都連通。連通分量或連通分支(co nnected bran ch, componen t):非連通無向圖的極大連通子圖 (maximally connected sub-graph)。具體說，若圖 G的頂點集 V

19、(G)可劃分為若干非空子集V1,V2, ,V，使得兩頂點屬于同一子集當(dāng)且僅當(dāng)它們在G中連通，則稱每個子圖GVi為圖G的一個連通分支( i 1,2, , )。圖 G 的連通分支是 G 的一個極大連通子圖。圖 G 連通當(dāng) 且僅當(dāng)=1。強(qiáng)連通分量 (strongly connected branch) 非強(qiáng)連通圖有向圖的極大強(qiáng)連通子圖。割 (cut)：點割集(vertex cut):點集V V,若G刪除了 V后不連通，但刪除了 V的任意真子集后 G 仍然連通。則稱 V 點割集。若某一結(jié)點就構(gòu)成就了點割集，則稱此結(jié)點 割點 (cut vertex)。 點數(shù)最少的點割集稱為 點連通度 k(G)。邊割集(

20、edge cut set):邊集E E，若G刪除了 E后不連通，但刪除了 E的任意真子集 后G仍然連通。則稱E點割集。若某一邊就構(gòu)成就了邊割集，則稱此結(jié)點 害也(cut edge或橋 (bridge)。邊數(shù)最少的邊割集稱為 邊連通度kG)。記號S,S表示一端在S中另一端在S中的所有邊的集合。塊(block)是指沒有割點的極大連通子圖。1.1.5. 圖論中特殊的集合 Sets in graph有v V, v關(guān)聯(lián)e。即一覆蓋了所有“邊”。 極小點最小點覆蓋 (minimum vertex點覆蓋(集)(vertex covering (set): V V，滿足對于 e E， 個點集，使得所有邊至少有

21、一個端點在集合里?；蛘哒f是“點” 覆蓋 (minimal vertex covering) ：本身為點覆蓋，其真子集都不是。covering):點最少的點覆蓋。點覆蓋數(shù)(vertex covering number)：最小點覆蓋的點數(shù)，記為V(G)V，有e E，e關(guān)聯(lián)v。即一個覆蓋了所有“點”。 極小邊覆蓋最小邊覆蓋 (minimum edge一般說覆蓋集就是指點覆蓋集。邊覆蓋(集)(edge covering (set) E E，滿足對于 v 邊集，使得所有點都與集合里的邊鄰接?；蛘哒f是“邊” (minimal edge covering) ：本身是邊覆蓋，其真子集都不是。covering)

22、：邊最少的邊覆蓋。邊覆蓋數(shù)(edge covering number)最小邊覆蓋的邊數(shù)，記為e(G)。獨立集(in de pen de nt set): V V，滿足對于u,v V，有(u,v) E。即一個點集，集合中任兩個結(jié)點不相鄰，則稱V為獨立集。或者說是導(dǎo)出的子圖是零圖(沒有邊)的點集。極大獨立集(maximal i ndepen de nt set):本身為獨立集，再加入任何點都不是。最大獨立集(maximum independent set) 點最多的獨立集。 獨立數(shù)(independent number) 最大獨立集的點數(shù)，記為V(G)。團(tuán)(clique): V V ,滿足對于u,

23、v V，有(u,v) E。即一個點集，集合中任兩個結(jié)點相鄰?；蛘哒f是導(dǎo)出的子圖是完全圖的點集。 極大團(tuán)(maximal clique)：本身為團(tuán)，再加入任 何點都不是。最大團(tuán)(maximum clique)：點最多的團(tuán)。團(tuán)數(shù)(clique number)：最大團(tuán)的點數(shù)， 記為(G)。邊獨立集(edge indepen de nt set) E E，滿足對于 e, f E，有e, f不鄰接。即一個邊集，滿足邊集中的任兩邊不鄰接。 極大邊獨立集(maximal edge in de pen de nt set)：本身為邊獨 立集，再加入任何邊都不是。 最大邊獨立集(maximum edge ind

24、epen de nt set)邊最多的邊獨立 集。邊獨立數(shù)(edge in de pen de nt number)最大邊獨立集的邊數(shù)，記為 e(G)。邊獨立集又稱匹配(matchi ng)，相應(yīng)的有極大匹配(maximal matchi ng),最大匹配(maximum match in g)， 匹配數(shù)(matchi ng nu mber)。支配集(dominating set)： V V，滿足對于 u V V，有 v V， (u,v) E。即一個點集，使得所有其他點至少有一個相鄰點在集合里。 或者說是一部分的“點”支配了所有“點”。 極小支配集(minimal dominating set

25、):本身為支配集，其真子集都不是。 最小支配集(minimum dominating set)：點最少的支配集。支配數(shù)(dominating number)：最小支配集的點數(shù)，記為v(G)。邊支配集(edge dominating set) E E，滿足對于 e E E，有f E，e, f鄰接。即 一個邊集，使得所有邊至少有一條鄰接邊在集合里。 或者說是一部分的“邊”支配了所有“邊”。 極小邊支配集(minimal edge dominating set)：本身是邊支配集，其真子集都不是。 最小邊支配 集(minimum edge dominating set): 邊最少的邊支配集。 邊支配數(shù)

26、(edge dominating number)： 最小邊支配集的邊數(shù)，記為 e(G)。定理：若G中無孤立點，D為支配集，則D=V(G)-D也是一個支配集。 定理：一個獨立集是極大獨立集，當(dāng)且僅當(dāng)它是支配集。關(guān)系:定理：無向圖G無孤立點，V是極小支配集，則存在V2是極小支配集，且V V定理：無向圖 G無孤立點，V是極大獨立集，則V是極小支配集。逆命題不成立。v(G) v(G)。定理：連通圖中，V是點覆蓋，則V是支配集。極小點覆蓋不一定是極小支配集。支配 集不一定是點覆蓋。定理：無向圖G無孤立點，V是(極，最小)點覆蓋，充要于V V是(極，最大)獨立集。v(G) v(G)|V|。V(G)。定理：

27、無向圖G,V是G的(極，最大)團(tuán)，充要于V是G的(極，最大)獨立集。(G)由上述定理知，v(G)， v(G)， (G)三者互相確定，但都是NPC的。但是二分圖中,點覆蓋數(shù)是匹配數(shù)。M 是匹配， W 是邊覆蓋， N 是點覆蓋， Y 是點獨立集。定理：無向圖G無孤立點，|M|v=|N|,|Y|v=|W|E(G)定理：無向圖G無孤立點，e(G) e(G) |V |。先取一個最大匹配 M ,1條邊蓋兩個點;剩下的一個未蓋點要用一條邊來覆蓋，邊覆蓋數(shù) =|M| +(|V|-2|M|)= |V|-|M|。定理：無向圖G無孤立點，e(G) = v(G)， v(G)= e(G)。定理：無向圖G無孤立點，(G)

28、= V(G)。求匹配數(shù)是 P 的，所以邊覆蓋和匹配都是易求的。最小路徑覆蓋(path covering)：是“路徑”覆蓋“點”，即用盡量少的不相交簡單路徑覆 蓋有向無環(huán)圖 G 的所有頂點，即每個頂點嚴(yán)格屬于一條路徑。路徑的長度可能為0(單個點 )。i 拆成兩個頂點 Xi 和 X 部到 Y 部。因 因此由最小路徑最小路徑覆蓋數(shù)=G的點數(shù)-最小路徑覆蓋中的邊數(shù)。應(yīng)該使得最小路徑覆蓋中的邊數(shù) 盡量多，但是又不能讓兩條邊在同一個頂點相交。拆點：將每一個頂點Yi。然后根據(jù)原圖中邊的信息，從 X部往丫部引邊。所有邊的方向都是由 此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。覆蓋數(shù)=原圖

29、G的頂點數(shù)一二分圖的最大匹配數(shù)便可以得解。1.1.6. 匹配 Matching稱邊獨立集(edge匹配(matching)是一個邊集，滿 足邊集中的邊 兩兩不鄰接。匹配又independent set。)在匹配中的點稱為 匹配點(matched vertex)或飽和點；反之，稱為未匹配點(unmatched vertex) 或未飽和點。交錯軌(alternating path)是圖的一條簡單路徑，滿足任意相鄰的兩條邊，一條在匹配內(nèi)， 一條不在匹配內(nèi)。增廣軌(augmenting path)：是一個始點與終點都為未匹配點的交錯軌。最大匹配(maximum matchi ng)是具有最多邊的匹配。

30、匹配數(shù)(matchi ng number)是最大匹配的大小。完美匹配(P erfect matchi ng)是匹配了所有點的匹配。完備匹配(com plete matchi ng是匹配了二分圖較小部份的所有點的匹配。 增廣軌定理 ：一個匹配是最大匹配當(dāng)且僅當(dāng)沒有增廣軌。綜上，在二分圖中，最小覆蓋數(shù)=最大匹配數(shù)。邊覆蓋數(shù)=最大獨立數(shù)=|V|-最大匹配數(shù)。1.1.7. 樹 TreeG=(V, E)為一個圖，則下列命題等價：(1)G是一棵樹；(2)G連通，且|E|=|V|-1 ； (3)G無圈,且|E|=|V|-1; (4)G的任何兩個頂點之間存在唯一的一條路；G連通，且將G的任何一條弧刪去之后，該

31、圖成為非連通圖；(6)G無圈，且在G的任何兩個不相鄰頂點之間加入一條弧之 后，該圖正好含有一個圈。Cayley公式：在n階完全圖 心中，不同生成樹的個數(shù)為nn 21.1.8. 組合優(yōu)化 Combinatorial optimization從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為(最)優(yōu)化(optimization)問題。法去所謂組合(最)優(yōu)化(combinatorial optimization)又稱離散優(yōu)化(discrete optimization)，它是通 過數(shù)學(xué)方法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等 . 這類問題可用數(shù)學(xué)模型描述 為：min

32、 f(x)s.t. g(x) 0, x D其中D表示有限個點組成的集合(定義域),f為目標(biāo)函數(shù),F x|x D,g(x) 0為可行域。網(wǎng)絡(luò)優(yōu)化(network optimization)就是研究與(賦權(quán))圖有關(guān)的組合優(yōu)化問題。常見的 P 類網(wǎng)絡(luò)優(yōu)化問題：最小生成樹，最短路，最大流，最小費用最大流，最大匹配， 中國郵路問題。常見的 NP 類網(wǎng)絡(luò)優(yōu)化問題：旅行商問題。參考文獻(xiàn)：1 Dictionary of Algorithms and Data Structures NIST， /dads/2 Wikipedia ， http:/en.wikipedia.or

33、g/wiki/Graph_theory3 謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系 網(wǎng)絡(luò)優(yōu)化講義 1.2. 圖的表示 Expressions of graph面介紹幾種表示圖的數(shù)據(jù)結(jié)構(gòu)。并統(tǒng)一用下圖做例子：241.2.1. 鄰接矩陣 Adjacency matrix用二元數(shù)組A(u,v)，來表示圖。這種表示法一般用于稠密圖。當(dāng)圖不是簡單圖，鄰接矩 陣法不能用。在無權(quán)圖中，若邊(u,v)存在，A(u,v)=1 ；否則A(u,v)=O。A(au,v)n n 0,1au,v0, (u,v) E1, (u,v) E無權(quán)圖的例子:0000010100100110100100010在有權(quán)圖中，若邊(u,v)存在，則A(

34、u,v)為它的權(quán)值；否則人為的規(guī)定 A(u,v)= X或-是一個足夠大的數(shù)。A(au,v)n n ,au,vw(u,v),(u,v) E,(u,v) E無向圖中，鄰接矩陣是按矩陣副對角線對稱的。1.2.2. 關(guān)聯(lián)矩陣 Incidence matrix用二元數(shù)組B(u,k)，來表示無權(quán)有向圖。一般不用這種表示法。若邊k與點U關(guān)聯(lián)，若k是U的出邊，貝U B(u, k) =1 ；若k是u的入邊B(u,k) =-1 ；否則B(u,k)=O。B (bu,k)nm 1,0,1nm, bu,k1,1,0,V V,k (u,v) E,V V,k (v,u) E， else無權(quán)圖的例子:110001010001

35、0100110000110000110010100011123. 鄰接表 Adjacency list圖的鄰接表是圖的所有節(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終點權(quán)值指針起點1.2.4. 弧表 Arc list所謂圖的弧表，也就是圖的弧

36、集合中的所有有序?qū)σ员砀竦姆绞絹肀硎尽?弧表表示法直接 列出所有弧的起點和終點，以及權(quán)值。一般用于稀疏圖。缺點是無法通過一些信息 (起點，終 點)定位一條邊。用S(i),F(i),W(i)分別表示起點，終點，權(quán)值。有權(quán)圖的例子：起點13455421終占k、八、22543343權(quán)值84376069125.星形表示 Star星形表示法就是對弧表的缺點的改進(jìn)，使之可以通過起點或終點定位邊。由于很多時候， 算法只需事先知道起點，通過枚舉邊擴(kuò)展，而不需要事先知道終點；如圖的遍歷，松弛操作。按定位方式，又分前向星形(forwards star)與反向星形(reverse star).前向星形：通過起點 定

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

38、(u,v)加一個前趨，表示以u為起點的邊鏈表的前一條邊。直觀的講， 就是將相同結(jié)點的邊用鏈表串起來。last(u)存以u為起點的最后一條邊的編號。有權(quán)圖的例子:作為起點的點12345最后邊的編號65278編號012345678起點nil53412145終點nil42524333權(quán)值nil74386906前趨nil00000431星形表示法的優(yōu)點是占用的存貯空間較少。一般圖都適用。邊排序法的優(yōu)點是已知起點 和終點的情況下可以精確定位邊，容易在起點定位的范圍內(nèi)二分查找終點，在反向邊的定位 中常用；缺點是代碼麻煩，時間抑或空間上都有額外開銷。鏈表法的優(yōu)點很多，不僅代碼簡 單，而且沒有太多的時空開銷，

39、對于反向邊的定位只要多加一個數(shù)據(jù)項紀(jì)錄下反向邊即可； 除了終點定位性，幾乎沒缺點。參考文獻(xiàn)：1 謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系 講義2 劉汝佳，黃亮， ， P601.3. 圖的遍歷 Traveling in graph1.3.1.深度優(yōu)先搜索 Depth first search (DFS).概念.2.橋一定不在圈求無向連通圖中的橋 Finding bridges in undirected graph在無向連通的條件下，邊是橋的充要條件是：1.橋一定是DFS樹中的邊; 中。的路徑上的邊都(深度最淺 )，表圈是由一條后向邊(u,v)與DFS樹中u到V的路徑組成。也就是說

40、u到V 不可能是橋，應(yīng)該給以標(biāo)記。記f(x)為x與其子孫的后向邊所連到的最老祖先 示X到f(x)上的邊均不為橋。然而維護(hù)f(x)比較麻煩，其實只要知道f(x)的拓?fù)湫驍?shù)就可以 了。所謂拓?fù)湫驍?shù)就是 滿足兒子的序數(shù)總比父親大 的一個編號方式。這個拓?fù)湫?，常用使?深度d，或者使用時間戳(TimeStamp) DFN(DFS訪問的次序)。下面以深度為例：記g(x) d(f (x)，在DFS樹中從x開始通過前向弧和后向弧所能到達(dá)的最小的d。有以下的動態(tài)規(guī)劃：d(x)g(x) min d(y) (x,y)is backforward edge, y father g(c) c is xschild .

41、這里：1. 第一次訪問 x 時，記錄 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 first search (BFS)1.4. 拓?fù)渑判?Topological sort拓?fù)渑判蚴菍τ邢驘o圈圖(DAG)頂點的一種排序，它使得如果存在 u,v的有向路徑，那么 滿足序中u在V前。拓?fù)渑判蚓褪怯梢环N偏序(partical order)得到一個全序(稱為拓?fù)溆行?(to pological order)。偏序是滿足自反性

42、，反對稱性，傳遞性的序。拓補(bǔ)排序的思路很簡單，就是每次任意找一個入度為 0 的點輸出，并把這個點以及與這 個點相關(guān)的邊刪除。實際算法中，用一個隊列實現(xiàn)。算法：1. 把所有入度 =0 的點入隊 Q。2. 若隊Q非空，則點u出隊，輸出u;否則轉(zhuǎn)4。3. 把所有與點u相關(guān)的邊(u,v)刪除，若此過程中有點V的入度變?yōu)?,則把V入隊Q， 轉(zhuǎn) 2。4. 若出隊點數(shù)VN，貝U有圈；否則輸出結(jié)果。算法復(fù)雜度 : O(m)。習(xí)題： MIPT 012 Correct dictionary設(shè)R為非空集合A上的二元關(guān)系，如果R滿足自反性(對于每一個x A , (x,x) R )，反 對稱性(x,y) RA (y,x

43、) R-x=y )和傳遞性(x,y) RA (y,x) R-(x,z) R)，則稱 R 為 A 上的 偏序關(guān)系，記作w。如果(x,y) R,則記作xm ,結(jié)束，此時G沒有生成樹；否則判斷T u是否含圈，是則轉(zhuǎn)2,否則轉(zhuǎn)3。3.T T e。若|T|=N，結(jié)束，此時T為G的最小生成樹。分離集合(disjoint set)，可用并查集實現(xiàn)。由于排序是O(mlogm)的。所以復(fù)雜度為O(mlogm ma(n)。.3. Sollin ( Boruvka)基本思想：前面介紹的兩種算法的綜合。每次迭代同時擴(kuò)展多棵子樹，直到得到最小生 成樹T。算法：1.對于所有v V,Gv V。T2.若|T|=

44、N，結(jié)束，此時T為G的最小生成樹；否則，對于T中所有的子樹集合Gv，計算它的邊割Gv,Gv中的最小弧ev (有的書稱連接兩個連通分量的最小弧“安全邊”)。3.對T中所有子樹集合Gv及其邊割最小弧ev (P,q)，將Gv與q所在的子樹集合合并。T Tev。轉(zhuǎn) 2。由于每次循環(huán)迭代時，每棵樹都會合并成一棵較大的子樹，因此每次循環(huán)迭代都會使子樹的數(shù)量至少減少一半，或者說第i次迭代每個分量大小至少為2i。所以，循環(huán)迭代的總次數(shù)為O(logn)。每次循環(huán)迭代所需要的計算時間：對于第 2步，每次檢查所有邊O(m)，去更新每個連通分量的最小弧；對于第3步，合并0(n/2)個子樹。所以總的復(fù)雜度為O(mlog

45、 n)。BaRTiVKAtVE)：T = (V0while F kaa more than one camponent diooae leaders using DFS FiNDSAPBBDaas(V, E) for each leader vadd a,afeV) to TFiwdSafbBdgb呂(畝 E): for eacL leader v aafefv) 1 oo for 遜 edge 叫巧 E u 1 leader(iL) V1 leaderfv if u* 云if wsafeiLsafeu) 1 mVlif wixv) w(Bafev) aafe(v)仏訶. 擴(kuò)展模

46、型 Extended models16121.度限制生成樹 Minimum degree-bounded spanning trees由于這個問題是NP-Hard的，一般用搜索算法解決。本文就只討論一種特殊多項式情況： 單點度限制(one node degree bounded)把度限制的點記為Vo，滿足度限制deg(vo) k。一種貪心的思路：在最小生成樹T的基礎(chǔ)上，通過添刪邊來改造樹，使之逐漸滿足度限制條件。 算法：1. 求圖的最小生成樹To2.若V0已滿足度限制，結(jié)束；否則轉(zhuǎn) 3。To3.對于刪去v0后的每一個連通分支T (為一棵樹)，求添加邊割Ti,T v。中的最小弧,刪除邊割Ti,v

47、O里的最大弧后的生成樹中的邊權(quán)和最小的一個。更新最小生成樹轉(zhuǎn)2o第3步，v的度少1o習(xí)題：NOI 2005小H的聚會.2. k 小生成樹 The k minimum spanning tree problem(k-MST)生成樹T刪除一條邊f(xié)并加入一條新邊e的操作稱為交換。若交換后的圖仍是一顆樹，則此交換稱為可行交換。若生成樹T可通過一次交換成為生成樹 T 則稱它們互為鄰樹。對于 生成樹集合S,生成樹T,若T不在S中，且在S中存在某生成樹是T的鄰樹，稱為T為S 的鄰樹。定理：設(shè)Ti,T2丄,Tk為圖的前k小生成樹，則生成圖集合Ti,T2,L ,Tk的鄰樹中的邊權(quán)和最小者可作為第

48、k+1 小生成樹 (可能有邊權(quán)和相同的情況 )。 按這個定理設(shè)計算法，很難得到有滿意的時間復(fù)雜度的算法。下面討論一個特例:次小生成樹 (The second MST, 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)|eP(u,v)。算法:1.求圖的最小生成樹T。次小生成樹T的權(quán)值的最小值w(T)。2.以每個結(jié)點為根r, DFS遍歷樹。在遍歷過程中求出f(