【正文】 簡單圖G中長度為奇數(shù)和偶數(shù)的圈分別稱為奇圈(odd cycle)和偶圈(even cycle)。圖G的直徑(diameter)：。. 連通性 Connectivity連通(connected)：在圖G中，兩個頂點間，至少存在一條路徑，稱兩個頂點連通的(connected)；反之，稱非連通(unconnected)。弱連通(weakly connected)：在有向圖G中，兩個頂點間，若不考慮G中邊的方向的圖才連通的，稱原有向圖為弱連通。連通分量或連通分支(connected branch, ponent)：非連通無向圖的極大連通子圖(maximally connected subgraph)。圖G的連通分支是G的一個極大連通子圖。強連通分量(strongly connected branch)：非強連通圖有向圖的極大強連通子圖。則稱點割集。點數(shù)最少的點割集稱為點連通度k(G)。則稱點割集。邊數(shù)最少的邊割集稱為邊連通度k’(G)。塊(block)是指沒有割點的極大連通子圖。即一個點集，使得所有邊至少有一個端點在集合里。極小點覆蓋(minimal vertex covering)：本身為點覆蓋，其真子集都不是。點覆蓋數(shù)(vertex covering number)：最小點覆蓋的點數(shù)，記為一般說覆蓋集就是指點覆蓋集。即一個邊集，使得所有點都與集合里的邊鄰接。 極小邊覆蓋(minimal edge covering)：本身是邊覆蓋，其真子集都不是。邊覆蓋數(shù)(edge covering number)：最小邊覆蓋的邊數(shù)，記為。即一個點集，集合中任兩個結(jié)點不相鄰，則稱為獨立集。極大獨立集(maximal independent set)：本身為獨立集，再加入任何點都不是。獨立數(shù)(independent number)：最大獨立集的點數(shù)，記為。即一個點集，集合中任兩個結(jié)點相鄰。極大團(maximal clique)：本身為團，再加入任何點都不是。團數(shù)(clique number)：最大團的點數(shù)，記為。即一個邊集，滿足邊集中的任兩邊不鄰接。最大邊獨立集(maximum edge independent set)：邊最多的邊獨立集。邊獨立集又稱匹配(matching)，相應(yīng)的有極大匹配(maximal matching)，最大匹配(maximum matching)，匹配數(shù)(matching number)。即一個點集，使得所有其他點至少有一個相鄰點在集合里。 極小支配集(minimal dominating set)：本身為支配集，其真子集都不是。支配數(shù)(dominating number)：最小支配集的點數(shù)，記為。即一個邊集，使得所有邊至少有一條鄰接邊在集合里。極小邊支配集(minimal edge dominating set)：本身是邊支配集，其真子集都不是。邊支配數(shù)(edge　dominating number)：最小邊支配集的邊數(shù)，記為。定理：一個獨立集是極大獨立集，當(dāng)且僅當(dāng)它是支配集。定理：無向圖G無孤立點，是極大獨立集，則是極小支配集。定理：連通圖中，是點覆蓋，則是支配集。支配集不一定是點覆蓋。定理：無向圖G，是G的(極，最大)團，充要于是的(極，最大)獨立集。但是二分圖中，點覆蓋數(shù)是匹配數(shù)。定理：無向圖G無孤立點，|M|=|N|,|Y|=|W|定理：無向圖G無孤立點。定理：無向圖G無孤立點，=，=。求匹配數(shù)是P的，所以邊覆蓋和匹配都是易求的。路徑的長度可能為0(單個點)。應(yīng)該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個頂點相交。然后根據(jù)原圖中邊的信息，從X部往Y部引邊。因此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。. 匹配 Matching匹配(matching)是一個邊集，滿足邊集中的邊兩兩不鄰接。在匹配中的點稱為匹配點(matched vertex)或飽和點；反之，稱為未匹配點(unmatched vertex)或未飽和點。 增廣軌(augmenting path)：是一個始點與終點都為未匹配點的交錯軌。匹配數(shù)(matching number)是最大匹配的大小。完備匹配(plete matching)是匹配了二分圖較小部份的所有點的匹配。綜上，在二分圖中，最小覆蓋數(shù)=最大匹配數(shù)。. 樹 TreeG=(V, E)為一個圖，則下列命題等價：(1)G是一棵樹；(2)G連通，且|E|=|V|1；(3)G無圈，且|E|=|V|1；(4)G的任何兩個頂點之間存在唯一的一條路；(5)G連通，且將G的任何一條弧刪去之后，該圖成為非連通圖；(6)G無圈，且在G的任何兩個不相鄰頂點之間加入一條弧之后，該圖正好含有一個圈。. 組合優(yōu)化 Combinatorial optimization從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為(最)優(yōu)化(optimization)問題。網(wǎng)絡(luò)優(yōu)化(network optimization)就是研究與(賦權(quán))圖有關(guān)的組合優(yōu)化問題。常見的NP類網(wǎng)絡(luò)優(yōu)化問題：旅行商問題。并統(tǒng)一用下圖做例子：1234512378654. 鄰接矩陣 Adjacency matrix用二元數(shù)組，來表示圖。當(dāng)圖不是簡單圖，鄰接矩陣法不能用。無權(quán)圖的例子：在有權(quán)圖中, 若邊存在,則為它的權(quán)值；否則人為的規(guī)定=∞或∞。無向圖中，鄰接矩陣是按矩陣副對角線對稱的。一般不用這種表示法。無權(quán)圖的例子：. 鄰接表 Adjacency list圖的鄰接表是圖的所有節(jié)點的鄰接表的集合；而對每個節(jié)點，它的鄰接表就是它的所有出弧的集合，含有終點，權(quán)值等信息。一般圖都適用。有權(quán)圖的例子：A(1)={2,3}，A(2)={4}，A(3)={2}，A(4)={3,5}，A(5)={3,4}12345283904602403053036470終點權(quán)值指針起點. 弧表 Arc list所謂圖的弧表, 也就是圖的弧集合中的所有有序?qū)σ员砀竦姆绞絹肀硎?。一般用于稀疏圖。用S(i),F(i),W(i)分別表示起點，終點，權(quán)值。由于很多時候，算法只需事先知道起點，通過枚舉邊擴展，而不需要事先知道終點；如圖的遍歷，松弛操作。前向星形：通過起點定位邊。實際上，反向星形幾乎沒用。通常有兩種方法實現(xiàn)這種對弧表改進：邊排序法，鏈表法。排序用不用額外空間的快速排序O(mlogm)或用額外空間O(m)的計數(shù)排序O(m)均可。這樣以結(jié)點u為起點的邊編號就是last(u1)+1到last(u)。直觀的講，就是將相同結(jié)點的邊用鏈表串起來。有權(quán)圖的例子：作為起點的點12345最后邊的編號65278編號012345678起點nil53412145終點nil42524333權(quán)值nil74386906前趨nil00000431星形表示法的優(yōu)點是占用的存貯空間較少。邊排序法的優(yōu)點是已知起點和終點的情況下可以精確定位邊，容易在起點定位的范圍內(nèi)二分查找終點，在反向邊的定位中常用；缺點是代碼麻煩，時間抑或空間上都有額外開銷。參考文獻：[1]謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系網(wǎng)絡(luò)優(yōu)化講義~jxie/courses/netopt[2]劉汝佳，黃亮，算法藝術(shù)與信息學(xué)競賽，P60. 圖的遍歷 Traveling in graph. 深度優(yōu)先搜索 Depth first search (DFS). 概念. 求無向連通圖中的橋 Finding bridges in undirected graph在無向連通的條件下，邊是橋的充要條件是：；。也就是說u到v的路徑上的邊都不可能是橋，應(yīng)該給以標(biāo)記。然而維護f(x)比較麻煩，其實只要知道f(x)的拓?fù)湫驍?shù)就可以了。這個拓?fù)湫?，常用使用深度d，或者使用時間戳(TimeStamp) DFN（DFS訪問的次序）。有以下的動態(tài)規(guī)劃：這里：，記錄d(x)2. d(y)自己發(fā)出去的后向邊所達到的深度。最后，若g(x)=d(x)，即(father,x)不在圈中，則(father, x)就是橋。拓?fù)渑判蚓褪怯梢环N偏序(partical order)得到一個全序(稱為拓?fù)溆行?topological order))。拓補排序的思路很簡單，就是每次任意找一個入度為0的點輸出，并把這個點以及與這個點相關(guān)的邊刪除。算法：1. 把所有入度=0的點入隊Q。3. 把所有與點u相關(guān)的邊(u,v)刪除，若此過程中有點v的入度變?yōu)?，則把v入隊Q，轉(zhuǎn)2。算法復(fù)雜度: O(m)。如果(x,y)∈R，則記作x≤y，讀作“x小于等于y”。拓?fù)渑判虻挠嫈?shù)。. 路徑與回路 Paths and circuits . 歐拉路徑或回路 Eulerian path對于連通的可重邊的圖G，若存在一回路，它通過G的所有邊一次且僅一次，則這回路稱為歐拉路徑或回路。nigsberg Bridges下面討論有向性：. 無向圖習(xí)題：Ural 1124 Mosaic. 有向圖習(xí)題：CEOI 2005 Depot Rearrangement. 混合圖混合圖是指有的邊是有向的，有的邊是無向的圖。見LRJ P324。由于每邊至少遍歷一次，所以最短路的瓶頸就在于重復(fù)遍歷。所以問題就等價于找一個奇點構(gòu)成的完全圖G’(V,E)的最小權(quán)匹配(Perfect Matching in General Graph)。算法：1. 確定G中的奇點，構(gòu)成G’。3. 對G’進行最小權(quán)匹配。5. 對G’’找一條歐拉路即可。. Hamiltonian Cycle 哈氏路徑與回路分支限界搜索模擬退火. 無權(quán)圖 Unweighted. 有權(quán)圖 Weighed — 旅行商問題The travelling salesman problem動態(tài)規(guī)劃. 網(wǎng)絡(luò)優(yōu)化 Network optimization. 最小生成樹 Minimum spanning trees最小生成樹是指連通圖中所有生成樹中邊權(quán)和最小的一個。每次增加一條邊，使得這條邊是由當(dāng)前子樹結(jié)點集及其補集所形成的邊割集的最小邊。算法：1. ,d()=0 (這里是任意一個結(jié)點),2. 若，則結(jié)束；否則，轉(zhuǎn)3。更新與相鄰的結(jié)點的d值，即若，則，轉(zhuǎn)2。假設(shè)用Fibonacci Heap實現(xiàn)(刪除最小O(logn)，減值O(1))，算法復(fù)雜度：。每次將一條權(quán)最小的邊加入子圖T中，并保證不形成圈。算法：1. ，將E中的邊按權(quán)從小到大排序。3. 。 分離集合(disjoint set)，可用并查集實現(xiàn)