電子科大圖論楊春4

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1Email: 圖論及其應(yīng)用圖論及其應(yīng)用任課教師：楊春任課教師：楊春數(shù)學(xué)科學(xué)學(xué)院數(shù)學(xué)科學(xué)學(xué)院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2第一章第一章 圖的基本概念圖的基本概念本次課主要內(nèi)容本次課主要內(nèi)容最短路算法、圖的代數(shù)表示最短路算法、圖的代數(shù)表示(一一)、最短路算法、最短路算法(二二)、圖的代數(shù)表示、圖的代數(shù)表示1、圖的鄰接矩陣、圖的鄰接矩陣2、圖的關(guān)聯(lián)矩陣、圖的關(guān)聯(lián)矩陣 0.8 1 0.6 0.4 0.2 0 x

2、 t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31 1、相關(guān)概念、相關(guān)概念(1) 賦權(quán)圖賦權(quán)圖()()( )eEHWHw e(一一)、最短路算法、最短路算法 在圖在圖G的每條邊上標(biāo)上一個實數(shù)的每條邊上標(biāo)上一個實數(shù)w (e)后后, 稱稱G為邊賦權(quán)圖。為邊賦權(quán)圖。被標(biāo)上的實數(shù)稱為邊的權(quán)值。被標(biāo)上的實數(shù)稱為邊的權(quán)值。 若若H是賦權(quán)圖是賦權(quán)圖G的一個子圖，稱的一個子圖，稱 為子圖為子圖H的權(quán)值。的權(quán)值。 權(quán)值的意義是廣泛的。可以表示距離，可以表示交通運(yùn)費(fèi)，權(quán)值的意義是廣泛的。可以表示距離，可以表示交通運(yùn)費(fèi)，可以表示網(wǎng)絡(luò)流量，在朋友關(guān)系圖甚至可以表示友誼深度?？梢员硎揪W(wǎng)絡(luò)流量，在朋友

3、關(guān)系圖甚至可以表示友誼深度。但都可以抽象為距離。但都可以抽象為距離。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4(2) 賦權(quán)圖中的最短路賦權(quán)圖中的最短路 設(shè)設(shè)G為邊賦權(quán)圖。為邊賦權(quán)圖。u與與v是是G中兩點，在連接中兩點，在連接u與與v的所有路的所有路中，路中各邊權(quán)值之和最小的路，稱為中，路中各邊權(quán)值之和最小的路，稱為u與與v間的最短路。間的最短路。 解決某類問題的一組有窮規(guī)則，稱為算法。解決某類問題的一組有窮規(guī)則，稱為算法。(3) 算法算法1) 好算法好算法 算法總運(yùn)算量是問題規(guī)模的多項式函數(shù)時，稱該算法為好算法總運(yùn)算量是問題

4、規(guī)模的多項式函數(shù)時，稱該算法為好算法。算法。(問題規(guī)模：描述或表示問題需要的信息量問題規(guī)模：描述或表示問題需要的信息量) 算法中的運(yùn)算包括算術(shù)運(yùn)算、比較運(yùn)算等。運(yùn)算量用運(yùn)算算法中的運(yùn)算包括算術(shù)運(yùn)算、比較運(yùn)算等。運(yùn)算量用運(yùn)算次數(shù)表示。次數(shù)表示。2) 算法分析算法分析 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 對算法進(jìn)行分析，主要對時間復(fù)雜性進(jìn)行分析。分析運(yùn)算對算法進(jìn)行分析，主要對時間復(fù)雜性進(jìn)行分析。分析運(yùn)算量和問題規(guī)模之間的關(guān)系。量和問題規(guī)模之間的關(guān)系。2 2、最短路算法、最短路算法 1959年，旦捷希年，旦捷希(Dantji

5、g）發(fā)現(xiàn)了在賦權(quán)圖中求由點）發(fā)現(xiàn)了在賦權(quán)圖中求由點a到點到點b的最短路好算法，稱為頂點標(biāo)號法。的最短路好算法，稱為頂點標(biāo)號法。 t (an) : 點點an的標(biāo)號值，表示點的標(biāo)號值，表示點 a1=a 到到an的最短路長度的最短路長度 Ai =a1,a2, ., ai:已經(jīng)標(biāo)號的頂點集合。已經(jīng)標(biāo)號的頂點集合。 Ti : a1到到ai的最短路上的邊集合的最短路上的邊集合算法敘述如下：算法敘述如下： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6(1) 記記 a=a1 , t(a1) =0, A1= a1, T1= ;(2) 若已經(jīng)得到若

6、已經(jīng)得到 Ai = a1,a2, ai , 且對于且對于 1ni,ni,已知已知t(at(an n),),對每一個對每一個a an n Ai , 求一點：求一點：( )( )()iinninbN aAB使得：使得：( )( )()min ()ininnnvBl a bl a v(3) 設(shè)有設(shè)有mi ，1mmi ii ,i ,而而b bmimi(i(i) )是使是使 取最小取最小值，令：值，令：( )()()iiiimmmt al a b( )11111, ()()(),iiiiimiimmiiimibat at al aaTTaa(4) 若若ai+1=b ,停止，否則，記停止，否則，記 ,轉(zhuǎn)轉(zhuǎn)

7、(2).11iiiAAa 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7時間復(fù)雜性分析：時間復(fù)雜性分析： 對第對第i次循環(huán)：步驟次循環(huán)：步驟(2)要進(jìn)行要進(jìn)行i次比較運(yùn)算，步驟次比較運(yùn)算，步驟(3)要進(jìn)行要進(jìn)行i次加法與次加法與i次比較運(yùn)算。所以，該次循環(huán)運(yùn)算量為次比較運(yùn)算。所以，該次循環(huán)運(yùn)算量為3i .所以，所以，在最壞的情況下，運(yùn)算量為在最壞的情況下，運(yùn)算量為n2級，是好算法。級，是好算法。算法證明算法證明 (略）略） 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n

8、8例例1 如圖所示，求點如圖所示，求點a到點到點b的距離。的距離。812614227924693av1v2v3v4v5v6b解解 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; 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 92. A2 =a, v3, b1 (2) =v1, b2 (2) =v2 ;3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(a

9、v1) = 2 (最小最小)， T3 =av3, av1; 2. 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, v1v42. 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, a

10、v1, v1v4, v4v5 ; 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 102. A5 = a, v3, 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

11、 (6) = v6，b6 (6) = v6 ;3. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小最小)， T7 =av3, 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 (最小最小)， 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11T8

12、=av3, av1, v1v4, v4v5, v4v2, v2v6, v6b;于是知于是知a與與b的距離的距離 d (a, b) = t (b) = 11 由由T8導(dǎo)出的導(dǎo)出的a到到b的最短路為：的最短路為：1426a v v v v b課外作業(yè)課外作業(yè) 某公司在六個城市某公司在六個城市C1,C2,C3,C4,C5,C6中有分公司，中有分公司，從從Ci到到Cj的直接航程票價記在下述矩陣的的直接航程票價記在下述矩陣的(i, j)位置上，位置上，表示沒有直接航程。制作一張任意兩城市間的最便表示沒有直接航程。制作一張任意兩城市間的最便宜的路線表。宜的路線表。050402510500152025150

13、102040201001025252010055102525550 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12例例2 某兩人有一只某兩人有一只8升的酒壺裝滿了酒，還有兩只空壺，升的酒壺裝滿了酒，還有兩只空壺，分別為分別為5升和升和3升。求最少的操作次數(shù)能均分酒。升。求最少的操作次數(shù)能均分酒。解：設(shè)解：設(shè)x1,x2,x3分別表示分別表示8,5,3升酒壺中的酒量。則升酒壺中的酒量。則1231238,8,5,3 .xxxxxx容易算出容易算出(x1,x2,x3) 的組合形式共的組合形式共24種。種。每種組合用一個點表示，兩點連線，

14、當(dāng)且僅當(dāng)可通過每種組合用一個點表示，兩點連線，當(dāng)且僅當(dāng)可通過倒酒的方式相互變換。倒酒的方式相互變換。若各邊賦權(quán)為若各邊賦權(quán)為1，則問題轉(zhuǎn)化為在該圖中求，則問題轉(zhuǎn)化為在該圖中求(8,0,0)到到(4,4,0)的一條最短路。結(jié)果如下：的一條最短路。結(jié)果如下：(8,0,0)(3,5,0)(3,2,3)(6,2,0)(6,0,2)(1,5,2)(1,4,3)(4,4,0). 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13例例3 在一河岸有狼，羊和卷心菜。擺渡人要將它們渡過河在一河岸有狼，羊和卷心菜。擺渡人要將它們渡過河去，由于船太小，每

15、次只能載一樣?xùn)|西。由于狼羊，羊去，由于船太小，每次只能載一樣?xùn)|西。由于狼羊，羊卷心菜不能單獨相處。問擺渡人至少要多少次才能將其卷心菜不能單獨相處。問擺渡人至少要多少次才能將其渡過河？渡過河？分析：人，狼，羊，菜所有組合形式為：分析：人，狼，羊，菜所有組合形式為：0123444444421 6CCCCC但是以下組合不能允許出現(xiàn)：但是以下組合不能允許出現(xiàn)：狼羊菜，羊菜，狼羊，人，人狼，人菜，共狼羊菜，羊菜，狼羊，人，人狼，人菜，共6種。種。岸上只能允許出現(xiàn)岸上只能允許出現(xiàn)10種組合：種組合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜

16、。狼菜，人羊菜。每種情況用點表示；每種情況用點表示； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14兩點連線，當(dāng)且僅當(dāng)兩種情況可用載人兩點連線，當(dāng)且僅當(dāng)兩種情況可用載人(或加一物或加一物)的的渡船相互轉(zhuǎn)變。渡船相互轉(zhuǎn)變。于是，問題轉(zhuǎn)化為求由頂點于是，問題轉(zhuǎn)化為求由頂點“人狼羊菜人狼羊菜”到頂點到頂點“空空”的一條最短路。的一條最短路。每條邊賦權(quán)為每條邊賦權(quán)為1結(jié)果為：結(jié)果為：(1) 人狼羊菜人狼羊菜狼菜狼菜人狼菜人狼菜狼狼人狼羊人狼羊羊羊人羊人羊空；空；(2) 人狼羊菜人狼羊菜狼菜狼菜人狼菜人狼菜菜菜人羊菜人羊菜羊羊人羊人羊空。

17、空。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15(二二)、圖的代數(shù)表示、圖的代數(shù)表示 用鄰接矩陣或關(guān)聯(lián)矩陣表示圖，稱為圖的代數(shù)表示。用鄰接矩陣或關(guān)聯(lián)矩陣表示圖，稱為圖的代數(shù)表示。用矩陣表示圖，主要有兩個優(yōu)點：用矩陣表示圖，主要有兩個優(yōu)點： (1) 能夠把圖輸入到計能夠把圖輸入到計算機(jī)中；算機(jī)中；(2) 可以用代數(shù)方法研究圖論?？梢杂么鷶?shù)方法研究圖論。1、圖的鄰接矩陣、圖的鄰接矩陣定義定義1 設(shè)設(shè)G為為n階圖，階圖，V=v1, v2, , vn,鄰接矩陣鄰接矩陣A(G)=(aij),其其中：中：,0ijijijl vvav與間

18、 邊 數(shù)， v 和不 鄰 接 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16例如：寫出下圖例如：寫出下圖G的鄰接矩陣：的鄰接矩陣：解：鄰接矩陣為：解：鄰接矩陣為：1234圖圖G02012011()01011112A G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17圖圖G的鄰接矩陣的性質(zhì)的鄰接矩陣的性質(zhì)(1)非負(fù)性與對稱性非負(fù)性與對稱性 由鄰接矩陣定義知由鄰接矩陣定義知aij是非負(fù)整數(shù)，即鄰接矩陣是非負(fù)整數(shù)是非負(fù)整數(shù)，即鄰接矩陣是非負(fù)整數(shù)矩陣；矩陣； 在圖中點在圖

19、中點vi與與vj鄰接，有鄰接，有vj與與vi鄰接，即鄰接，即aij =aji.所以，鄰接所以，鄰接矩陣是對稱矩陣。矩陣是對稱矩陣。(2) 同一圖的不同形式的鄰接矩陣是相似矩陣。同一圖的不同形式的鄰接矩陣是相似矩陣。 這是因為，同圖的兩種不同形式矩陣可以通過交換行和相這是因為，同圖的兩種不同形式矩陣可以通過交換行和相應(yīng)的列變成一致。應(yīng)的列變成一致。(3) 如果如果G為簡單圖，則為簡單圖，則A(G)為布爾矩陣為布爾矩陣;行和行和(列和列和)等于對等于對應(yīng)頂點的度數(shù)；矩陣元素總和為圖的總度數(shù)，也就是應(yīng)頂點的度數(shù)；矩陣元素總和為圖的總度數(shù)，也就是G的邊的邊數(shù)的數(shù)的2倍。倍。 0.8 1 0.6 0.4

20、 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18(4) G連通的充分必要條件是：連通的充分必要條件是：A(G)不能與如下矩陣相似不能與如下矩陣相似112200AA證明：證明：1) 必要性必要性若不然：設(shè)若不然：設(shè)A11對應(yīng)的頂點是對應(yīng)的頂點是v1,v2, vk , A22對應(yīng)的頂點對應(yīng)的頂點為為vk+1,vk+2, vn顯然，顯然，vi (1ik)ik)與與vj (k+1in)不鄰接，即不鄰接，即G是非連通是非連通圖。矛盾！圖。矛盾！2) 充分性充分性若不然：設(shè)若不然：設(shè)G1與與G2是是G的兩個不連通的部分，并且設(shè)的兩個不連通的部分，并且設(shè)V(G1)=v1

21、,v2,vk, V(G2)=vk+1,vk+2,vn, 如果在寫如果在寫 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19G的鄰接矩陣時，先排的鄰接矩陣時，先排V(G1)中點，再排中點，再排V(G2)中點，則中點，則G的鄰接矩陣形式必為：的鄰接矩陣形式必為：112200AA(5) 定理：設(shè)定理：設(shè) ，則，則a ij (k)表示頂點表示頂點vi到頂點到頂點vj的途徑長度為的途徑長度為k的途徑條數(shù)。的途徑條數(shù)。( )()()kkijAGa證明：對證明：對k作數(shù)學(xué)歸納法證明。作數(shù)學(xué)歸納法證明。當(dāng)當(dāng)k=1時，由鄰接矩陣的定義，結(jié)論成立；時

22、，由鄰接矩陣的定義，結(jié)論成立；設(shè)結(jié)論對設(shè)結(jié)論對k-1時成立。當(dāng)為時成立。當(dāng)為k時：時：一方面：先計算一方面：先計算Ak ; 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20(1)(1)(1)11122kkkkkijijinjnn nAAAaaaaaa另一方面：考慮另一方面：考慮vi到到vj的長度為的長度為k的途徑的途徑設(shè)設(shè)vm是是vi到到vj的途徑中點，且該點和的途徑中點，且該點和vj鄰接。則鄰接。則vi到到vj的經(jīng)的經(jīng)過過vm且長度為且長度為k的途徑數(shù)目應(yīng)該為：的途徑數(shù)目應(yīng)該為：(1)kimm jaa所以，所以，vi到到vj的長

23、度為的長度為k的途徑數(shù)目為：的途徑數(shù)目為：(1)(1)(1)1122kkkijijinjnaaaaaa即為即為( )kija例例4 求下圖中求下圖中v1到到v3的途徑長度為的途徑長度為2和和3的條數(shù)。的條數(shù)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21解：由于：解：由于：v4v1v2v302012011()01011111A G251331614()31223424AG35164121671012()410381212813AG所以，所以，v1到到v3的途徑長度為的途徑長度為2和和3的條數(shù)分別為：的條數(shù)分別為：3和和4。推論

24、推論: (1)A2的元素的元素aii (2)是是vi的度數(shù)，的度數(shù)，A3的元素的元素aii (3)是含是含vi的的三角形個數(shù)的三角形個數(shù)的2倍；倍； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22(2) 若若G是連通的，對于是連通的，對于i j , vi和和vj間距離是使間距離是使An的的aij (n)0的最小整數(shù)。的最小整數(shù)。2、圖的關(guān)聯(lián)矩陣、圖的關(guān)聯(lián)矩陣(1) 若若G是是(n, m) 圖。定義圖。定義G的關(guān)聯(lián)矩陣：的關(guān)聯(lián)矩陣：()()ijn mM Ga其中：其中：,ijijal ve與關(guān)聯(lián)的次數(shù)(0,1,或2(環(huán)）)例如：例

25、如：e1v4v3v2v1e7e5e4e3e2e61 1 0 0 1 0 11 1 1 0 0 0 0( )0 0 1 1 0 0 10 0 0 1 1 2 0M G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23(2) 關(guān)聯(lián)矩陣的性質(zhì)關(guān)聯(lián)矩陣的性質(zhì)1) 關(guān)聯(lián)矩陣的元素為關(guān)聯(lián)矩陣的元素為0，1或或2；2) 關(guān)聯(lián)矩陣的每列和為關(guān)聯(lián)矩陣的每列和為2；每行的和為對應(yīng)頂點度數(shù)；每行的和為對應(yīng)頂點度數(shù)；3) 無環(huán)圖無環(huán)圖G連通的充分必要條件是連通的充分必要條件是R(M) = n-1；證明：證明：令：令：12nmmMm由于由于M中每列恰有兩個中每列恰有兩個“1”元素，所有行向量的和為元素，所有行向量的和為0(模模2加法運(yùn)算加法運(yùn)算)。所以：。所以：()1R Mn 0.8 1 0.6 0.4 0.2 0 x t 0