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

1、1.1.定義與術(shù)語(yǔ) Definition and Glossary1.1.1. 圖與網(wǎng)絡(luò) Graph and Network1.1.2. 圖的術(shù)語(yǔ) Glossary of Graph1.1.3. 路徑與回路 Path and Cycle1.1.4. 連通性 Connectivity1.1.5. 圖論中特殊的集合 Sets in graph1.1.6. 匹配 Matching1.1.7. 樹(shù) 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). 概念. 求無(wú)向連通圖中的橋 Finding bridges in undirected graph1.3.2. 廣度優(yōu)先搜索 Breadth first search (BFS).拓?fù)渑判?Topological sort1.5.2. Hamiltonian

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

4、panning trees. 基本算法 Basic algorithms.1. Prim.2. Kruskal.3. Sollin (Boruvka). 擴(kuò)展模型 Extended models.1. 度限制生成樹(shù) Minimum degree-bounded spanning trees.2. k 小生成樹(shù) 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. 有向無(wú)環(huán)圖上的最短路 Shortest paths in DAG. 所有頂點(diǎn)對(duì)間最短路 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有上下界的流問(wèn)題.2. 擴(kuò)展模型 Extended models.2.1 . 最小費(fèi)用流 Minimum cost flow.1. 找最小費(fèi)用路 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. 無(wú)權(quán)圖 -匈牙利算法 Unweighted - Hopcroft and Karp algorithm 164.12 帶權(quán)圖-KM 算法 Weighted -Kuhn-Munkres(KM) algorithm. 一般圖 General Graph.1. 無(wú)權(quán)圖-帶花樹(shù)算法 Unweighted - Blossom (Edmonds)1. 圖論 Graph Theor

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

10、;對(duì)于v來(lái)說(shuō)u,v是入邊(in comi ng arc)。反之，若邊的點(diǎn)對(duì)無(wú)序則稱(chēng)為 無(wú)向(un directed)邊，所形成的圖稱(chēng)無(wú)向圖 (undirected graph)。若圖的邊有一個(gè)權(quán)值(weight)，則稱(chēng)為賦權(quán)邊，所形成的圖稱(chēng) 賦權(quán)圖(weighted graph)或網(wǎng) 絡(luò)(network)。用三元組G(V,E,W)表示網(wǎng)絡(luò)。其中 W表示權(quán)集，它的元素與邊集 E 一一對(duì)應(yīng)。滿足|E| |V|log |V |的圖，稱(chēng)為稀疏(sp arse圖；反之，稱(chēng)為 稠密(de nse)ffl。1.1.2. 圖的術(shù)語(yǔ) Glossary of Graph階(order):圖G中頂點(diǎn)集V的大小稱(chēng)作圖

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

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

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

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

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

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

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

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

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

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

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

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

23、v V，有(u,v) E。即一個(gè)點(diǎn)集，集合中任兩個(gè)結(jié)點(diǎn)相鄰?；蛘哒f(shuō)是導(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ù)， 記為(G)。邊獨(dú)立集(edge indepen de nt set) E E，滿足對(duì)于 e, f E，有e, f不鄰接。即一個(gè)邊集，滿足邊集中的任兩邊不鄰接。 極大邊獨(dú)立集(maximal edge in de pen de nt set)：本身為邊獨(dú) 立集，再加入任何邊都不是。 最大邊獨(dú)立集(maximum edge ind

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

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

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

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

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

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

30、匹配數(shù)(matchi ng number)是最大匹配的大小。完美匹配(P erfect matchi ng)是匹配了所有點(diǎn)的匹配。完備匹配(com plete matchi ng是匹配了二分圖較小部份的所有點(diǎn)的匹配。 增廣軌定理 ：一個(gè)匹配是最大匹配當(dāng)且僅當(dāng)沒(méi)有增廣軌。綜上，在二分圖中，最小覆蓋數(shù)=最大匹配數(shù)。邊覆蓋數(shù)=最大獨(dú)立數(shù)=|V|-最大匹配數(shù)。1.1.7. 樹(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)之間存在唯一的一條路；G連通，且將G的任何一條弧刪去之后，該

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

32、 f(x)s.t. g(x) 0, x D其中D表示有限個(gè)點(diǎn)組成的集合(定義域),f為目標(biāo)函數(shù),F x|x D,g(x) 0為可行域。網(wǎng)絡(luò)優(yōu)化(network optimization)就是研究與(賦權(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 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)，來(lái)表示圖。這種表示法一般用于稠密圖。當(dāng)圖不是簡(jiǎn)單圖，鄰接矩 陣法不能用。在無(wú)權(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無(wú)權(quán)圖的例子:0000010100100110100100010在有權(quán)圖中，若邊(u,v)存在，則A(

34、u,v)為它的權(quán)值；否則人為的規(guī)定 A(u,v)= X或-是一個(gè)足夠大的數(shù)。A(au,v)n n ,au,vw(u,v),(u,v) E,(u,v) E無(wú)向圖中，鄰接矩陣是按矩陣副對(duì)角線對(duì)稱(chēng)的。1.2.2. 關(guān)聯(lián)矩陣 Incidence matrix用二元數(shù)組B(u,k)，來(lái)表示無(wú)權(quán)有向圖。一般不用這種表示法。若邊k與點(diǎn)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無(wú)權(quán)圖的例子:110001010001

35、0100110000110000110010100011123. 鄰接表 Adjacency list圖的鄰接表是圖的所有節(jié)點(diǎn)的鄰接表的集合；而對(duì)每個(gè)節(jié)點(diǎn)， 出弧的集合，含有終點(diǎn)，權(quán)值等信息。對(duì)于有向圖G=(V,E)，般用A(v)表示節(jié)點(diǎn)V的鄰接表， 合或鏈表(實(shí)際上只需要列出弧的另一個(gè)端點(diǎn)，即弧的尾 )。它的鄰接表就是它的所有即節(jié)點(diǎn)V的所有出弧構(gòu)成的集一般圖都適用。鄰接表方法增加或刪除一條弧所需的計(jì)算工作量很少。 有權(quán)圖的例子：A(1)=2,3，A(2)=4 , A(3)=2，A(4)=3,5 , A(5)=3,4終點(diǎn)權(quán)值指針起點(diǎn)1.2.4. 弧表 Arc list所謂圖的弧表，也就是圖的弧

36、集合中的所有有序?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終占k、八、22543343權(quán)值84376069125.星形表示 Star星形表示法就是對(duì)弧表的缺點(diǎn)的改進(jìn)，使之可以通過(guò)起點(diǎn)或終點(diǎn)定位邊。由于很多時(shí)候， 算法只需事先知道起點(diǎn)，通過(guò)枚舉邊擴(kuò)展，而不需要事先知道終點(diǎn)；如圖的遍歷，松弛操作。按定位方式，又分前向星形(forwards star)與反向星形(reverse star).前向星形：通過(guò)起點(diǎn) 定

37、位邊。反向星形：通過(guò)終點(diǎn)定位邊。實(shí)際上，反向星形幾乎沒(méi)用。故本文只討論前向星形。通常有兩種方法實(shí)現(xiàn)這種對(duì)弧表改進(jìn)：邊排序法，鏈表法。邊排序法：把弧表按起點(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(O)=O。這樣以結(jié)點(diǎn)u為起點(diǎn)的邊編號(hào)就是last(u-1)+1到last(u)。有權(quán)圖的例子：作為起點(diǎn)的點(diǎn)012345最后邊的編號(hào)023468編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)值89640367鏈表法：給每條邊

38、(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)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)的情況下可以精確定位邊，容易在起點(diǎn)定位的范圍內(nèi)二分查找終點(diǎn)，在反向邊的定位 中常用；缺點(diǎn)是代碼麻煩，時(shí)間抑或空間上都有額外開(kāi)銷(xiāo)。鏈表法的優(yōu)點(diǎn)很多，不僅代碼簡(jiǎn) 單，而且沒(méi)有太多的時(shí)空開(kāi)銷(xiāo)，

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

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

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

42、，反對(duì)稱(chēng)性，傳遞性的序。拓補(bǔ)排序的思路很簡(jiǎn)單，就是每次任意找一個(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)刪除，若此過(guò)程中有點(diǎn)V的入度變?yōu)?,則把V入隊(duì)Q， 轉(zhuǎn) 2。4. 若出隊(duì)點(diǎn)數(shù)VN，貝U有圈；否則輸出結(jié)果。算法復(fù)雜度 : O(m)。習(xí)題： MIPT 012 Correct dictionary設(shè)R為非空集合A上的二元關(guān)系，如果R滿足自反性(對(duì)于每一個(gè)x A , (x,x) R )，反 對(duì)稱(chēng)性(x,y) RA (y,x

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

44、N，結(jié)束，此時(shí)T為G的最小生成樹(shù)；否則，對(duì)于T中所有的子樹(shù)集合Gv，計(jì)算它的邊割Gv,Gv中的最小弧ev (有的書(shū)稱(chēng)連接兩個(gè)連通分量的最小弧“安全邊”)。3.對(duì)T中所有子樹(shù)集合Gv及其邊割最小弧ev (P,q)，將Gv與q所在的子樹(shù)集合合并。T Tev。轉(zhuǎn) 2。由于每次循環(huán)迭代時(shí)，每棵樹(shù)都會(huì)合并成一棵較大的子樹(shù)，因此每次循環(huán)迭代都會(huì)使子樹(shù)的數(shù)量至少減少一半，或者說(shuō)第i次迭代每個(gè)分量大小至少為2i。所以，循環(huán)迭代的總次數(shù)為O(logn)。每次循環(huán)迭代所需要的計(jì)算時(shí)間：對(duì)于第 2步，每次檢查所有邊O(m)，去更新每個(gè)連通分量的最小弧；對(duì)于第3步，合并0(n/2)個(gè)子樹(shù)。所以總的復(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.度限制生成樹(shù) Minimum degree-bounded spanning trees由于這個(gè)問(wèn)題是NP-Hard的，一般用搜索算法解決。本文就只討論一種特殊多項(xiàng)式情況： 單點(diǎn)度限制(one node degree bounded)把度限制的點(diǎn)記為Vo，滿足度限制deg(vo) k。一種貪心的思路：在最小生成樹(shù)T的基礎(chǔ)上，通過(guò)添刪邊來(lái)改造樹(shù)，使之逐漸滿足度限制條件。 算法：1. 求圖的最小生成樹(shù)To2.若V0已滿足度限制，結(jié)束；否則轉(zhuǎn) 3。To3.對(duì)于刪去v0后的每一個(gè)連通分支T (為一棵樹(shù))，求添加邊割Ti,T v。中的最小弧,刪除邊割Ti,v

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

48、k+1 小生成樹(shù) (可能有邊權(quán)和相同的情況 )。 按這個(gè)定理設(shè)計(jì)算法，很難得到有滿意的時(shí)間復(fù)雜度的算法。下面討論一個(gè)特例:次小生成樹(shù) (The second MST, 2-MST)基本思想：枚舉最小生成樹(shù) T 的每一個(gè)鄰樹(shù)，即枚舉被添加與被刪除的邊。由于在樹(shù)中 添加一條邊(u,v)(u,v) T )，一定形成了一個(gè)環(huán)，環(huán)是由(u,v)與從u到V的生成樹(shù)上的唯一路徑(記為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.求圖的最小生成樹(shù)T。次小生成樹(shù)T的權(quán)值的最小值w(T)。2.以每個(gè)結(jié)點(diǎn)為根r, DFS遍歷樹(shù)。在遍歷過(guò)程中求出f(