1、1,Email: ,圖論及其應(yīng)用,任課教師：楊春,數(shù)學(xué)科學(xué)學(xué)院,2,第一章 圖的基本概念,本次課主要內(nèi)容,最短路算法、圖的代數(shù)表示,(一)、最短路算法,(二)、圖的代數(shù)表示,1、圖的鄰接矩陣,2、圖的關(guān)聯(lián)矩陣,3,1、相關(guān)概念,(1) 賦權(quán)圖,(一)、最短路算法,在圖G的每條邊上標(biāo)上一個實數(shù)w (e)后, 稱G為邊賦權(quán)圖。被標(biāo)上的實數(shù)稱為邊的權(quán)值。,若H是賦權(quán)圖G的一個子圖，稱 為子圖H的權(quán)值。,權(quán)值的意義是廣泛的?？梢员硎揪嚯x，可以表示交通運費，可以表示網(wǎng)絡(luò)流量，在朋友關(guān)系圖甚至可以表示友誼深度。但都可以抽象為距離。,4,(2) 賦權(quán)圖中的最短路,設(shè)G為邊賦權(quán)圖。u與v是G中兩點，在連接u與

2、v的所有路中，路中各邊權(quán)值之和最小的路，稱為u與v間的最短路。,解決某類問題的一組有窮規(guī)則，稱為算法。,(3) 算法,1) 好算法,算法總運算量是問題規(guī)模的多項式函數(shù)時，稱該算法為好算法。(問題規(guī)模：描述或表示問題需要的信息量),算法中的運算包括算術(shù)運算、比較運算等。運算量用運算次數(shù)表示。,2) 算法分析,5,對算法進(jìn)行分析，主要對時間復(fù)雜性進(jìn)行分析。分析運算量和問題規(guī)模之間的關(guān)系。,2、最短路算法,1959年，旦捷希(Dantjig）發(fā)現(xiàn)了在賦權(quán)圖中求由點a到點b的最短路好算法，稱為頂點標(biāo)號法。,t (an) : 點an的標(biāo)號值，表示點 a1=a 到an的最短路長度,Ai =a1,a2, .

3、, ai:已經(jīng)標(biāo)號的頂點集合。,Ti : a1到ai的最短路上的邊集合,算法敘述如下：,6,(1) 記 a=a1 , t(a1) =0, A1= a1, T1= ;,(2) 若已經(jīng)得到 Ai = a1,a2, ai , 且對于 1ni,已知t(an),對每一個an Ai , 求一點：,使得：,(3) 設(shè)有mi ，1mii ,而bmi(i)是使 取最小值，令：,(4) 若ai+1=b ,停止，否則，記 ,轉(zhuǎn)(2).,7,時間復(fù)雜性分析：,對第i次循環(huán)：步驟(2)要進(jìn)行i次比較運算，步驟(3)要進(jìn)行i次加法與i次比較運算。所以，該次循環(huán)運算量為3i .所以，在最壞的情況下，運算量為n2級，是好算法

4、。,算法證明：,定理1：算法中的函數(shù)t(ai)給出了a與ai的距離。,證明：對i作數(shù)學(xué)歸納法。,(1) i=1時結(jié)論顯然成立。,(2) 設(shè)對所有的j，1ji 時，t (aj)=d (a, aj).,(3) 考慮j=i,令P= v0 v1 vd , v0 = a ,vd =ai是連接a與ai的一條最短路.,8,于是,因為 ，所以：,又令vn是P中第一個不在Ai-1中的點。由于 ，所以 這樣的點存在。,記P中a到vn一段長為 ,而a到vn-1的一段長為 。,由歸納假設(shè)有：,9,顯然有：,由算法：當(dāng)已知 而要給ai標(biāo)號時，,其中要選擇 ，由選擇知：,所以：,10,另一方面：由算法知，存在一條長度為t

5、(ai)的 聯(lián)結(jié)a與ai的路，所以：,又由算法最終對點ai的標(biāo)號值的選擇方法知：,這樣，我們證明了：,故，算法是正確的。,11,例1 如圖所示，求點a到點b的距離。,解 1. A1= a，t (a) = 0，T1 = ,2. b1 (1)= v3 ;,3. m1 = 1, a2 = v3 , t(v3) = t(a) + l(av3) = 1 (最小)， T2 =av3;,12,2. A2 =a, v3, b1 (2) =v1, b2 (2) =v2 ;,3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)，,T3 =av3, av1;,2.

6、A3 =a, v3, v1, b1 (3) =v2, b2 (3) =v2 , b3 (3) =v4 ;,3. m3 = 3, a4 = v4 , t(v4) = t(v1) + l(v1v4) = 3 (最小)，,T4 =av3, av1, v1v4,2. A4 = a, v3, v1, v4，b1 (4) = v2，b2 (4) = v2，b3 (4) = v2, b4 (4) = v5 ;,3. m4 = 4, a5 = v5 , t(v5) = t(v4) + l(v4v5) = 6 (最小)，,T5 =av3, av1, v1v4, v4v5 ;,13,2. A5 = a, v3,

7、v1, v4, v5，b1 (5) = v2，b2 (5) = v2， b3 (5) = v2 , b4 (5) = v2, b5 (5) = v2 ;,3. m5 = 4, t(v2) = t(v4) + l(v4v2) = 7 (最小)，,T6 =av3, av1, v1v4, v4v5, v4v2;,2. A6 = a, v3, v1, v4, v5, v2, b2 (6) = v6, b4 (6) = b， b5 (6) = v6，b6 (6) = v6 ;,3. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小)，,T7 =av3,

8、av1, v1v4, v4v5, v4v2, v2v6 ;,2. A7 = a, v3, v1, v4, v5, v2, v6, b4 (7) = b，b5 (7) =b， b7 (7) =b ;,3. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)，,14,T8 =av3, av1, v1v4, v4v5, v4v2, v2v6, v6b;,于是知a與b的距離,d (a, b) = t (b) = 11,由T8導(dǎo)出的a到b的最短路為：,課外作業(yè),某公司在六個城市C1,C2,C3,C4,C5,C6中有分公司，從Ci到Cj的直接航程票價記在下述矩

9、陣的(i, j)位置上，表示沒有直接航程。制作一張任意兩城市間的最便宜的路線表。,15,例2 某兩人有一只8升的酒壺裝滿了酒，還有兩只空壺，分別為5升和3升。求最少的操作次數(shù)能均分酒。,解：設(shè)x1,x2,x3分別表示8,5,3升酒壺中的酒量。則,容易算出(x1,x2,x3) 的組合形式共24種。,每種組合用一個點表示，兩點連線，當(dāng)且僅當(dāng)可通過倒酒的方式相互變換。,若各邊賦權(quán)為1，則問題轉(zhuǎn)化為在該圖中求(8,0,0)到 (4,4,0)的一條最短路。結(jié)果如下：,16,例3 在一河岸有狼，羊和卷心菜。擺渡人要將它們渡過河去，由于船太小，每次只能載一樣?xùn)|西。由于狼羊，羊卷心菜不能單獨相處。問擺渡人至少

10、要多少次才能將其渡過河？,分析：人，狼，羊，菜所有組合形式為：,但是以下組合不能允許出現(xiàn)：,狼羊菜，羊菜，狼羊，人，人狼，人菜，共6種。,岸上只能允許出現(xiàn)10種組合：,人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。,每種情況用點表示；,17,兩點連線，當(dāng)且僅當(dāng)兩種情況可用載人(或加一物)的渡船相互轉(zhuǎn)變。,于是，問題轉(zhuǎn)化為求由頂點“人狼羊菜”到頂點“空”的一條最短路。,每條邊賦權(quán)為1,結(jié)果為：,人狼羊菜狼菜人狼菜狼人狼羊羊 人羊空；,(2) 人狼羊菜狼菜人狼菜菜人羊菜羊 人羊空。,18,(二)、圖的代數(shù)表示,用鄰接矩陣或關(guān)聯(lián)矩陣表示圖，稱為圖的代數(shù)表示。 用矩陣表示圖，主要有兩個

11、優(yōu)點： (1) 能夠把圖輸入到計 算機中；(2) 可以用代數(shù)方法研究圖論。,1、圖的鄰接矩陣,定義1 設(shè)G為n階圖，V=v1, v2, , vn,鄰接矩陣A(G)=(aij),其中：,19,例如：寫出下圖G的鄰接矩陣：,解：鄰接矩陣為：,20,圖G的鄰接矩陣的性質(zhì),(1)非負(fù)性與對稱性,由鄰接矩陣定義知aij是非負(fù)整數(shù)，即鄰接矩陣是非負(fù)整數(shù)矩陣；,在圖中點vi與vj鄰接，有vj與vi鄰接，即aij =aji.所以，鄰接矩陣是對稱矩陣。,(2) 同一圖的不同形式的鄰接矩陣是相似矩陣。,這是因為，同圖的兩種不同形式矩陣可以通過交換行和相應(yīng)的列變成一致。,(3) 如果G為簡單圖，則A(G)為布爾矩陣

12、;行和(列和)等于對應(yīng)頂點的度數(shù)；矩陣元素總和為圖的總度數(shù)，也就是G的邊數(shù)的2倍。,21,(4) G連通的充分必要條件是：A(G)不能與如下矩陣相似,證明：1) 必要性,若不然：設(shè)A11對應(yīng)的頂點是v1,v2, vk , A22對應(yīng)的頂點為vk+1,vk+2, vn,顯然，vi (1ik)與vj (k+1in)不鄰接，即G是非連通圖。矛盾！,2) 充分性,若不然：設(shè)G1與G2是G的兩個不連通的部分，并且設(shè) V(G1)=v1,v2,vk, V(G2)=vk+1,vk+2,vn, 如果在寫,22,G的鄰接矩陣時，先排V(G1)中點，再排V(G2)中點，則G的鄰接矩陣形式必為：,(5) 定理：設(shè) ，

13、則a ij (k)表示頂點vi到頂點 vj的途徑長度為k的途徑條數(shù)。,證明：對k作數(shù)學(xué)歸納法證明。,當(dāng)k=1時，由鄰接矩陣的定義，結(jié)論成立；,設(shè)結(jié)論對k-1時成立。當(dāng)為k時：,一方面：先計算Ak ;,23,另一方面：考慮vi到vj的長度為k的途徑,設(shè)vm是vi到vj的途徑中點，且該點和vj鄰接。則vi到vj的經(jīng)過vm且長度為k的途徑數(shù)目應(yīng)該為：,所以，vi到vj的長度為k的途徑數(shù)目為：,即為,例4 求下圖中v1到v3的途徑長度為2和3的條數(shù)。,24,解：由于：,所以，v1到v3的途徑長度為2和3的條數(shù)分別為：3和4。,推論: (1)A2的元素aii (2)是vi的度數(shù)，A3的元素aii (3)

14、是含vi的三角形個數(shù)的2倍；,25,(2) 若G是連通的，對于i j , vi和vj間距離是使An的 aij (n)0的最小整數(shù)。,2、圖的關(guān)聯(lián)矩陣,(1) 若G是(n, m) 圖。定義G的關(guān)聯(lián)矩陣：,其中：,例如：,26,(2) 關(guān)聯(lián)矩陣的性質(zhì),1) 關(guān)聯(lián)矩陣的元素為0，1或2；,2) 關(guān)聯(lián)矩陣的每列和為2；每行的和為對應(yīng)頂點度數(shù)；,3) 無環(huán)圖G連通的充分必要條件是R(M) = n-1；,證明：,令：,由于M中每列恰有兩個“1”元素，所有行向量的和為0(模2加法運算)。所以：,27,另一方面：在M中任意去掉一行mk, 由于G是連通的，因此，mk中存在元素“1”, 這樣，M中去掉行mk后的行按模2相加不等于零，即它們是線性無關(guān)的。所以：,所以：,若G不連通，假設(shè)G有兩個連通分支G1與G2。又設(shè)G1與G2的關(guān)聯(lián)矩陣分別為M1與M2, 則G的關(guān)聯(lián)矩陣可以寫為：,于是，R(M)