第八章 一些特殊的圖,定義2 給定簡單無向圖G=，若E*E，且E*中任意兩條邊都是不相鄰的，則E*稱為G的一個(gè)匹配或邊獨(dú)立集，若在E*中再加入任何一條邊都不是匹配，稱E*為極大匹配，邊數(shù)最多的極大匹配為最大匹配，最大匹配中邊的個(gè)數(shù)稱為G的匹配數(shù)，記為 令M是G的一個(gè)匹配，若結(jié)點(diǎn)v與M中的邊關(guān)聯(lián)，則稱v是M飽和點(diǎn)；否則，稱v是M非飽和點(diǎn)；若G中的每個(gè)結(jié)點(diǎn)都是M飽和點(diǎn)，則稱M是完美匹配。顯然，每個(gè)完美匹配是最大匹配，但反之不真。 定義3 設(shè)G=為一個(gè)二部圖,M為G中一個(gè)最大匹配，若|M|=min|V1|，|V2|，稱M為G中的一個(gè)完備匹配，且 若|V1|V2|,稱M為V1到V2的一個(gè)完備匹配； 若|V1|=|V2|，此時(shí)M為G的完美匹配； （完美匹配是完備匹配，反之不真）,定理2 （Hall 定理） 設(shè)二部圖G=，|V1|V2|,G中存在從V1到V2的完備匹配當(dāng)且僅當(dāng)V1中任意k個(gè)頂點(diǎn)至少鄰接V2中的k個(gè)頂點(diǎn)。（相異性條件） 定理3 設(shè)二部圖G=，如果： （1）V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t（t0）條邊； （2）V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊；（t條件） 則G中存在V1到V2的完備匹配。 滿足t條件的二部圖一定滿足相異性條件；反之不真,第二節(jié) 歐拉圖,PLAY,第三節(jié) 哈密頓圖,第四節(jié) 平面圖,第五節(jié) 圖中頂點(diǎn)的著色（無環(huán)無向圖）,第六節(jié) 地圖的著色與平面圖的點(diǎn)著色,第七節(jié) 邊著色（無環(huán)無向圖）,第三節(jié) 帶權(quán)圖與貨郎擔(dān)問題,第十七章 平面圖及圖的著色,第十七章 習(xí)題課,解,證,證,解,圖20,圖19,解,最短路徑 (Shortest Path),最短路徑問題：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。 問題解法 邊上權(quán)值非負(fù)情形的單源最短路徑問題 Dijkstra算法 邊上權(quán)值為任意值的單源最短路徑問題 Bellman和Ford算法 所有頂點(diǎn)之間的最短路徑 Floyd算法,邊上權(quán)值非負(fù)情形的單源最短路徑問題,問題的提法： 給定一個(gè)帶權(quán)有向圖D與源點(diǎn)v，求從v到D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。 為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。 舉例說明,Dijkstra逐步求解的過程,引入一個(gè)輔助數(shù)組dist。它的每一個(gè)分量disti表示當(dāng)前找到的從源點(diǎn)v0到終點(diǎn)vi 的最短路徑的長度。初始狀態(tài)： 若從源點(diǎn)v0到頂點(diǎn)vi有邊，則disti為該邊上的權(quán)值； 若從源點(diǎn)v0到頂點(diǎn)vi 沒有邊，則disti為+ 。 一般情況下，假設(shè) S 是已求得的最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑必然是從v0 出發(fā)，中間只經(jīng)過S中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)vx (vx V-S )的路徑中的一條。 每次求得一條最短路徑之后，其終點(diǎn)vk 加入集合S，然后對所有的vi V-S，修改其disti值。,Dijkstra算法可描述如下：,初始化： S v0 ; distj Edge0j, j = 1, 2, , n-1; / n為圖中頂點(diǎn)個(gè)數(shù) 求出最短路徑的長度： distk min disti , i V- S ; S S U k ; 修改： disti min disti, distk + Edgeki , 對于每一個(gè) i V- S ; 判斷： 若S = V, 則算法結(jié)束，否則轉(zhuǎn)。,Dijkstra算法中各輔助數(shù)組的變化,如何從表中讀取源點(diǎn)0到終點(diǎn)v的最短路徑？舉頂點(diǎn)4為例 path4 = 2 path2 = 3 path3 = 0，反過來排列，得到路徑0, 3, 2, 4，這就是源點(diǎn)0到終點(diǎn)4的最短路徑。,邊上權(quán)值為任意值的單源最短路徑問題,帶權(quán)有向圖D的某幾條邊或所有邊的長度可能為負(fù)值。利用Dijkstra算法，不一定能得到正確的結(jié)果。 源點(diǎn)0到終點(diǎn)2的最短路徑應(yīng)是0, 1, 2，其長度為2，它小于算法中計(jì)算出來的dist2的值。,若設(shè)源點(diǎn)v = 0，使用Dijkstra算法，所得到的結(jié)果是不對的。,Bellman和Ford提出了從源點(diǎn)逐次繞過其它頂點(diǎn)，以縮短到達(dá)終點(diǎn)的最短路徑長度的方法。該方法有一個(gè)限制條件，即要求圖中不能包含有由帶負(fù)權(quán)值的邊組成的回路。 當(dāng)圖中沒有由帶負(fù)權(quán)值的邊組成的回路時(shí)，有n個(gè)頂點(diǎn)的圖中任意兩個(gè)頂點(diǎn)之間如果存在最短路徑，此路徑最多有n-1條邊。 我們將以此為依據(jù)考慮計(jì)算從源點(diǎn)v到其它頂點(diǎn)u的最短路徑的長度distu。,Bellman-Ford方法構(gòu)造一個(gè)最短路徑長度數(shù)組序列dist1 u，dist2 u，distn-1 u。其中，dist1 u是從源點(diǎn)v到終點(diǎn)u的只經(jīng)過一條邊的最短路徑的長度，dist1 u = Edgevu；dist2 u是從源點(diǎn)v最多經(jīng)過兩條邊到達(dá)終點(diǎn)u的最短路徑的長度，dist3 u是從源點(diǎn)v出發(fā)最多經(jīng)過不構(gòu)成帶負(fù)長度邊回路的三條邊到達(dá)終點(diǎn)u的最短路徑的長度，dist n-1u是從源點(diǎn)v出發(fā)最多經(jīng)過不構(gòu)成帶負(fù)長度邊回路的n-1條邊到達(dá)終點(diǎn)u的最短路徑的長度。 算法的最終目的是計(jì)算出dist n-1u。 可以用遞推方式計(jì)算distk u。,dist1 u = Edgevu； distk u = min distk-1 u, min distk-1 j+ Edgeju 設(shè)已經(jīng)求出 distk-1 j, j = 0, 1, , n-1, 此即從源點(diǎn) v 最多經(jīng)過不構(gòu)成帶負(fù)長度邊回路的 k-1 條邊到達(dá)終點(diǎn) j 的最短路徑的長度。 從圖的鄰接矩陣中可以找到各個(gè)頂點(diǎn) j 到達(dá)頂點(diǎn) u 的距離 Edgeju，計(jì)算 min distk-1 j+ Edgeju ，可得從源點(diǎn) v 繞過各個(gè)頂點(diǎn)，最多經(jīng)過不構(gòu)成帶負(fù)長度邊回路的 k 條邊到達(dá)終點(diǎn)u的最短路徑的長度。 用它與distk-1 u比較，取小者作為distk u的值。,圖的最短路徑長度,計(jì)算最短路徑的Bellman和Ford算法 void Graph:BellmanFord ( const int n, const int v ) /在帶權(quán)有向圖中有的邊具有負(fù)的權(quán)值。從頂點(diǎn) v /找到所有其它頂點(diǎn)的最短路徑。 for ( int i = 0; i n; i+ ) disti = Edgevi; if ( i != v ,for ( int k = 2; k 0 ,所有頂點(diǎn)之間的最短路徑,問題的提法：已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點(diǎn) vi vj，要求求出vi 與vj之間的最短路徑和最短路徑長度。 Floyd算法的基本思想： 定義一個(gè)n階方陣序列： A(-1), A(0), , A(n-1). 其中 A(-1) ij = Edgeij； A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n-1,A(0) ij是從頂點(diǎn)vi 到vj , 中間頂點(diǎn)是v0的最短路徑的長度, A(k) ij是從頂點(diǎn)vi 到vj , 中間頂點(diǎn)的序號不大于k的最短路徑的長度, A(n-1)ij是從頂點(diǎn)vi 到vj 的最短路徑長度。,所有各對頂點(diǎn)之間的最短路徑 void Graph:AllLengths ( const int n ) /Edgenn是一個(gè)具有n個(gè)頂點(diǎn)的圖的鄰接矩陣。/aij是頂點(diǎn) i 和 j 之間的最短路徑長度。pathij /是相應(yīng)路徑上頂點(diǎn) j 的前一頂點(diǎn)的頂點(diǎn)號, 在求 /最短路徑時(shí)圖的類定義中要修改path為 /pathNumVerticesNumVertices。,for ( int i = 0; i j /縮短路徑長度, 繞過 k 到 j ,以 Path(3)為例，對最短路徑的讀法加以說明。從A(3)知，頂點(diǎn)1到0的最短路徑長度為a10 = 11, 其最短路徑看 path10 = 2，path12 = 3，path 13 = 1, 表示頂點(diǎn)0 頂點(diǎn)2 頂點(diǎn)3 頂點(diǎn)1;從頂點(diǎn)1到頂點(diǎn)0最短路徑為,。 Floyd算法允許圖中有帶負(fù)權(quán)值的邊，但不許有包含帶負(fù)權(quán)值的邊組成的回路。 本章給出的求解最短路徑的算法不僅適用于帶權(quán)有向圖，對帶權(quán)無向圖也可以適用。因?yàn)閹?quán)無向圖可以看作是有往返二重邊的有向圖，只要在頂點(diǎn)vi 與vj 之間存在無向邊(vi , vj )，就可以看成是在這兩個(gè)頂點(diǎn)之間存在權(quán)值相同的兩條有向邊和。,用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE網(wǎng)絡(luò)),如果在無有向環(huán)的帶權(quán)有向圖中 用有向邊表示一個(gè)工程中的各項(xiàng)活動(dòng)(Activity) 用邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間(Duration) 用頂點(diǎn)表示事件(Event) 則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡稱AOE (Activity On Edges)網(wǎng)絡(luò)。 AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解： (1) 完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))? (2) 為縮短完成工程所需的時(shí)間, 應(yīng)當(dāng)加快哪些活動(dòng)?,在AOE網(wǎng)絡(luò)中, 有些活動(dòng)順序進(jìn)行，有些活動(dòng)并行進(jìn)行。 從源點(diǎn)到各個(gè)頂點(diǎn)，以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同，但只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。 因此，完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長路徑長度，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(Critical Path)。,要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng)，即不按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)。 關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。因此，只要找到了關(guān)鍵活動(dòng)，就可以找到,關(guān)鍵路徑,定義幾個(gè)與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量：,事件Vi 的最早可能開始時(shí)間Ve(i) 是從源點(diǎn)V0 到頂點(diǎn)Vi 的最長路徑長度。 事件Vi 的最遲允許開始時(shí)間Vli 是在保證匯點(diǎn)Vn-1 在Ven-1 時(shí)刻完成的前提下，事件Vi 的允許的最遲開始時(shí)間。 活動(dòng)ak 的最早可能開始時(shí)間 ek 設(shè)活動(dòng)ak 在邊上，則ek是從源點(diǎn)V0到頂點(diǎn)Vi 的最長路徑長度。因此, ek = Vei。 活動(dòng)ak 的最遲允許開始時(shí)間 lk lk是在不會(huì)引起時(shí)間延誤的前提下，該活動(dòng)允許的最遲開始時(shí)間。,lk = Vlj - dur()。 其中，dur()是完成ak 所需的時(shí)間。 時(shí)間余量 lk - ek 表示活動(dòng)ak 的最早可能開始時(shí)間和最遲允許開始時(shí)間的時(shí)間余量。lk = ek表示活動(dòng)ak 是沒有時(shí)間余量的關(guān)鍵活動(dòng)。 為找出關(guān)鍵活動(dòng), 需要求各個(gè)活動(dòng)的 ek 與 lk，以判別是否 lk = ek. 為求得ek與 lk，需要先求得從源點(diǎn)V0到各個(gè)頂點(diǎn)Vi 的 Vei 和 Vli。 求Vei的遞推公式,從Ve0 = 0開始，向前遞推 S2, i = 1, 2, , n-1 其中, S2是所有指向頂點(diǎn)Vi 的有向邊的集合。 從Vln-1 = Ven-1開始，反向遞推 S1, i = n-2, n-3, , 0 其中, S1是所有從頂點(diǎn)Vi 發(fā)出的有向邊的集合。 這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚣澳嫱負(fù)溆行虻那疤嵯逻M(jìn)行。,設(shè)活動(dòng)ak (k = 1, 2, , e)在帶權(quán)有向邊 上, 它的持續(xù)時(shí)間用dur () 表示，則有 ek = Vei； lk = Vlj - dur()；k = 1, 2, , e。這樣就得到計(jì)算關(guān)鍵路徑的算法。 計(jì)算關(guān)鍵路徑時(shí)，可以一邊進(jìn)行拓?fù)渑判蛞贿呌?jì)算各頂點(diǎn)的Vei。為了簡化算法，假定在求關(guān)鍵路徑之前已經(jīng)對各頂點(diǎn)實(shí)現(xiàn)了拓?fù)渑判颍赐負(fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)行了編號。算法在求Vei, i=0, 1, , n-1時(shí)按拓?fù)溆行虻捻樞蛴?jì)