【正文】 416 Confidential. 最短路Shortest paths. 單源最短路 Singlesource shortest paths令s為起點(diǎn)，t為終點(diǎn)。3. 輸出。2. 以每個(gè)結(jié)點(diǎn)為根r，DFS遍歷樹(shù)。算法：1. 求圖的最小生成樹(shù)T。所以被刪除的邊一定在上。下面討論一個(gè)特例：次小生成樹(shù)(The second MST, 2MST) 基本思想：枚舉最小生成樹(shù)T的每一個(gè)鄰樹(shù)，即枚舉被添加與被刪除的邊。定理：設(shè)為圖的前k小生成樹(shù)，則生成圖集合的鄰樹(shù)中的邊權(quán)和最小者可作為第k+1小生成樹(shù)(可能有邊權(quán)和相同的情況)。若生成樹(shù)T可通過(guò)一次交換成為生成樹(shù)T’，則稱它們互為鄰樹(shù)。習(xí)題：NOI 2005 小H的聚會(huì). k小生成樹(shù) The k minimum spanning tree problem(kMST)生成樹(shù)T刪除一條邊f(xié)并加入一條新邊e的操作稱為交換。轉(zhuǎn)2。3. 對(duì)于刪去后的每一個(gè)連通分支(為一棵樹(shù))，求添加邊割中的最小弧，刪除邊割里的最大弧后的生成樹(shù)中的邊權(quán)和最小的一個(gè)。算法：1. 求圖的最小生成樹(shù)T。把度限制的點(diǎn)記為，滿足度限制。. 擴(kuò)展模型 Extended models. 度限制生成樹(shù) Minimum degreebounded spanning trees由于這個(gè)問(wèn)題是NPHard的，一般用搜索算法解決。每次循環(huán)迭代所需要的計(jì)算時(shí)間：對(duì)于第2步，每次檢查所有邊O(m)，去更新每個(gè)連通分量的最小??；對(duì)于第3步，合并個(gè)子樹(shù)。由于每次循環(huán)迭代時(shí)，每棵樹(shù)都會(huì)合并成一棵較大的子樹(shù)，因此每次循環(huán)迭代都會(huì)使子樹(shù)的數(shù)量至少減少一半，或者說(shuō)第i次迭代每個(gè)分量大小至少為。3. 對(duì)T中所有子樹(shù)集合及其邊割最小弧，將與q所在的子樹(shù)集合合并。 算法：1. 對(duì)于所有。. Sollin（Boruvka）基本思想：前面介紹的兩種算法的綜合。由于排序是的。若|T|=N，結(jié)束，此時(shí)T為G的最小生成樹(shù)。2. i=i+1，若im，結(jié)束，此時(shí)G沒(méi)有生成樹(shù)；否則判斷是否含圈，是則轉(zhuǎn)2，否則轉(zhuǎn)3。如果當(dāng)前弧加入后不形成圈，則加入這條弧，如果當(dāng)前弧加入后會(huì)形成圈，則不加入這條弧，并考慮下一條弧。. Kruskal基本思想：就是維護(hù)一個(gè)生成森林。這里的d可以用優(yōu)先隊(duì)列實(shí)現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。3. 找補(bǔ)集中的d最小的節(jié)點(diǎn)，加入。令d(v)為v到結(jié)點(diǎn)集S的最小距離。即：求G的一棵生成樹(shù)T，使得. 基本算法 Basic algorithms. Prim基本思想：不斷擴(kuò)展一棵子樹(shù)，直到包括原圖的全部頂點(diǎn)，得到最小生成樹(shù)T。有向的中國(guó)郵路問(wèn)題，比較復(fù)雜。4. 最小權(quán)匹配里的各匹配邊所對(duì)應(yīng)的路徑在G中被重復(fù)遍歷一次,得到歐拉圖G’’。2. 確定G’兩兩結(jié)點(diǎn)在G中的最短路作為它們?cè)贕’中的邊權(quán)。V(G’)為原圖G中的奇點(diǎn)，每條邊為兩奇點(diǎn)對(duì)應(yīng)原圖的最短路長(zhǎng)度。由于圖一直保持連通性，所以兩兩奇點(diǎn)之間都存在歐拉路；又兩兩奇點(diǎn)之間的最短路可求；奇點(diǎn)個(gè)數(shù)為偶數(shù)。下面討論在有權(quán)性上的擴(kuò)展：. 無(wú)權(quán)圖 Unweighted. 有權(quán)圖 Weighed — 中國(guó)郵路問(wèn)題The Chinese post problem這就是一個(gè)經(jīng)典的問(wèn)題中國(guó)郵路問(wèn)題：給出一個(gè)連通的無(wú)向的可重邊的有權(quán)圖G，求最短的回路，使得每邊至少遍歷1次。由于無(wú)向邊只能經(jīng)過(guò)一次，所以不能拆成兩條方向相反的有向邊，只能給無(wú)向邊定向，使得定向后的圖滿足“入度等于出度”。著名的問(wèn)題：The K246。？？？？？？？？？？？？？？？？？？？？？？？？？？？？？AOV(activity on vertex network)AOE(activity on edge network)，其中頂點(diǎn)表示事件event，權(quán)表示時(shí)間。存在偏序關(guān)系的集合A稱為偏序集(partical order)。習(xí)題：MIPT 012 Correct dictionary設(shè)R為非空集合A上的二元關(guān)系，如果R滿足自反性(對(duì)于每一個(gè)x∈A，(x,x)∈R )，反對(duì)稱性((x,y)∈R∧(y,x)∈R→x=y )和傳遞性((x,y)∈R∧(y,x)∈R→(x,z)∈R)，則稱R為A上的偏序關(guān)系，記作≤。4. 若出隊(duì)點(diǎn)數(shù)N，則有圈；否則輸出結(jié)果。2. 若隊(duì)Q非空，則點(diǎn)u出隊(duì)，輸出u；否則轉(zhuǎn)4。實(shí)際算法中，用一個(gè)隊(duì)列實(shí)現(xiàn)。偏序是滿足自反性，反對(duì)稱性，傳遞性的序。. 廣度優(yōu)先搜索 Breadth first search (BFS). 拓?fù)渑判?Topological sort拓?fù)渑判蚴菍?duì)有向無(wú)圈圖(DAG)頂點(diǎn)的一種排序，它使得如果存在u,v的有向路徑，那么滿足序中u在v前。3. g(c)就是其子孫中的g最小值。下面以深度為例：記，在DFS樹(shù)中從x開(kāi)始通過(guò)前向弧和后向弧所能到達(dá)的最小的d。所謂拓?fù)湫驍?shù)就是滿足兒子的序數(shù)總比父親大的一個(gè)編號(hào)方式。記f(x)為x與其子孫的后向邊所連到的最老祖先(深度最淺)，表示x 到f(x) 上的邊均不為橋。圈是由一條后向邊(u,v)與DFS樹(shù)中u到v的路徑組成。鏈表法的優(yōu)點(diǎn)很多，不僅代碼簡(jiǎn)單，而且沒(méi)有太多的時(shí)空開(kāi)銷，對(duì)于反向邊的定位只要多加一個(gè)數(shù)據(jù)項(xiàng)紀(jì)錄下反向邊即可；除了終點(diǎn)定位性，幾乎沒(méi)缺點(diǎn)。一般圖都適用。last(u)存以u(píng)為起點(diǎn)的最后一條邊的編號(hào)。有權(quán)圖的例子：作為起點(diǎn)的點(diǎn)012345最后邊的編號(hào)023468編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)值89640367鏈表法：給每條邊(u,v)加一個(gè)前趨，表示以u(píng)為起點(diǎn)的邊鏈表的前一條邊。之后用數(shù)組last(u)記錄以結(jié)點(diǎn)u為起點(diǎn)的最后一條邊的編號(hào)，并規(guī)定last(0)=0。邊排序法：把弧表按起點(diǎn)為第一關(guān)鍵字，終點(diǎn)為第二關(guān)鍵字來(lái)排序。故本文只討論前向星形。反向星形：通過(guò)終點(diǎn)定位邊。按定位方式，又分前向星形(forwards star)與反向星形(reverse star)。有權(quán)圖的例子：起點(diǎn)13455421終點(diǎn)22543343權(quán)值84376069. 星形表示 Star星形表示法就是對(duì)弧表的缺點(diǎn)的改進(jìn)，使之可以通過(guò)起點(diǎn)或終點(diǎn)定位邊。缺點(diǎn)是無(wú)法通過(guò)一些信息(起點(diǎn)，終點(diǎn))定位一條邊?；”肀硎痉ㄖ苯恿谐鏊谢〉钠瘘c(diǎn)和終點(diǎn)，以及權(quán)值。鄰接表方法增加或刪除一條弧所需的計(jì)算工作量很少。對(duì)于有向圖G=(V,E)，一般用A(v)表示節(jié)點(diǎn)v的鄰接表，即節(jié)點(diǎn)v的所有出弧構(gòu)成的集合或鏈表(實(shí)際上只需要列出弧的另一個(gè)端點(diǎn)，即弧的尾)。若邊k與點(diǎn)u關(guān)聯(lián)，若k是u的出邊，則=1；若k是u的入邊=1；否則=0。. 關(guān)聯(lián)矩陣 Incidence matrix用二元數(shù)組，來(lái)表示無(wú)權(quán)有向圖。∞是一個(gè)足夠大的數(shù)。在無(wú)權(quán)圖中，若邊存在，=1；否則=0。這種表示法一般用于稠密圖。參考文獻(xiàn)：[1]Dictionary of Algorithms and Data Structures NIST，[2]Wikipedia，[3]謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系網(wǎng)絡(luò)優(yōu)化講義~jxie/courses/netopt. 圖的表示 Expressions of graph下面介紹幾種表示圖的數(shù)據(jù)結(jié)構(gòu)。常見(jiàn)的P類網(wǎng)絡(luò)優(yōu)化問(wèn)題：最小生成樹(shù)，最短路，最大流，最小費(fèi)用最大流，最大匹配，中國(guó)郵路問(wèn)題。所謂組合(最)優(yōu)化(binatorial optimization)又稱離散優(yōu)化(discrete optimization)，它是通過(guò)數(shù)學(xué)方法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等. 這類問(wèn)題可用數(shù)學(xué)模型描述為：其中D表示有限個(gè)點(diǎn)組成的集合(定義域)，f為目標(biāo)函數(shù),為可行域。Cayley公式：在n階完全圖中，不同生成樹(shù)的個(gè)數(shù)為。邊覆蓋數(shù)=最大獨(dú)立數(shù)=|V|最大匹配數(shù)。增廣軌定理：一個(gè)匹配是最大匹配當(dāng)且僅當(dāng)沒(méi)有增廣軌。完美匹配(perfect matching)是匹配了所有點(diǎn)的匹配。最大匹配(maximum matching)是具有最多邊的匹配。交錯(cuò)軌(alternating path)是圖的一條簡(jiǎn)單路徑，滿足任意相鄰的兩條邊，一條在匹配內(nèi)，一條不在匹配內(nèi)。匹配又稱邊獨(dú)立集(edge independent set)。因此由最小路徑覆蓋數(shù)＝原圖G的頂點(diǎn)數(shù)－二分圖的最大匹配數(shù)便可以得解。所有邊的方向都是由X部到Y(jié)部。拆點(diǎn)：將每一個(gè)頂點(diǎn)i拆成兩個(gè)頂點(diǎn)Xi和Yi。最小路徑覆蓋數(shù)＝G的點(diǎn)數(shù)－最小路徑覆蓋中的邊數(shù)。最小路徑覆蓋(path covering)：是“路徑” 覆蓋“點(diǎn)”，即用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)圖G的所有頂點(diǎn)，即每個(gè)頂點(diǎn)嚴(yán)格屬于一條路徑。定理：無(wú)向圖G無(wú)孤立點(diǎn)，=。先取一個(gè)最大匹配M，1條邊蓋兩個(gè)點(diǎn)；剩下的一個(gè)未蓋點(diǎn)要用一條邊來(lái)覆蓋，邊覆蓋數(shù)=|M| +(|V|2|M|)= |V||M|。M是匹配，W是邊覆蓋，N是點(diǎn)覆蓋，Y是點(diǎn)獨(dú)立集。由上述定理知，三者互相確定，但都是NPC的。定理：無(wú)向圖G無(wú)孤立點(diǎn)，是(極，最小)點(diǎn)覆蓋，充要于是(極，最大)獨(dú)立集。極小點(diǎn)覆蓋不一定是極小支配集。逆命題不成立。關(guān)系：定理：無(wú)向圖G無(wú)孤立點(diǎn)，是極小支配集，則存在是極小支配集，且。 定理：若G中無(wú)孤立點(diǎn)，D為支配集，則D=V(G)D也是一個(gè)支配集。最小邊支配集(minimum edge dominating set)：邊最少的邊支配集?；蛘哒f(shuō)是一部分的“邊”支配了所有“邊”。邊支配集(edge dominating set)：，滿足對(duì)于，有，鄰接。最小支配集(minimum dominating set)：點(diǎn)最少的支配集?；蛘哒f(shuō)是一部分的“點(diǎn)”支配了所有“點(diǎn)”。支配集(dominating set)：，滿足對(duì)于，有。邊獨(dú)立數(shù)(edge independent number)：最大邊獨(dú)立集的邊數(shù)，記為。極大邊獨(dú)立集(maximal edge independent set)：本身為邊獨(dú)立集，再加入任何邊都不是。邊獨(dú)立集(edge independent set)：，滿足對(duì)于，有不鄰接。最大團(tuán)(maximum clique)：點(diǎn)最多的團(tuán)?；蛘哒f(shuō)是導(dǎo)出的子圖是完全圖的點(diǎn)集。團(tuán)(clique)：，滿足對(duì)于，有。最大獨(dú)立集(maximum independent set)：點(diǎn)最多的獨(dú)立集?；蛘哒f(shuō)是導(dǎo)出的子圖是零圖（沒(méi)有邊）的點(diǎn)集。獨(dú)立集(independent set)：，滿足對(duì)于，有。最小邊覆蓋(minimum edge covering)：邊最少的邊覆蓋?；蛘哒f(shuō)是“邊” 覆蓋了所有“點(diǎn)”。邊覆蓋(集)(edge covering (set))：，滿足對(duì)于，有，關(guān)聯(lián)。最小點(diǎn)覆蓋(minimum vertex covering)：點(diǎn)最