圖論總結(jié)(超強(qiáng)大)（精）.doc

圖論總結(jié)(超強(qiáng)大)（精） V為結(jié)點(diǎn)結(jié)點(diǎn)(node)或頂點(diǎn)頂點(diǎn)(vertex)集。 E為V中結(jié)點(diǎn)之間的邊的集合。 點(diǎn)對?,u v稱為邊邊(edge)或稱弧弧(arc)，其中,u v V?，稱,u v是相鄰相鄰的(adjacent)，稱u,v與邊?,u v相關(guān)聯(lián)關(guān)聯(lián)(incident)或相鄰。 若邊的點(diǎn)對?,u v有序則稱為有向有向(directed)邊，其中u稱為頭頭(head)，v稱為尾尾(tail)。 所形成的圖稱有向圖有向圖(directedgraph)。 為對于u來說?,u v是出邊出邊(outgoing arc)；對于v來說?,u v是入邊入邊(ining arc)。 反之，若邊的點(diǎn)對無序則稱為無向(undirected graph)。 若圖的邊有一個(gè)權(quán)值權(quán)值(weight)，則稱為賦權(quán)邊，所形成的圖稱賦權(quán)圖絡(luò)絡(luò)(work)。 用三元組G(V,E,W)表示網(wǎng)絡(luò)。 其中W表示權(quán)集，它的元素與邊集E一一對應(yīng)。 無向(undirected)邊，所形成的圖稱無向圖無向圖賦權(quán)圖(weighted graph)或網(wǎng)網(wǎng)滿足|?|log|EVV的圖，稱為稀疏稀疏(sparse)圖；反之，稱為稠密稠密(dense)圖。 1.1.2.圖的術(shù)語圖的術(shù)語Glossary ofGraph階階(order)圖G中頂點(diǎn)集V的大小稱作圖G的階。 環(huán)環(huán)(loop)若一條邊的兩個(gè)頂點(diǎn)為同一頂點(diǎn)，則此邊稱作環(huán)。 簡單圖簡單圖(simple graph)沒有環(huán)、且沒有多重弧的圖稱作簡單圖。 定向圖定向圖對無向圖G的每條無向邊指定一個(gè)方向得到的有向圖。 底圖底圖把一個(gè)有向圖的每一條有向邊的方向都去掉得到的無向圖。 逆圖逆圖把一個(gè)有向圖的每條邊都反向由此得到的有向圖。 競賽圖競賽圖(tournament)有向圖的底圖是無向完全圖，則此有向圖是競賽圖。 鄰域鄰域(neighborhood)在圖中與u相鄰的點(diǎn)的集合|,(,)v v V u v?E?，稱為u的鄰域，記為()N u。 度度度(degree)一個(gè)頂點(diǎn)的度是指與該邊相關(guān)聯(lián)的邊的條數(shù)，頂點(diǎn)v的度記作deg(v)。 握手定理無向圖deg()2|v V?vE?；有向圖deg()deg()v V?v V?vv?。 入度入度(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)孤立點(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)奇點(diǎn)(odd vertex)度為奇數(shù)的點(diǎn)。 偶點(diǎn)子圖偶點(diǎn)(even vertex)度為偶數(shù)的點(diǎn)。 子圖子圖(sub-graph)G稱作圖G的子圖如果()()V GV G?以及()E G()E G?。 生成子圖生成子圖(spanning sub-graph)即包含G的所有頂點(diǎn)的連通子圖，即滿足條件()V G()V G?的G的子圖G。 生成樹生成樹(spanningtree)設(shè)T是圖G的一個(gè)子圖，如果T是一棵樹，且()()V TV G?，則稱T是G的一個(gè)生成樹。 即G的生成子圖，且子圖為樹。 點(diǎn)導(dǎo)出子圖點(diǎn)導(dǎo)出子圖(induced subgraph)設(shè))(GVV?，以V?為頂點(diǎn)集，以兩端點(diǎn)均在V?中的邊的全體為邊集所組成的子圖，稱為G的由頂點(diǎn)集V?導(dǎo)出的子圖，簡稱為G的點(diǎn)導(dǎo)出子圖，記為G V?。 邊導(dǎo)出子圖邊導(dǎo)出子圖(edge-induced subgraph)設(shè))(GEE?，以E?為頂點(diǎn)集，以兩端點(diǎn)均在E?中的邊的全體為邊集所組成的子圖，稱為G的由邊集E?導(dǎo)出的子圖，簡稱為G的邊導(dǎo)出子圖，記為EG?。 圖的補(bǔ)圖圖的補(bǔ)圖(plement)設(shè)G是一個(gè)圖，以)(GV為頂點(diǎn)集，以(,)|(,)()E Gu vu v?為邊集的圖稱為G的補(bǔ)圖，記為G。 點(diǎn)集的補(bǔ)集點(diǎn)集的補(bǔ)集記VVV?為點(diǎn)集V的補(bǔ)集。 特殊的圖零圖零圖(null graph)E?，即只有孤立點(diǎn)的圖。 n階零圖記為nN。 平凡圖平凡圖(trivial graph)一階零圖。 空圖空圖(empty graph)VE?的圖。 有向無環(huán)圖有向無環(huán)圖(directed acyclicgraph(DAG)有向的無環(huán)的圖。 完全圖完全圖(plete graph)完全圖是指每一對不同頂點(diǎn)間都有邊相連的的無向圖，n階完全圖常記作nK。 二分圖二分圖（bipartite graph）若圖G的頂點(diǎn)集可劃分為兩個(gè)非空子集X和Y，即V且XY?，且每一條邊都有一個(gè)頂點(diǎn)在X中，而另一個(gè)頂點(diǎn)在Y中，那么這樣的圖稱作二分圖。 完全二分圖完全二分圖(plete bipartitegraph)二分圖G中若任意兩個(gè)X和Y中的頂點(diǎn)都有邊相XY?連，則這樣的圖稱作完全二分圖。 若|,|Xm Yn?，則完全二分圖G記作,m nK。 正則圖正則圖(regular graph)如果圖中所有頂點(diǎn)的度皆相等，則此圖稱為正則圖。 1.1.3.路徑與回路路徑與回路Path andCycle途徑途徑(walk)圖G中一個(gè)點(diǎn)邊交替出現(xiàn)的序列?。 01i1i2kkiiiipv ev eev?，滿足,jjiivV eE?，1(,)jjjiiievv?跡跡(trail)邊不重復(fù)的途徑。 路路(path)頂點(diǎn)不重復(fù)的跡。 簡單圖中的路可以完全用頂點(diǎn)來表示，kiiivvvP?10?。 若1mpp?，稱閉閉的(closed)；反之，稱為開開的(open)。 閉途徑閉途徑(closed walk)起點(diǎn)和終點(diǎn)相同的途徑。 閉跡閉跡(closed trail)起點(diǎn)和終點(diǎn)相同的跡，也稱為回路回路(circuit)。 圈圈(cycle)起點(diǎn)和終點(diǎn)相同的路。 途徑（閉途徑）、跡（閉跡）、路（圈）上所含的邊的個(gè)數(shù)稱為它的長度簡單圖G中長度為奇數(shù)和偶數(shù)的圈分別稱為奇圈長度(length)。 奇圈(odd cycle)和偶圈偶圈(even cycle)。 對任意,()u v VG?，從x到y(tǒng)的具有最小長度的路稱為x到y(tǒng)的最短路最短路(shortestpath)，其長度稱為x到y(tǒng)的距離距離(distance)，記為(,)u v。 Gd圖G的直徑直徑(diameter)max(,)|u v,()GDdu vVG?。 簡單圖G中最短圈的長度稱為圖G的圍長(perimeter)。 圍長(girth)，最長圈的長度稱為圖G的周長周長1.1.4.連通性連通性Connectivity連通連通(connected)在圖G中，兩個(gè)頂點(diǎn)間，至少存在一條路徑，稱兩個(gè)頂點(diǎn)連通的(connected)；反之，稱非連通強(qiáng)連通強(qiáng)連通(strongly connected)在有向圖G中，兩個(gè)頂點(diǎn)間，至少存在一條路徑，稱兩個(gè)頂點(diǎn)強(qiáng)連通。 弱連通弱連通(weakly connected)在有向圖G中，兩個(gè)頂點(diǎn)間，若不考慮G中邊的方向的圖才連通的，稱原有向圖為弱連通。 連通圖連通圖(connected graph)圖G中任二頂點(diǎn)都連通。 連通分量連通分量或連通分支連通分支(connected branch,ponent)非連通無向圖的極大連通子圖(maximally connected sub-graph)。 具體說，若圖G的頂點(diǎn)集V(G)可劃分為若干非空子集非連通(unconnected)。 ?VVV,21?，使得兩頂點(diǎn)屬于同一子集當(dāng)且僅當(dāng)它們在G中連通，則稱每個(gè)子圖iVG為圖G的一個(gè)連通分支（?,2,1?i）。 圖G的連通分支是G的一個(gè)極大連通子圖。 圖G連通當(dāng)且僅當(dāng)1?。 強(qiáng)連通分量強(qiáng)連通分量(strongly connectedbranch)非強(qiáng)連通圖有向圖的極大強(qiáng)連通子圖。 割(cut)點(diǎn)割集點(diǎn)割集(vertex cut)點(diǎn)集VV?，若G刪除了G仍然連通。 則稱V點(diǎn)割集。 若某一結(jié)點(diǎn)就構(gòu)成就了點(diǎn)割集，則稱此結(jié)點(diǎn)割點(diǎn)點(diǎn)數(shù)最少的點(diǎn)割集稱為點(diǎn)連通度點(diǎn)連通度k(G)。 邊割集邊割集(edge cutset)邊集EE?，若G刪除了后G仍然連通。 則稱E點(diǎn)割集。 若某一邊就構(gòu)成就了邊割集，則稱此結(jié)點(diǎn)割邊(bridge)。 邊數(shù)最少的邊割集稱為邊連通度邊連通度k(G)。 割V后不連通，但刪除了V的任意真子集后割點(diǎn)(cut vertex)。 E后不連通，但刪除了E的任意真子集割邊(cut edge)或橋橋記號,SS?表示一端在S中另一端在S?中的所有邊的集合。 塊塊(block)是指沒有割點(diǎn)的極大連通子圖。 1.1.5.圖論中特殊的集合圖論中特殊的集合Sets ingraph點(diǎn)覆蓋點(diǎn)覆蓋(集個(gè)點(diǎn)集，使得所有邊至少有一個(gè)端點(diǎn)在集合里。 或者說是“點(diǎn)”覆蓋了所有“邊”。 極小點(diǎn)覆蓋覆蓋(minimal vertex covering)本身為點(diǎn)覆蓋，其真子集都不是。 最小點(diǎn)覆蓋集)(vertex covering(set)VV?，滿足對于eE?，有vV?，v關(guān)聯(lián)e。 即一極小點(diǎn)最小點(diǎn)覆蓋(minimum vertexcovering)點(diǎn)最少的點(diǎn)覆蓋。 點(diǎn)覆蓋數(shù)點(diǎn)覆蓋數(shù)(vertexcoveringnumber)最小點(diǎn)覆蓋的點(diǎn)數(shù)，記為()VG?一般說覆蓋集就是指點(diǎn)覆蓋集。 邊覆蓋邊覆蓋(集集)(edge covering(set)邊集，使得所有點(diǎn)都與集合里的邊鄰接。 或者說是“邊”覆蓋了所有“點(diǎn)”。 極小邊覆蓋(minimal edge covering)本身是邊覆蓋，其真子集都不是。 最小邊覆蓋EE?，滿足對于vV?，有eE?，e關(guān)聯(lián)v。 即一個(gè)極小邊覆蓋最小邊覆蓋(minimum edgecovering)邊最少的邊覆蓋。 邊覆蓋數(shù)邊覆蓋數(shù)(edgecoveringnumber)最小邊覆蓋的邊數(shù)，記為()EG?。 獨(dú)立集獨(dú)立集(independent set)VV?，滿足對于,u vV?，有(,)u vE?。 即一個(gè)點(diǎn)集，集合中任兩個(gè)結(jié)點(diǎn)不相鄰，則稱大獨(dú)立集大獨(dú)立集(maximal independent set)本身為獨(dú)立集，再加入任何點(diǎn)都不是。 最大獨(dú)立集(maximum independent set)點(diǎn)最多的獨(dú)立集。 獨(dú)立數(shù)V為獨(dú)立集。 或者說是導(dǎo)出的子圖是零圖（沒有邊）的點(diǎn)集。 極極最大獨(dú)立集獨(dú)立數(shù)(independent number)最大獨(dú)立集的點(diǎn)數(shù)，記為()VG?。 團(tuán)團(tuán)(clique)VV?，滿足對于,u vV?，有(,)u vE?。 即一個(gè)點(diǎn)集，集合中任兩個(gè)結(jié)點(diǎn)相鄰。 或者說是導(dǎo)出的子圖是完全圖的點(diǎn)集。 極大團(tuán)何點(diǎn)都不是。 最大團(tuán)最大團(tuán)(maximum clique)點(diǎn)最多的團(tuán)。 團(tuán)數(shù)極大團(tuán)(maximal clique)本身為團(tuán)，再加入任團(tuán)數(shù)(clique number)最大團(tuán)的點(diǎn)數(shù)，記為()?G。 邊獨(dú)立集邊獨(dú)立集(edge independent set)EE?，滿足對于,e fE?，有,e f不鄰接。 即一個(gè)邊集，滿足邊集中的任兩邊不鄰接。 極大邊獨(dú)立集立集，再加入任何邊都不是。 最大邊獨(dú)立集極大邊獨(dú)立集(maximal edge independentset)本身為邊獨(dú)最大邊獨(dú)立集(maximum edgeindependentset)邊最多的邊獨(dú)立集。 邊獨(dú)立數(shù)邊獨(dú)立數(shù)(edgeindependentnumber)最大邊獨(dú)立集的邊數(shù)，記為()EG?。 邊獨(dú)立集又稱匹配matching)，匹配數(shù)匹配(matching)，相應(yīng)的有極大匹配匹配數(shù)(matching number)。 極大匹配(maximal matching)，最大匹配最大匹配(maximum支配集支配集(dominating set)VV?，滿足對于uVV?，有vV?，(,)u vE?。 即一個(gè)點(diǎn)集，使得所有其他點(diǎn)至少有一個(gè)相鄰點(diǎn)在集合里。 或者說是一部分的“點(diǎn)”支配了所有“點(diǎn)”。 極小支配集極小支配集(minimal dominating set)本身為支配集，其真子集都不是。 最小支配集最小支配集(minimum dominating set)點(diǎn)最少的支配集。 支配數(shù)支配數(shù)(dominating number)最小支配集的點(diǎn)數(shù)，記為()VG?。 邊支配集邊支配集(edge dominatingset)EE?，滿足對于eEE?，有fE?，,e f鄰接。 即一個(gè)邊集，使得所有邊至少有一條鄰接邊在集合里。 或者說是一部分的“邊”支配了所有“邊”。 極小邊支配集極小邊支配集(minimal edge dominatingset)本身是邊支配集，其真子集都不是。 最小邊支配集集(minimum edgedominatingset)邊最少的邊支配集。 邊支配數(shù)最小邊支配邊支配數(shù)(edgedominatingnumber)最小邊支配集的邊數(shù)，記為()EG?。 定理若G中無孤立點(diǎn)，D為支配集，則D=V(G)-D也是一個(gè)支配集。 定理一個(gè)獨(dú)立集是極大獨(dú)立集，當(dāng)且僅當(dāng)它是支配集。 關(guān)系定理無向圖G無孤立點(diǎn)，1V是極小支配集，則存在2V是極小支配集，且12VV?。 定理無向圖G無孤立點(diǎn)，V是極大獨(dú)立集，則V是極小支配集。 逆命題不成立。 ()G()GVV?。 定理連通圖中，集不一定是點(diǎn)覆蓋。 定理無向圖G無孤立點(diǎn)，V是點(diǎn)覆蓋，則V是支配集。 極小點(diǎn)覆蓋不一定是極小支配集。 支配V是(極，最小)點(diǎn)覆蓋，充要于VV?是(極，最大)獨(dú)立集。 ()G()|G|VVV?。 定理無向圖G，V是G的(極，最大)團(tuán)，充要于V是G的(極，最大)獨(dú)立集。 ()()GVG?。 由上述定理知，()VG?，()VG?，()?G三者互相確定，但都是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()|G|EEV?。 先取一個(gè)最大匹配M，1條邊蓋兩個(gè)點(diǎn)；剩下的一個(gè)未蓋點(diǎn)要用一條邊來覆蓋，邊覆蓋數(shù)=|M|+(|V|-2|M|)=|V|-|M|。 定理無向圖G無孤立點(diǎn)，()EG?=()VG?，()VG?=()EG?。 定理無向圖G無孤立點(diǎn)，()G?=()VG?。 求匹配數(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部引邊。 所有邊的方向都是由X部到Y(jié)部。 因此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。 因此由最小路徑覆蓋數(shù)原圖G的頂點(diǎn)數(shù)二分圖的最大匹配數(shù)便可以得解。 1.1.6.匹配匹配Matching匹配匹配(matching)是一個(gè)邊集，滿足邊集中的邊兩兩不鄰接。 匹配又稱邊獨(dú)立集independentset)。 在匹配中的點(diǎn)稱為匹配點(diǎn)匹配點(diǎn)(matched vertex)或飽和點(diǎn)；反之，稱為未匹配點(diǎn)或未飽和點(diǎn)。 交錯(cuò)軌交錯(cuò)軌(alternating path)是圖的一條簡單路徑，滿足任意相鄰的兩條邊，一條在匹配內(nèi)，一條不在匹配內(nèi)。 增廣軌增廣軌(augmenting path)是一個(gè)始點(diǎn)與終點(diǎn)都為未匹配點(diǎn)的交錯(cuò)軌。 最大匹配最大匹配(maximum matching)是具有最多邊的匹配。 匹配數(shù)匹配數(shù)(matching number)是最大匹配的大小。 完美匹配完美匹配(perfect matching)是匹配了所有點(diǎn)的匹配。 完備匹配完備匹配(plete matching)是匹配了二分圖較小部份的所有點(diǎn)的匹配。 增廣軌定理增廣軌定理一個(gè)匹配是最大匹配當(dāng)且僅當(dāng)沒有增廣軌。 綜上，在二分圖中，最小覆蓋數(shù)在二分圖中，最小覆蓋數(shù)=最大匹配數(shù)。 邊覆蓋數(shù)最大匹配數(shù)。 邊覆蓋數(shù)=最大獨(dú)立數(shù)邊獨(dú)立集(edge未匹配點(diǎn)(unmatched vertex)最大獨(dú)立數(shù)=|V|-最大匹配數(shù)。 最大匹配數(shù)。 1.1.7.樹樹Tree G=(V,E)為一個(gè)圖，則下列命題等價(jià) (1)G是一棵樹； (2)G連通，且|E|=|V|-1； (3)G無圈，且|E|=|V|-1； (4)G的任何兩個(gè)頂點(diǎn)之間存在唯一的一條路； (5)G連通，且將G的任何一條弧刪去之后，該圖成為非連通圖； (6)G無圈，且在G的任何兩個(gè)不相鄰頂點(diǎn)之間加入一條弧之后，該圖正好含有一個(gè)圈。 Cayley公式在n階完全圖nK中，不同生成樹的個(gè)數(shù)為2nn?。 1.1.8.組合優(yōu)化組合優(yōu)化Combinatorial optimization從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最)優(yōu)化優(yōu)化(optimization)問題。 所謂組合組合(最最)優(yōu)化優(yōu)化(binatorial optimization)又稱離散優(yōu)化過數(shù)學(xué)方法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等.這類問題可用數(shù)學(xué)模型描述為(最離散優(yōu)化(discrete optimization)，它是通min().()st g x0,f xxD?其中D表示有限個(gè)點(diǎn)組成的集合(定義域)，f為目標(biāo)函數(shù),|x x,()D gx0F?為可行域。 網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化(work optimization)就是研究與(賦權(quán))圖有關(guān)的組合優(yōu)化問題。 常見的P類網(wǎng)絡(luò)優(yōu)化問題最小生成樹，最短路，最大流，最小費(fèi)用最大流，最大匹配，中國郵路問題。 常見的NP類網(wǎng)絡(luò)優(yōu)化問題旅行商問題。 參考文獻(xiàn)1Dictionary ofAlgorithms andData StructuresNIST，.nist/dads/2Wikipedia，en.wikipedia/wiki/Graph_theory3謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系講義faculty.math.tsinghua./jxie/courses/opt1.2.圖的表示圖的表示Expressions ofgraph下面介紹幾種表示圖的數(shù)據(jù)結(jié)構(gòu)。 并統(tǒng)一用下圖做例子1.2.1.鄰接矩陣鄰接矩陣Adjacency matrix用二元數(shù)組(,)A u v，來表示圖。 這種表示法一般用于稠密圖。 當(dāng)圖不是簡單圖，鄰接矩陣法不能用。 在無權(quán)圖中，若邊(,)u v存在，(,)A u v=1；否則(,)A u v=0。 ,0,1,?(,)(,)u v()0,1,n n?u vn nau vu vEEAa?無權(quán)圖的例子0000010100100110100100010?在有權(quán)圖中,若邊(,)u v存在,則(,)A u v為它的權(quán)值；否則人為的規(guī)定(,)A u v=或-。 是一個(gè)足夠大的數(shù)。 ,(,),(,)(,)u v(),u vn nau vw u vu vEEAa?無向圖中，鄰接矩陣是按矩陣副對角線對稱的。 1.2.2.關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣Incidence matrix用二元數(shù)組(,)B u k，來表示無權(quán)有向圖。 一般不用這種表示法。 若邊k與點(diǎn)u關(guān)聯(lián)，若k是u的出邊，則(,)B u k=1；若k是u的入邊(,)B uk=-1；否則1234512378654(,)B uk=0。 ,1,(,)(,)v u?,()1,0,1?,1,0,n m?u knm?u kvV kvV kelseu vEBbbE?，無權(quán)圖的例子1?10?010?0?00?0001?00?000?1100011001100110011011?1.2.3.鄰接表鄰接表Adjacency 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,41.2.4.弧表弧表Arc list所謂圖的弧表,也就是圖的弧集合中的所有有序?qū)σ员砀竦姆绞絹肀硎尽?弧表表示法直接列出所有弧的起點(diǎn)和終點(diǎn)，以及權(quán)值。 一般用于稀疏圖。 缺點(diǎn)是無法通過一些信息(起點(diǎn)，終點(diǎn))定位一條邊。 12345283904602403053036470終點(diǎn)權(quán)值指針起點(diǎn)用S(i),F(i),W(i)分別表示起點(diǎn)，終點(diǎn)，權(quán)值。 有權(quán)圖的例子起點(diǎn)13終點(diǎn)22權(quán)值844535475364302461391.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í)際上，反向星形幾乎沒用。 故本文只討論前向星形。 通常有兩種方法實(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)圖的例子鏈表法給每條邊(u,v)加一個(gè)前趨，表示以u為起點(diǎn)的邊鏈表的前一條邊。 直觀的講，就是將相同結(jié)點(diǎn)的邊用鏈表串起來。 last(u)存以u為起點(diǎn)的最后一條邊的編號。 有權(quán)圖的例子作為起點(diǎn)的點(diǎn)0最后邊的編號01223344658編號起點(diǎn)1終點(diǎn)2權(quán)值812139324643245430645375368547作為起點(diǎn)的點(diǎn)1最后邊的編號625324758編號0起點(diǎn)nil終點(diǎn)nil權(quán)值nil前趨nil1547023240345304128052460613947430385361星形表示法的優(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)定位性，幾乎沒缺點(diǎn)。 參考文獻(xiàn)1謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系講義faculty.math.tsinghua./jxie/courses/opt2劉汝佳，黃亮，P601.3.圖的遍歷圖的遍歷Traveling ingraph1.3.1.深度優(yōu)先搜索深度優(yōu)先搜索Depth firstsearch(DFS)1.3.1.1.概念概念1.3.1.2.求無向連通圖中的橋求無向連通圖中的橋Finding bridgesin undirectedgraph在無向連通的條件下，邊是橋的充要條件是1.橋一定是DFS樹中的邊；2.橋一定不在圈中。 圈是由一條后向邊(u,v)與DFS樹中u到v的路徑組成。 也就是說u到v的路徑上的邊都不可能是橋，應(yīng)該給以標(biāo)記。 記f(x)為x與其子孫的后向邊所連到的最老祖先與其子孫的后向邊所連到的最老祖先(深度最淺)，表示x到f(x)上的邊均不為橋。 然而維護(hù)f(x)比較麻煩，其實(shí)只要知道f(x)的拓?fù)湫驍?shù)了。 所謂拓?fù)湫驍?shù)就是滿足兒子的序數(shù)總比父親大滿足兒子的序數(shù)總比父親大的一個(gè)編號方式。 這個(gè)拓?fù)湫颍Ｓ檬褂蒙疃萪，或者使用時(shí)間戳(TimeStamp)DFN（DFS訪問的次序）。 下面以深度為例拓?fù)湫驍?shù)就可以記()gx()d fx?，在DFS樹中從x開始通過前向弧和后向弧所能到達(dá)的最小的d。 有以下的動態(tài)規(guī)劃()()()g c()g xmin(,)x yis backforwardedge ycis xs child,.d xdyfather?這里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)先搜索廣度優(yōu)先搜索Breadth firstsearch(BFS)1.4.拓?fù)渑判蛲負(fù)渑判騎opological 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)刪除，若此過程中有點(diǎn)v的入度變?yōu)?，則把v入隊(duì)Q，轉(zhuǎn)2。 4.若出隊(duì)點(diǎn)數(shù) 算法復(fù)雜度:O(m)。 習(xí)題MIPT012Correct dictionary設(shè)R為非空集合A上的二元關(guān)系，如果R滿足自反性(對于每一個(gè)xA，(x,x)R)，反對稱性(x,y)R(y,x)Rx=y)和傳遞性(x,y)R(y,x)R(x,z)R)，則稱R為A上的偏序關(guān)系，記作。 如果(x,y)R，則記作xy，讀作“x小于等于y”。 存在偏序關(guān)系的集合A稱為偏序集偏序集(partical order)。 拓?fù)渑判虻挠?jì)數(shù)。 ？AOV(activity onvertex work)AOE(activity onedge work)，其中頂點(diǎn)表示事件event，權(quán)表示時(shí)間。 1.5.路徑與回路路徑與回路Paths andcircuits1.5.1.歐拉路徑或回路歐拉路徑或回路Eulerian path對于連通的可重邊的圖G，若存在一回路，它通過G的所有邊一次且僅一次，則這回路稱為歐拉路徑或回路。 著名的問題The K?nigsberg Bridges下面討論有向性1.5.1.1.無向圖無向圖習(xí)題Ural1124Mosaic1.5.1.2.有向圖有向圖習(xí)題CEOIxxDepot Rearrangement1.5.1.3.混合圖混合圖混合圖是指有的邊是有向的，有的邊是無向的圖。 由于無向邊只能經(jīng)過一次，所以不能拆成兩條方向相反的有向邊，只能給無向邊定向，使得定向后的圖滿足“入度等于出度”。 見LRJ P324。 下面討論在有權(quán)性上的擴(kuò)展1.5.1.4.無權(quán)圖無權(quán)圖Unweighted1.5.1.5.有權(quán)圖有權(quán)圖Weighed中國郵路問題中國郵路問題The Chinesepost problem這就是一個(gè)經(jīng)典的問題中國郵路問題給出一個(gè)連通的無向的可重邊的有權(quán)圖G，求最短的回路，使得每邊至少遍歷1次。 由于每邊至少遍歷一次，所以最短路的瓶頸就在于重復(fù)遍歷。 由于圖一直保持連通性，所以兩兩奇點(diǎn)之間都存在歐拉路；又兩兩奇點(diǎn)之間的最短路可求；奇點(diǎn)個(gè)數(shù)為偶數(shù)。 所以問題就等價(jià)于找一個(gè)奇點(diǎn)構(gòu)成的完全圖G(V,E)的最小權(quán)匹配(Perfect Matchingin GeneralGraph)。 V(G)為原圖G中的奇點(diǎn)，每條邊為兩奇點(diǎn)對應(yīng)原圖的最短路長度。 算法1.確定G中的奇點(diǎn)，構(gòu)成G。 2.確定G兩兩結(jié)點(diǎn)在G中的最短路作為它們在G中的邊權(quán)。 3.對G進(jìn)行最小權(quán)匹配。 4.最小權(quán)匹配里的各匹配邊所對應(yīng)的路徑在G中被重復(fù)遍歷一次,得到歐拉圖G。 5.對G找一條歐拉路即可。 有向的中國郵路問題，比較復(fù)雜。 1.5.2.Hamiltonian Cycle哈氏路徑與回路哈氏路徑與回路分支限界搜索模擬退火1.5.2.1.無權(quán)圖無權(quán)圖Unweighted1.5.2.2.有權(quán)圖有權(quán)圖Weighed旅行商問題旅行商問題The travellingsalesman problem動態(tài)規(guī)劃1.6.網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化Network optimization1.6.1.最小生成樹最小生成樹Minimum spanningtrees最小生成樹是指連通圖中所有生成樹中邊權(quán)和最小的一個(gè)。 即求G的一棵生成樹T，使得()minT()e T?w Tw e?1.6.1.1.基本算法基本算法Basic algorithms1.6.1.1.1.Prim基本思想不斷擴(kuò)展一棵子樹(,S E),TEE?，直到S包括原圖的全部頂點(diǎn)，得到最小生成樹T。 每次增加一條邊，使得這條邊是由當(dāng)前子樹結(jié)點(diǎn)集S及其補(bǔ)集S所形成的邊割集的最小邊。 令d(v)為v到結(jié)點(diǎn)集S的最小距離。 算法1.,v ES?,d(0v)=0(這里0v是任意一個(gè)結(jié)點(diǎn)),0(),()d vvv?2.若|SN?，則結(jié)束；否則，轉(zhuǎn)3。 3.找補(bǔ)集S中的d最小的節(jié)點(diǎn)v，加入S。 更新與v相鄰的結(jié)點(diǎn)w的d值，即若()(,)W vwd w?，則()d w(,)W vw?，轉(zhuǎn)2。 這里的d可以用優(yōu)先隊(duì)列實(shí)現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。 假設(shè)用Fibonai Heap實(shí)現(xiàn)(刪除最小O(logn)，減值O (1)，算法復(fù)雜度(log)O nnm?。 1.6.1.1.2.Kruskal基本思想就是維護(hù)一個(gè)生成森林。 每次將一條權(quán)最小的邊加入子圖T中，并保證不形成圈。 如果當(dāng)前弧加入后不形成圈，則加入這條弧，如果當(dāng)前弧加入后會形成圈，則不加入這條弧，并考慮下一條弧。 算法1.,0Ti?，將E中的邊按權(quán)從小到大排序，12()()()mW eW eWe?。 2.i=i+1，若im，結(jié)束，此時(shí)G沒有生成樹；否則判斷iTe?是否含圈，是則轉(zhuǎn)2，否則轉(zhuǎn)3。 3.iTTe?。 若|T|=N，結(jié)束，此時(shí)T為G的最小生成樹。 分離集合(disjoint set)，可用并查集實(shí)現(xiàn)。 由于排序是(logO m)m的。 所以復(fù)雜度為(logO m()mma n?。 1.6.1.1.3.Sollin（Boruvka）基本思想前面介紹的兩種算法的綜合。 每次迭代同時(shí)擴(kuò)展多棵子樹，直到得到最小生成樹T。 算法1.對于所有,vvv VG?。 T?。 2.若|T|=N，結(jié)束，此時(shí)T為G的最小生成樹；否則，對于T中所有的子樹集合vG，計(jì)算它的邊割,vvG G?中的最小弧*ve（有的書稱連接兩個(gè)連通分量的最小弧“安全邊”）。 3.對T中所有子樹集合vG及其邊割最小弧*(,)p qve?，將vG與q所在的子樹集合合并。 *vTTe?。 轉(zhuǎn)2。 由于每次循環(huán)迭代時(shí)，每棵樹都會合并成一棵較大的子樹，因此每次循環(huán)迭代都會使子樹的數(shù)量至少減少一半，或者說第i次迭代每個(gè)分量大小至少為2i。 所以，循環(huán)迭代的總次數(shù)為O(logn)。 每次循環(huán)迭代所需要的計(jì)算時(shí)間對于第2步，每次檢查所有邊O(m)，去更新每個(gè)連通分量的最小弧；對于第3步，合并(/2)iO n個(gè)子樹。 所以總的復(fù)雜度為(log)O mn。 1.6.1.2.擴(kuò)展模型擴(kuò)展模型Extended models1.6.1.2.1.度限制生成樹度限制生成樹Minimum degree-bounded spanningtrees由于這個(gè)問題是NP-Hard的，一般用搜索算法解決。 本文就只討論一種特殊多項(xiàng)式情況單點(diǎn)度限制(one nodedegree bounded)。 把度限制的點(diǎn)記為0v，滿足度限制0deg()vk?。 一種貪心的思路在最小生成樹T的基礎(chǔ)上，通過添刪邊來改造樹，使之逐漸滿足度限制條件。 算法1.求圖的最小生成樹T。 2.若0v已滿足度限制，結(jié)束；否則轉(zhuǎn)3。 3.對于刪去0v后的每一個(gè)連通分支iT(為一棵樹)，求添加邊割0,T Tvii?中的最小弧，刪除邊割,0iTv里的最大弧后的生成樹中的邊權(quán)和最小的一個(gè)。 更新最小生成樹T。 轉(zhuǎn)2。 第3步，0v的度少1。 習(xí)題NOIxx小H的聚會1.6.1.2.2.k小生成樹小生成樹The kminimum spanningtree problem(k-MST)生成樹T刪除一條邊f(xié)并加入一條新邊e的操作稱為交換交換。 若交換后的圖仍是一顆樹，則此交換稱為可行交換生成樹集合S，生成樹T，若T不在S中，且在S中存在某生成樹是T的鄰樹，稱為T為S的鄰樹。 可行交換。 若生成樹T可通過一次交換成為生成樹T，則稱它們互為鄰樹鄰樹。 對于定理設(shè)12,kT TT?為圖的前k小生成樹，則生成圖集合12,T T,kT?的鄰樹中的邊權(quán)和最小者可作為第k+1小生成樹(可能有邊權(quán)和相同的情況)。 按這個(gè)定理設(shè)計(jì)算法，很難得到有滿意的時(shí)間復(fù)雜度的算法。 下面討論一個(gè)特例次小生成樹(The secondMST,2-MST)基本思想枚舉最小生成樹T的每一個(gè)鄰樹，即枚舉被添加與被刪除的邊。 由于在樹中添加一條邊(,)uv(,)u vT?)，一定形成了一個(gè)環(huán)，環(huán)是由(,)uv與從u到v的生成樹上的唯一路徑(記為(,)P uv)組成的。 所以被刪除的邊一定在(,)P uv上。 由于要求最小邊權(quán)和，所以被刪除的邊一定是(,)P uv上最小者，其權(quán)值記為(,)f uv(,)min()|wee(,)P uvf uv?。 算法1.求圖的最小生成樹T。 次小生成樹T的權(quán)值的最小值()w T?。 2.以每個(gè)結(jié)點(diǎn)為根r，DFS遍歷樹。 在遍歷過程中求出(,)|f rvv V?，用()w T(,)w rv(,)f rv?更新次小生成樹的權(quán)值的最小值()w T。 3.輸出()w T。 算法復(fù)雜度的瓶頸在第2步2()O n，故總算法復(fù)雜度為2()O n。 習(xí)題Ural1416Confidential1.6.2.最短路最短路Shortest paths1.6.2.1.單源最短路單源最短路Single-source shortestpaths令s為起點(diǎn)，t為終點(diǎn)。 單源最短路問題定義為對于網(wǎng)絡(luò)G=(V,E,W)，尋找s到t的一條簡單路徑，使得路徑上的所有邊權(quán)和最少。 令d(v)為s到v的最短路長度上界。 單源最短路問題的規(guī)劃模型如下 (1)(). (2)()() (3)()0d s?(,)w uv(,)u vmindtstd vd uE?對于只含正有向圈的連通有向網(wǎng)絡(luò)，從起點(diǎn)s到任一頂點(diǎn)j都存在最短路，它們構(gòu)成以起點(diǎn)s為根的樹形圖（稱為最短路樹（Tree ofShortest Paths）。 當(dāng)某弧(u,v)位于最短路上時(shí)，一定有()()(,)w uvd vdu?。 所以最短路的長度可以由Bellman方程（最短路方程）唯一確定 (1)() (2)()d v0min()uv?(,)w uvd sdu?在規(guī)劃模型與最短路方程中都出現(xiàn)了()()(,)w uvd vdu?形式的式子，下面引入松弛操作松弛操作是對于邊(u,v)進(jìn)行的改進(jìn)操作若()()(,)w uvd vdu?，則改進(jìn)()()(,)w uvd vdu?。 直觀的講，就是路徑最后通過(u,v)，使得s到v的距離比原來s到v的方案的距離短。 松弛操作是最短路算法求解的基本方式。 最短路算法求解過程中的標(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)行一次修正，所有頂點(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)號還可能會在以后的迭代中再被改變（稱為臨時(shí)標(biāo)號）。 下文稱永久標(biāo)號為已檢查。 算法1.()0d s?，()d v,()vs?，已檢查U?2.取未檢查的u，即uU?，使得()du最小。 若u取不到，即d(u)=則結(jié)束；否則標(biāo)記為已檢查，即uUU?。 3.枚舉所有的u的臨邊(,)uv，滿足v未檢查，即v U?。 松弛(,)uv，即若()()(,)w uvd vdu?，則改進(jìn)()()(,)w uvd vdu?，pred(v)=u。 轉(zhuǎn)2。 這里的d可以用優(yōu)先隊(duì)列實(shí)現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。 假設(shè)用Fibonai Heap實(shí)現(xiàn)(刪除最小O(logn)，減值O (1)，則算法復(fù)雜度(log)O nnm?。 若用Binary Heap則()log)O nmn?。 適用范圍非負(fù)權(quán)圖。 1.6.2.1.1.2.Bellman-Ford采用了標(biāo)號修正算法(Label-Correcting)。 本質(zhì)就是用迭代法（動態(tài)規(guī)劃）解Bellman-Ford方程 (1)()0,()(,),()min(),min()uv? (1) (1)()k()k(,),w uv,1,2,2kddsvw sv?vsdvdvduu vV k?n?()()kdv表示s到v的且邊數(shù)不超過k條時(shí)的最短路路長。 下面用歸納法證明k=1顯然成立。 假設(shè)對k成立，下面考慮k+1的情況.從起點(diǎn)s