1、第一章第一章 圖的基本概念圖的基本概念l 圖和簡(jiǎn)單圖圖和簡(jiǎn)單圖l 子圖與圖的運(yùn)算子圖與圖的運(yùn)算l 路與圖的連通性路與圖的連通性l 最短路及其算法最短路及其算法l 圖的代數(shù)表示及其特征圖的代數(shù)表示及其特征l 極圖極圖1.1 圖和簡(jiǎn)單圖圖和簡(jiǎn)單圖 一一、圖的定義圖的定義定義定義 一個(gè)圖一個(gè)圖G 定義為一個(gè)有序?qū)Χx為一個(gè)有序?qū)?V, E)，記為，記為G = (V, E)，其中其中 (1) V 是一個(gè)非空集合，稱為是一個(gè)非空集合，稱為頂點(diǎn)集頂點(diǎn)集或或點(diǎn)集點(diǎn)集，其元素稱為，其元素稱為頂點(diǎn)頂點(diǎn)或或點(diǎn)點(diǎn)；(2) E 是由是由V 中的點(diǎn)組成的無(wú)序點(diǎn)對(duì)構(gòu)成的集合，稱為中的點(diǎn)組成的無(wú)序點(diǎn)對(duì)構(gòu)成的集合，稱為邊集邊

2、集，其元素稱為其元素稱為邊邊，且同一點(diǎn)對(duì)在，且同一點(diǎn)對(duì)在E中可出現(xiàn)多次。中可出現(xiàn)多次。注：注：圖圖G 的頂點(diǎn)集記為的頂點(diǎn)集記為V(G)，邊集記為邊集記為E(G)。圖。圖G 的頂點(diǎn)的頂點(diǎn)數(shù)數(shù)( (或階數(shù)或階數(shù)) )和邊數(shù)可分別用符號(hào)和邊數(shù)可分別用符號(hào)n(G)和和m(G)表示。表示。例例 設(shè)設(shè)V =v1, v2, v3, v4，E =v1v2 , v1v2, v2v3 ，則，則G = (V, E)是是一個(gè)一個(gè)4 4階圖。階圖。若用小圓點(diǎn)代表點(diǎn)，連線代表邊，則可將一個(gè)圖用若用小圓點(diǎn)代表點(diǎn)，連線代表邊，則可將一個(gè)圖用“圖形圖形”來(lái)表示來(lái)表示, , 如例中的圖可表示為如例中的圖可表示為v1v2v3v4注

3、：注：也可記邊也可記邊uv為為e，即，即e = uv。v1v2v3v4e1e2e3e4e5例例 設(shè)設(shè)V = v1,v2,v3,v4，E = e1,e2,e3,e4,e5，其中其中 e1= v1v2，e2 = v2v3， e3 = v2v3， e4 = v3v4， e5 = v4v4，則則G = (V, E)是一個(gè)圖。是一個(gè)圖。(1) 若邊若邊e = uv, , 此時(shí)稱此時(shí)稱u和和v是是e 的的端點(diǎn)端點(diǎn); ; 并稱并稱u和和v相鄰相鄰，u ( (或或v) )與與e相關(guān)聯(lián)相關(guān)聯(lián)。若兩條邊有一個(gè)共同的端點(diǎn)，則稱這兩條。若兩條邊有一個(gè)共同的端點(diǎn)，則稱這兩條邊邊相鄰相鄰。(2) 孤立點(diǎn)：孤立點(diǎn)：不與任何

4、邊相關(guān)聯(lián)的點(diǎn)；不與任何邊相關(guān)聯(lián)的點(diǎn)； 自環(huán)：自環(huán)：兩端點(diǎn)重合的邊；兩端點(diǎn)重合的邊； 重邊：重邊：連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)，叫做邊的連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)，叫做邊的重?cái)?shù)重?cái)?shù)。 重?cái)?shù)大于重?cái)?shù)大于1 1的邊稱為的邊稱為重邊重邊。相關(guān)概念相關(guān)概念(4) 既沒(méi)有環(huán)也沒(méi)有重邊的圖稱為既沒(méi)有環(huán)也沒(méi)有重邊的圖稱為簡(jiǎn)單圖簡(jiǎn)單圖。其他所有的圖都。其他所有的圖都稱為稱為復(fù)合圖。復(fù)合圖。簡(jiǎn)單圖簡(jiǎn)單圖非非簡(jiǎn)單簡(jiǎn)單圖圖例例 平凡圖平凡圖(3) 點(diǎn)集與邊集均為有限集合的圖稱為點(diǎn)集與邊集均為有限集合的圖稱為有限圖有限圖，本書(shū)只討論，本書(shū)只討論有限圖。只有一個(gè)頂點(diǎn)而無(wú)邊的圖稱為有限圖。只有一個(gè)頂點(diǎn)而無(wú)邊的圖稱為平凡圖平凡

5、圖。邊集為空的。邊集為空的圖稱為圖稱為空?qǐng)D空?qǐng)D。二、圖的同構(gòu)二、圖的同構(gòu)定義定義 設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖G1 = (V1, E1)和和G2 = (V2, E2)，若在其頂點(diǎn)，若在其頂點(diǎn)集合之間存在雙射，即存在一一對(duì)應(yīng)的關(guān)系，使得邊之間集合之間存在雙射，即存在一一對(duì)應(yīng)的關(guān)系，使得邊之間有如下的關(guān)系：設(shè)有如下的關(guān)系：設(shè)u1, v1V1 , u2, v2V2, u1 u2, v1 v2, u1v1E1當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)u2v2E2，且，且u1v1的重?cái)?shù)與的重?cái)?shù)與u2v2相等，則稱相等，則稱兩圖同構(gòu)兩圖同構(gòu)，記為，記為G1 G2。例例 注：注：(1) 兩個(gè)同構(gòu)的圖均有相同的結(jié)構(gòu)，沒(méi)有本質(zhì)上的差兩個(gè)同構(gòu)的圖

6、均有相同的結(jié)構(gòu)，沒(méi)有本質(zhì)上的差異異, , 差異只是頂點(diǎn)和邊的名稱不同。差異只是頂點(diǎn)和邊的名稱不同。(2) 圖同構(gòu)的幾個(gè)必要條件：圖同構(gòu)的幾個(gè)必要條件：頂點(diǎn)數(shù)相同；頂點(diǎn)數(shù)相同；邊數(shù)相同；邊數(shù)相同；度數(shù)相等的頂點(diǎn)個(gè)數(shù)相同。度數(shù)相等的頂點(diǎn)個(gè)數(shù)相同。(3) 在圖的圖形表示中我們可以不給圖的點(diǎn)和邊標(biāo)上符號(hào)，稱在圖的圖形表示中我們可以不給圖的點(diǎn)和邊標(biāo)上符號(hào)，稱這樣的圖為這樣的圖為非標(biāo)定（號(hào)）圖非標(biāo)定（號(hào)）圖，否則稱為，否則稱為標(biāo)定（號(hào)）圖標(biāo)定（號(hào)）圖。非標(biāo)。非標(biāo)定圖實(shí)際上是代表一類相互同構(gòu)的圖。定圖實(shí)際上是代表一類相互同構(gòu)的圖。不誤解時(shí)我們也不嚴(yán)不誤解時(shí)我們也不嚴(yán)格區(qū)分標(biāo)定圖與非標(biāo)定圖。格區(qū)分標(biāo)定圖與非標(biāo)

7、定圖。 (4) 判定圖的同構(gòu)是很困難的。對(duì)于規(guī)模不大的兩個(gè)圖，判判定圖的同構(gòu)是很困難的。對(duì)于規(guī)模不大的兩個(gè)圖，判定其是否同構(gòu)，可以采用觀察加推證的方法。定其是否同構(gòu)，可以采用觀察加推證的方法。定義定義 設(shè)設(shè)v為為G的頂點(diǎn)，的頂點(diǎn)，G 中以中以v為端點(diǎn)的邊的條數(shù)為端點(diǎn)的邊的條數(shù)( (環(huán)計(jì)算兩環(huán)計(jì)算兩次次) )稱為點(diǎn)稱為點(diǎn)v的的度數(shù)度數(shù)，簡(jiǎn)稱為點(diǎn)，簡(jiǎn)稱為點(diǎn)v的的度度，記為，記為dG (v)，簡(jiǎn)記為簡(jiǎn)記為d(v)。d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2v1v2v3v4v5例例 注：注：該圖中各點(diǎn)的度數(shù)之和等于該圖中各點(diǎn)的度數(shù)之和等

8、于14，恰好是邊數(shù)，恰好是邊數(shù)7的的兩倍兩倍。例例 證明下面兩圖同構(gòu)。證明下面兩圖同構(gòu)。證明證明 作映射作映射 f : vi ui (i=1,2.,10)，易知該，易知該映射為雙射。映射為雙射。容易驗(yàn)證，對(duì)容易驗(yàn)證，對(duì) vi v j E (a)， 有有 f (vivj) ui uj E(b) ，(1 i 10, 1 j 10 )由圖的同構(gòu)定義知，圖由圖的同構(gòu)定義知，圖(a)與與(b)是同構(gòu)的。是同構(gòu)的。v5v1v2v4v3v10v6v7v8v9(a)u1u2u3u4u5u6u7u8u9u10(b)例例 判斷下面兩圖是否同構(gòu)。判斷下面兩圖是否同構(gòu)。u1v1解解 兩圖不同構(gòu)。兩圖不同構(gòu)。若兩圖同構(gòu)

9、，則兩圖中唯一的與環(huán)關(guān)聯(lián)的兩個(gè)點(diǎn)若兩圖同構(gòu)，則兩圖中唯一的與環(huán)關(guān)聯(lián)的兩個(gè)點(diǎn)u1與與v1一定一定相對(duì)應(yīng)，而相對(duì)應(yīng)，而u1的兩個(gè)鄰接點(diǎn)與的兩個(gè)鄰接點(diǎn)與v1的兩個(gè)鄰接點(diǎn)狀況不同，的兩個(gè)鄰接點(diǎn)狀況不同，u1鄰接有鄰接有4度點(diǎn)，而度點(diǎn)，而v1沒(méi)有。沒(méi)有。所以，兩圖不同構(gòu)。所以，兩圖不同構(gòu)。例例 指出指出4個(gè)頂點(diǎn)的非同構(gòu)的所有簡(jiǎn)單圖。個(gè)頂點(diǎn)的非同構(gòu)的所有簡(jiǎn)單圖。分析：分析：四個(gè)頂點(diǎn)的簡(jiǎn)單圖最少邊數(shù)為四個(gè)頂點(diǎn)的簡(jiǎn)單圖最少邊數(shù)為0，最多邊數(shù)為，最多邊數(shù)為6，所以，所以可按邊數(shù)進(jìn)行枚舉?？砂催厰?shù)進(jìn)行枚舉。解解(a)(b)(c)(d)(e)(f)(g)三、完全圖，偶圖，補(bǔ)圖三、完全圖，偶圖，補(bǔ)圖定義定義 任意兩點(diǎn)

10、均相鄰的簡(jiǎn)單圖稱為任意兩點(diǎn)均相鄰的簡(jiǎn)單圖稱為完全圖完全圖，在同構(gòu)意義，在同構(gòu)意義下，下，n 階完全圖只有一個(gè)，記為階完全圖只有一個(gè)，記為Kn。K2K3K4例例 K2, K3, K4分別為如下圖所示分別為如下圖所示。K30定義定義 若一個(gè)圖的點(diǎn)集可以分解為兩個(gè)（非空）子集若一個(gè)圖的點(diǎn)集可以分解為兩個(gè)（非空）子集X 和和Y，使得每條邊的一個(gè)端點(diǎn)在使得每條邊的一個(gè)端點(diǎn)在X中，另一個(gè)端點(diǎn)在中，另一個(gè)端點(diǎn)在Y中，則這樣中，則這樣的圖稱為的圖稱為具有二分類具有二分類（X, Y）的偶圖（或二部圖）的偶圖（或二部圖）。完全偶圖完全偶圖是指具有二分類是指具有二分類(X, Y )的簡(jiǎn)單偶圖，其中的簡(jiǎn)單偶圖，其中X

11、的的每個(gè)頂點(diǎn)與每個(gè)頂點(diǎn)與Y 的每個(gè)頂點(diǎn)相連，若的每個(gè)頂點(diǎn)相連，若 |X|=m，|Y|=n，則這，則這樣的偶圖記為樣的偶圖記為Km,n。例例偶圖偶圖不是偶圖例例 K3, 3 K1, 3 G1 G2 四個(gè)圖均為偶圖四個(gè)圖均為偶圖K1, 3, K3, 3為完全偶圖為完全偶圖 偶圖是一種常見(jiàn)數(shù)學(xué)模型。偶圖是一種常見(jiàn)數(shù)學(xué)模型。例例 學(xué)校有學(xué)校有6位教師將開(kāi)設(shè)位教師將開(kāi)設(shè)6門(mén)課程。六位教師的代號(hào)分別是門(mén)課程。六位教師的代號(hào)分別是xi (i=1,2,3,4,5,6 )，六門(mén)課程代號(hào)是，六門(mén)課程代號(hào)是yi (i=1,2,3,4,5,6 )。已知教。已知教師師x1能夠勝任課程能夠勝任課程y2和和y3；教師；教師

12、x2能夠勝任課程能夠勝任課程y4和和y5；教師；教師x3能夠勝任課程能夠勝任課程y2；教師；教師x4能夠勝任課程能夠勝任課程y6和和y3；教師；教師x5能夠能夠勝任課程勝任課程y1和和y6；教師；教師x6能夠勝任課程能夠勝任課程y5和和y6。請(qǐng)畫(huà)出老師和。請(qǐng)畫(huà)出老師和課程之間的狀態(tài)圖。課程之間的狀態(tài)圖。解解x1x5x4x3x2x6y4y3y1y2y5y61, ,Euv uv u vV簡(jiǎn)單圖簡(jiǎn)單圖G 的的補(bǔ)圖：補(bǔ)圖：設(shè)設(shè)G =(V, E) )，則圖，則圖H =(V, E1E)稱為稱為G 的的補(bǔ)圖，記為補(bǔ)圖，記為 ，其中集合，其中集合HG例例 下圖中的下圖中的(a)，(b)兩圖是互補(bǔ)的。兩圖是互補(bǔ)

13、的。(a)(b)定理定理 若若n 階圖階圖G是自補(bǔ)的（即是自補(bǔ)的（即 ），則），則 n = 0, 1 (mod 4)。GG證明證明 因?yàn)橐驗(yàn)镚 是自補(bǔ)的，則是自補(bǔ)的，則G 和其補(bǔ)圖有同樣多的邊數(shù)，且和其補(bǔ)圖有同樣多的邊數(shù)，且邊數(shù)邊數(shù)(1)( )( )()2nn nm Gm Gm K。從而從而(1)()4n nm G。又因又因G的邊數(shù)的邊數(shù)m(G)是整數(shù)，故是整數(shù)，故n(n-1)/4為整數(shù)，即只能有為整數(shù)，即只能有n0 (mod 4) 或或 (n-1)0 (mod 4)。 四、頂點(diǎn)的度、度序列四、頂點(diǎn)的度、度序列設(shè)設(shè)v為為G 的頂點(diǎn)，的頂點(diǎn)，G 中以中以v為端點(diǎn)的邊的條數(shù)為端點(diǎn)的邊的條數(shù)( (環(huán)

14、計(jì)算兩次環(huán)計(jì)算兩次) )稱稱為點(diǎn)為點(diǎn)v的度數(shù)，簡(jiǎn)稱為點(diǎn)的度數(shù)，簡(jiǎn)稱為點(diǎn)v的的度度，記為，記為dG (v)，簡(jiǎn)記為簡(jiǎn)記為d(v)。奇點(diǎn)：奇點(diǎn)：度數(shù)為奇數(shù)的頂點(diǎn)度數(shù)為奇數(shù)的頂點(diǎn)相關(guān)術(shù)語(yǔ)和記號(hào)相關(guān)術(shù)語(yǔ)和記號(hào) G：圖圖G 的頂點(diǎn)的最小度的頂點(diǎn)的最小度 G：圖圖G 的頂點(diǎn)的最大度的頂點(diǎn)的最大度偶點(diǎn)：偶點(diǎn)：度數(shù)為偶數(shù)的頂點(diǎn)度數(shù)為偶數(shù)的頂點(diǎn)k-正則圖正則圖: : 每個(gè)點(diǎn)的度均為每個(gè)點(diǎn)的度均為k 的的簡(jiǎn)單圖簡(jiǎn)單圖例如，完全圖和完全偶圖例如，完全圖和完全偶圖Kn, n 均是正則圖。均是正則圖。 推論推論 任意圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。任意圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。證明證明 設(shè)設(shè)V1，V2分別是分別是G 中偶點(diǎn)集和奇

15、點(diǎn)集。則由握手定理中偶點(diǎn)集和奇點(diǎn)集。則由握手定理知：知： 12v Vv Vd vd v偶數(shù)。顯然第一個(gè)求和式為偶數(shù)，而第二個(gè)求和式中的每一項(xiàng)均顯然第一個(gè)求和式為偶數(shù)，而第二個(gè)求和式中的每一項(xiàng)均為奇數(shù)，所以第二個(gè)求和式必然有偶數(shù)項(xiàng)，即度數(shù)為奇數(shù)為奇數(shù)，所以第二個(gè)求和式必然有偶數(shù)項(xiàng)，即度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)必為偶數(shù)。的頂點(diǎn)個(gè)數(shù)必為偶數(shù)。推論推論 正則圖的階數(shù)和度數(shù)不同時(shí)為奇數(shù)。正則圖的階數(shù)和度數(shù)不同時(shí)為奇數(shù)。證明證明 設(shè)設(shè)G 是是k- -正則圖，若正則圖，若k 為奇數(shù)，則由推論知正則圖為奇數(shù)，則由推論知正則圖G的點(diǎn)數(shù)必為偶數(shù)。的點(diǎn)數(shù)必為偶數(shù)。 例例 設(shè)設(shè)與與是簡(jiǎn)單圖是簡(jiǎn)單圖G 的最大度與最小度，求證

16、：的最大度與最小度，求證： 2 mn 。()()2vVGndvmn，證明證明 由握手定理知由握手定理知所以所以2 mn 。定義定義 一個(gè)圖一個(gè)圖G 的各個(gè)點(diǎn)的度的各個(gè)點(diǎn)的度d1, d2, dn構(gòu)成的非負(fù)整數(shù)組構(gòu)成的非負(fù)整數(shù)組(d1, d2, dn)稱為稱為G 的的度序列度序列。定理定理 非負(fù)整數(shù)組非負(fù)整數(shù)組(d1, d2,.,dn)是圖的度序列的充分必要條件是圖的度序列的充分必要條件是：是：di 為偶數(shù)。為偶數(shù)。證明證明 必要性由握手定理立即得到。必要性由握手定理立即得到。如果如果di為偶數(shù)，則數(shù)組中為奇數(shù)的數(shù)字個(gè)數(shù)必為偶數(shù)。為偶數(shù)，則數(shù)組中為奇數(shù)的數(shù)字個(gè)數(shù)必為偶數(shù)。按照如下方式作圖按照如下方

17、式作圖G: 若若di為偶數(shù)，則在與之對(duì)應(yīng)的點(diǎn)作為偶數(shù)，則在與之對(duì)應(yīng)的點(diǎn)作di /2個(gè)環(huán)；對(duì)于剩下的偶數(shù)個(gè)奇數(shù)，個(gè)環(huán)；對(duì)于剩下的偶數(shù)個(gè)奇數(shù)，兩兩配對(duì)后分別在每配對(duì)兩兩配對(duì)后分別在每配對(duì)點(diǎn)間先連一條邊，然后在每個(gè)頂點(diǎn)畫(huà)點(diǎn)間先連一條邊，然后在每個(gè)頂點(diǎn)畫(huà)(dj - -1)/2個(gè)環(huán)。個(gè)環(huán)。該圖的度序列就是已知數(shù)組。該圖的度序列就是已知數(shù)組。定義定義 對(duì)于一個(gè)非負(fù)整數(shù)組對(duì)于一個(gè)非負(fù)整數(shù)組(d1, d2, dn)，若存在一個(gè)，若存在一個(gè)簡(jiǎn)單簡(jiǎn)單圖圖G，以它為度序列，則稱這個(gè)數(shù)組是，以它為度序列，則稱這個(gè)數(shù)組是可圖的可圖的?？蓤D的序列。可圖的序列簡(jiǎn)稱為簡(jiǎn)稱為可圖序列可圖序列或或圖序列圖序列。關(guān)于可圖序列，主要

18、研究關(guān)于可圖序列，主要研究3個(gè)問(wèn)題：個(gè)問(wèn)題：(1) 存在問(wèn)題存在問(wèn)題：什么樣的整數(shù)組是可圖序列？：什么樣的整數(shù)組是可圖序列？(2) 計(jì)數(shù)問(wèn)題計(jì)數(shù)問(wèn)題：一個(gè)可圖序列對(duì)應(yīng)多少不同構(gòu)的圖？：一個(gè)可圖序列對(duì)應(yīng)多少不同構(gòu)的圖？(3) 構(gòu)造問(wèn)題構(gòu)造問(wèn)題：如何畫(huà)出可圖序列對(duì)應(yīng)的所有不同構(gòu)圖？：如何畫(huà)出可圖序列對(duì)應(yīng)的所有不同構(gòu)圖？(1)徹底解決了；徹底解決了；(2)解決得不好；解決得不好；(3)沒(méi)有解決。沒(méi)有解決。研究現(xiàn)狀研究現(xiàn)狀定理定理 設(shè)有非負(fù)整數(shù)組設(shè)有非負(fù)整數(shù)組= (d1, d2, dn)滿足滿足1212ninddddm且，則則是可圖序列的充分必要條件是：是可圖序列的充分必要條件是：1112312(1,

19、1,1,)ddnddddd 是可圖序列。是可圖序列。證明證明 充分性顯然，我們只需證明必要性。充分性顯然，我們只需證明必要性。設(shè)設(shè)G 是是對(duì)應(yīng)的簡(jiǎn)單圖，對(duì)應(yīng)的簡(jiǎn)單圖，d (vi)=di 。情形情形1：點(diǎn)點(diǎn)v1與點(diǎn)與點(diǎn)v2, v3,vd1+1鄰接，則刪去頂點(diǎn)鄰接，則刪去頂點(diǎn)v1及其關(guān)聯(lián)及其關(guān)聯(lián)的邊所得到的圖的度序列正好為的邊所得到的圖的度序列正好為1。情形情形2：點(diǎn)點(diǎn)v1與點(diǎn)與點(diǎn)vd1+2,vn 的某些頂點(diǎn)鄰接。的某些頂點(diǎn)鄰接。假設(shè)：假設(shè)：設(shè)設(shè)v1與與vj0鄰接，但當(dāng)鄰接，但當(dāng)kj0 時(shí)，時(shí)，v1與與vk不鄰接；又設(shè)不鄰接；又設(shè)v1與與vi0不鄰接，但當(dāng)不鄰接，但當(dāng)k2。(非連通圖的直徑定義為非

20、連通圖的直徑定義為)不妨假設(shè)不妨假設(shè)u和和v1, v2,vk相鄰。相鄰。為了保證為了保證u到各點(diǎn)距離不超過(guò)到各點(diǎn)距離不超過(guò)2，vk+1,.vn-2這些頂點(diǎn)的每一這些頂點(diǎn)的每一個(gè)必須和前面?zhèn)€必須和前面v1, v2, vk中某點(diǎn)相鄰，這樣，圖中至少又有中某點(diǎn)相鄰，這樣，圖中至少又有n- -2條邊。條邊。因此，總共至少有因此，總共至少有2n- -4條邊。條邊。定理定理 若圖若圖G 是不連通的，則其補(bǔ)圖是連通圖。是不連通的，則其補(bǔ)圖是連通圖。證明證明 因因G是不連通，故是不連通，故G中至少兩個(gè)分支。中至少兩個(gè)分支。設(shè)設(shè)u，v是是G 的任意兩個(gè)頂點(diǎn)。的任意兩個(gè)頂點(diǎn)。若若u和和v在在G中不鄰接，則在補(bǔ)圖中

21、它們鄰接。中不鄰接，則在補(bǔ)圖中它們鄰接。若若u和和v在在G中鄰接，則它們屬于中鄰接，則它們屬于G的同一分支。的同一分支。在另一個(gè)分支中取一點(diǎn)在另一個(gè)分支中取一點(diǎn)w，則在補(bǔ)圖中，則在補(bǔ)圖中u和和v均與均與w鄰接，從鄰接，從而而uwv是一條途徑是一條途徑, 故在補(bǔ)圖中它們鄰接。故在補(bǔ)圖中它們鄰接。因此因此G的補(bǔ)圖是連通圖。的補(bǔ)圖是連通圖。定理定理 設(shè)圖設(shè)圖G為為n階圖，若階圖，若G中任意兩個(gè)不相鄰頂點(diǎn)中任意兩個(gè)不相鄰頂點(diǎn)u與與v滿足滿足d(u)+d(v)n- -1，則，則G是連通圖且是連通圖且d(G)2。證明證明 我們將證明，對(duì)我們將證明，對(duì)G中任意兩點(diǎn)中任意兩點(diǎn)x與與y，一定存在一條長(zhǎng)，一定存在

22、一條長(zhǎng)度至多為度至多為2的連接的連接x與與y的路。的路。若若x和和y相鄰，則上述論斷成立。相鄰，則上述論斷成立。若若x和和y不相鄰，則一定存在一點(diǎn)不相鄰，則一定存在一點(diǎn)w與與x和和y均相鄰。均相鄰。若不然，在若不然，在G的剩下的的剩下的n-2個(gè)頂點(diǎn)中，假設(shè)有個(gè)頂點(diǎn)中，假設(shè)有k個(gè)與個(gè)與x鄰接，但鄰接，但與與y不鄰接，有不鄰接，有l(wèi)個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和y鄰接，但不與鄰接，但不與x鄰接，同時(shí)假定有鄰接，同時(shí)假定有m個(gè)頂點(diǎn)與個(gè)頂點(diǎn)與x和和y均不相鄰。均不相鄰。那么那么d(x)=k，d(y)=l。由于由于k+l+m=n- -2，所以，所以d(x)+d(y)=n- -2- -mn- -2，矛盾！，矛盾！三、偶

23、圖判定定理三、偶圖判定定理定理定理 一個(gè)圖是偶圖當(dāng)且當(dāng)它不包含奇圈。一個(gè)圖是偶圖當(dāng)且當(dāng)它不包含奇圈。證明證明 一個(gè)圖是偶圖當(dāng)且僅當(dāng)每個(gè)連通分支是偶圖，一個(gè)圈一個(gè)圖是偶圖當(dāng)且僅當(dāng)每個(gè)連通分支是偶圖，一個(gè)圈只能屬于一個(gè)連通分支，因此我們只需對(duì)連通圖證明即可。只能屬于一個(gè)連通分支，因此我們只需對(duì)連通圖證明即可。設(shè)設(shè)G是具有二分類是具有二分類(X, Y)的偶圖，并且的偶圖，并且C = v0v1vkv0是是G的任的任意一個(gè)圈。意一個(gè)圈。不失一般性，可假定不失一般性，可假定v0X。這樣，。這樣，v2iX，且，且v2i +1Y。又因?yàn)橛忠驗(yàn)関0X，所以，所以vkY。由此即得。由此即得C是偶圈。是偶圈。接下來(lái)

24、證明充分性。接下來(lái)證明充分性。設(shè)設(shè)G是不包含奇圈的連通圖。是不包含奇圈的連通圖。任選一個(gè)頂點(diǎn)任選一個(gè)頂點(diǎn)u且定義且定義V 的一個(gè)分類的一個(gè)分類（X, Y）如下：如下：X = x | d (u, x) 是偶數(shù)，是偶數(shù)，xV(G) ，Y = y | d (u, y) 是奇數(shù)，是奇數(shù)，yV(G) 。現(xiàn)在證明現(xiàn)在證明( X, Y )是是G的一個(gè)二分類。的一個(gè)二分類。斷言：斷言：對(duì)對(duì)X中任意兩點(diǎn)中任意兩點(diǎn)v與與w，必不相鄰！，必不相鄰！設(shè)設(shè)P是一條最短是一條最短(u , v)路，而路，而Q是一條最短是一條最短的的(u, w)路。路。設(shè)設(shè)u1是是P和和Q的最后一個(gè)交點(diǎn)。的最后一個(gè)交點(diǎn)。由于由于P，Q是最短

25、路，所以是最短路，所以P，Q中中u到到u1段長(zhǎng)段長(zhǎng)度相同，因此奇偶性相同。度相同，因此奇偶性相同。又因?yàn)橛忠驗(yàn)镻，Q的長(zhǎng)度均是偶數(shù)，所以的長(zhǎng)度均是偶數(shù)，所以P，Q中中u1v段和段和u1w段段奇偶性相同。奇偶性相同。 如果如果v與與w相鄰，則可得到奇圈，矛盾！相鄰，則可得到奇圈，矛盾！所以所以(X, Y )是是G的一個(gè)二分類。的一個(gè)二分類。類似地，類似地，Y中任意兩個(gè)頂點(diǎn)也不相鄰。中任意兩個(gè)頂點(diǎn)也不相鄰。QPvuwu11.4 最短路及其算法最短路及其算法定義定義 若圖若圖G的每一條邊的每一條邊e都附有一個(gè)實(shí)數(shù)都附有一個(gè)實(shí)數(shù)w(e)，稱為稱為e的的權(quán)權(quán),則則G連同它邊上的權(quán)稱為連同它邊上的權(quán)稱為賦

26、權(quán)圖賦權(quán)圖。若若H是一個(gè)賦權(quán)圖，則是一個(gè)賦權(quán)圖，則H的各邊權(quán)之和稱為的各邊權(quán)之和稱為圖圖H的權(quán)的權(quán)，記為，記為W(H)。例例 右圖右圖G為賦權(quán)圖，為賦權(quán)圖，v1v3v2v4 G 1 3 5 6 5其中其中w(v1v2) = 1，w(v1v3) = 5，W(G) = 20。一、一、 賦權(quán)圖賦權(quán)圖 定義定義 設(shè)設(shè)G為賦權(quán)圖，為賦權(quán)圖，u與與v是是G中兩點(diǎn)，在連接中兩點(diǎn)，在連接u與與v的所有路的所有路中，各邊權(quán)值之和最小的路，稱為中，各邊權(quán)值之和最小的路，稱為u與與v間的間的最短路最短路，最短路，最短路的長(zhǎng)度稱為的長(zhǎng)度稱為u與與v的的距離距離，仍記為，仍記為 d(u, v)。例例 求求v2與與 v4

27、的距離。的距離。v1v3v2v4 G 1 3 1 6 3易知，各邊的權(quán)均為易知，各邊的權(quán)均為1的賦權(quán)圖中的路長(zhǎng)與非賦權(quán)圖中的的賦權(quán)圖中的路長(zhǎng)與非賦權(quán)圖中的路長(zhǎng)是一致的。路長(zhǎng)是一致的。解解 d(v2, v4) = 5。相應(yīng)的最短路為相應(yīng)的最短路為 ：v2v1v3v4。二、最短路問(wèn)題二、最短路問(wèn)題 許多最優(yōu)化問(wèn)題都可轉(zhuǎn)化為在一個(gè)賦權(quán)圖中找出某類具有最許多最優(yōu)化問(wèn)題都可轉(zhuǎn)化為在一個(gè)賦權(quán)圖中找出某類具有最?。ɑ蜃畲螅?quán)的子圖，其中之一就是?。ɑ蜃畲螅?quán)的子圖，其中之一就是最短路問(wèn)題：給出一最短路問(wèn)題：給出一個(gè)連接各城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)之間個(gè)連接各城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定

28、城鎮(zhèn)之間試確定一條最短路線。試確定一條最短路線。數(shù)學(xué)模型：數(shù)學(xué)模型：在一個(gè)賦權(quán)圖中的兩個(gè)指定頂點(diǎn)在一個(gè)賦權(quán)圖中的兩個(gè)指定頂點(diǎn)a和和b之間找出一之間找出一條最短條最短(a, b)路。路。1959年，年，Dijkstra發(fā)表了一篇名為發(fā)表了一篇名為“A Note on Two Problems in Connexion with Graphs ”，這篇僅有兩頁(yè)半的文章發(fā)表在，這篇僅有兩頁(yè)半的文章發(fā)表在一流一流期刊期刊Numerische mathematik 上面。上面。這篇文章給出了解決最短路問(wèn)題的著名的這篇文章給出了解決最短路問(wèn)題的著名的Dijkstra算法算法，同，同時(shí)指出：在此之前時(shí)指出：

29、在此之前Ford和和Berge已經(jīng)分別給出了解決最短路已經(jīng)分別給出了解決最短路問(wèn)題的方法。問(wèn)題的方法。巧合的是，同年巧合的是，同年11月，月，“線性規(guī)劃之父線性規(guī)劃之父”Dantzig提交了一提交了一篇名為篇名為“ On the Shortest Path Route Through a Network ”的論文的論文，該論文第二年正式發(fā)表在，該論文第二年正式發(fā)表在Top期刊期刊Management Science上面。上面。該論文只有三頁(yè)半，也提出了解決最短路問(wèn)題的算法，同時(shí)該論文只有三頁(yè)半，也提出了解決最短路問(wèn)題的算法，同時(shí)也提到也提到Ford的工作。的工作。2003年，年，Dantzig

30、在其著作在其著作Linear Programming中曾提中曾提到到“About the same time, Dijkstra independently proposed a refined version of the same algorithm for finding the shortestdirected paths from a node to all other nodes.”，但，但Dantzig并未給出具有說(shuō)服力的依據(jù)。并未給出具有說(shuō)服力的依據(jù)。但肯定的是，但肯定的是，F(xiàn)ord在在Network Flow Theory方面的工作是最方面的工作是最短路問(wèn)題的先驅(qū)，也是短路問(wèn)

31、題的先驅(qū)，也是Dijkstra和和Dantzig工作的基礎(chǔ)。工作的基礎(chǔ)。Dantzig算法算法( (頂點(diǎn)標(biāo)號(hào)法頂點(diǎn)標(biāo)號(hào)法) ) t (ak)：點(diǎn)：點(diǎn)ak的標(biāo)號(hào)值，表示點(diǎn)的標(biāo)號(hào)值，表示點(diǎn)a1=a 到到ak的最短路長(zhǎng)度；的最短路長(zhǎng)度；Ai =a1, a2,., ai：已經(jīng)標(biāo)號(hào)的頂點(diǎn)集合；：已經(jīng)標(biāo)號(hào)的頂點(diǎn)集合；Ti ：a1到到ai的最短路上的邊所在的集合；的最短路上的邊所在的集合； l(e)：邊：邊e的權(quán)重；的權(quán)重；記號(hào)說(shuō)明記號(hào)說(shuō)明：Dantzig算法不僅找到了最短的算法不僅找到了最短的(a, b)路，而且給出了路，而且給出了a到圖到圖G的所有其他頂點(diǎn)的最短路。的所有其他頂點(diǎn)的最短路。 N(ak)：

32、與點(diǎn)：與點(diǎn)ak相鄰的所有點(diǎn)的集合，稱為相鄰的所有點(diǎn)的集合，稱為ak的鄰集的鄰集。Dantzig算法算法(1) 記記 a1=a, t(a1) =0, A1= a1, T1= ;(2) 若已經(jīng)得到若已經(jīng)得到Ai = a1, a2, ai ，且對(duì)于，且對(duì)于 1ki，已知已知 t(ak)。對(duì)每一個(gè)對(duì)每一個(gè)ak Ai，求一點(diǎn)：，求一點(diǎn)：( )( )()iikkikbN aAB使得：使得：()()()m in()ikikkkvBlablav；(3) 設(shè)有設(shè)有mi ，1mii，而，而bmi(i)是使是使 取最小取最小值。令：值。令：( )()()iiiimmmt al a b( )11111, ()()()

33、, iiiiiimimmiiimiabt at al a aTTa a；(4) 若若ai+1=b， 停止；否則，記停止；否則，記 ， 轉(zhuǎn)轉(zhuǎn)(2)。11iiiAAa例例 如圖所示，求點(diǎn)如圖所示，求點(diǎn)a到點(diǎn)到點(diǎn)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;解解14. A2 =a, v3， b1 (2) =v1，b2 (2) =v2 ；812614227924693av1v2

34、v3v4v5v6b15. m2 = 1，a3 = v1， t(v1) = t(a) + l(av1) = 2 (最小最小)， T3 =av3, av1； 6. A3 =a, v3, v1，b1 (3) =v2，b2 (3) =v2， b3 (3) =v4 ； 7. m3 = 3, a4 = v4, t(v4) = t(v1) + l(v1v4) = 3 (最小最小)， T4 =av3, av1, v1v4 8. A4 = a, v3, v1, v4，b1 (4) = v2，b2 (4) = v2，b3 (4) = v2, b4 (4) = v5 ；9. m4 = 4, a5 = v5, t(v

35、5) = t(v4) + l(v4v5) = 6 (最小最小)， T5 =av3, av1, v1v4, v4v5 ;236236812614227924693av1v2v3v4v5v6b110. A5 = a, v3, v1, v4, v5，b1 (5) = v2，b2 (5) = v2，b3 (5) = v2 , b4 (5) = v2, b5 (5) = v2 ;11. m5 = 4, a6 = v2, t(v2) = t(v4) + l(v4v2) = 7 (最小最小)， T6 =av3, av1, v1v4, v4v5, v4v2;12. A6 = a, v3, v1, v4, v5

36、, v2, b2 (6) = v6, b4 (6) = b，b5 (6) = v6， b6 (6) = v6 ;13. m6 = 6, a7 = v6, t(v6) = t(v2) + l(v2v6) = 9 (最小最小)， 7914. A7 = a, v3, v1, v4, v5, v2, v6, b4 (7) = b，b5 (7) =b，b7 (7) =b ;15. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小最小)， T8 =av3, av1, v1v4, v4v5, v4v2, v2v6, v6b;于是知于是知a與與b的距離的距離d (

37、a, b) = t (b) = 11，最短路為，最短路為 1426avvvvb 。T7 =av3, av1, v1v4, v4v5, v4v2, v2v6 ;1179236812614227924693av1v2v3v4v5v6b11.5 圖的代數(shù)表示及特征圖的代數(shù)表示及特征一、一、 鄰接矩陣鄰接矩陣定義定義 設(shè)設(shè)n階標(biāo)定圖階標(biāo)定圖G = (V, E)，V = v1, v2, vn，則則G的的鄰鄰接矩陣接矩陣是一個(gè)是一個(gè)nn 矩陣矩陣A(G) = aij (簡(jiǎn)記為簡(jiǎn)記為A)，其中若，其中若 vi鄰接鄰接vj，則，則aij =1；否則；否則aij =0。注：注：若若aij 取為連接取為連接vi與

38、與vj 的邊的數(shù)目，則稱的邊的數(shù)目，則稱A為為推廣的鄰接推廣的鄰接矩陣矩陣。 用鄰接矩陣或關(guān)聯(lián)矩陣表示圖，稱為用鄰接矩陣或關(guān)聯(lián)矩陣表示圖，稱為圖的代數(shù)表示圖的代數(shù)表示。用矩陣表示圖，主要有兩個(gè)優(yōu)點(diǎn)：用矩陣表示圖，主要有兩個(gè)優(yōu)點(diǎn)： (1) 能夠把圖輸入到計(jì)能夠把圖輸入到計(jì)算機(jī)中；算機(jī)中；(2) 可以用代數(shù)方法研究圖論?？梢杂么鷶?shù)方法研究圖論。鄰接矩陣鄰接矩陣 推廣的鄰接矩陣推廣的鄰接矩陣 v1v2v4v3e1e2e3e4e5例例0100101001010011A0100102002010011A(1) 鄰接矩陣是一個(gè)對(duì)稱方陣。鄰接矩陣是一個(gè)對(duì)稱方陣。 (2) 簡(jiǎn)單標(biāo)定圖的鄰接矩陣的各行簡(jiǎn)單標(biāo)定圖

39、的鄰接矩陣的各行 (列列) 元素之和是該行元素之和是該行 (列列) 對(duì)應(yīng)的點(diǎn)的度。對(duì)應(yīng)的點(diǎn)的度。 (3) 若若A1和和A2是對(duì)應(yīng)于同一個(gè)是對(duì)應(yīng)于同一個(gè)圖圖的兩種不同的標(biāo)定的鄰的兩種不同的標(biāo)定的鄰接矩陣，則接矩陣，則 A1和和A2 是相似的，即是相似的，即存在一個(gè)可逆矩存在一個(gè)可逆矩陣陣P使得使得A1=P- -1A2P。(4) G是連通的當(dāng)且僅當(dāng)沒(méi)有是連通的當(dāng)且僅當(dāng)沒(méi)有G的點(diǎn)的一種標(biāo)定法使它的點(diǎn)的一種標(biāo)定法使它 的鄰接矩陣有約化的形式的鄰接矩陣有約化的形式112200AAA。鄰接矩陣的性質(zhì)鄰接矩陣的性質(zhì)v1到到v1的長(zhǎng)為的長(zhǎng)為2的通道的數(shù)目為的通道的數(shù)目為1 v1到到v2的長(zhǎng)為的長(zhǎng)為2的通道的數(shù)

40、目為的通道的數(shù)目為0v1到到v3的長(zhǎng)為的長(zhǎng)為2的通道的數(shù)目為的通道的數(shù)目為2v1到到v4的長(zhǎng)為的長(zhǎng)為2的通道的數(shù)目為的通道的數(shù)目為0 v2到到v2的長(zhǎng)為的長(zhǎng)為2的通道的數(shù)目為的通道的數(shù)目為5 v1v2v4v3e1e2e3e4e5左圖的推廣的鄰接矩陣為左圖的推廣的鄰接矩陣為0100102002010011A例例計(jì)算得計(jì)算得21020050220510212A圖中圖中定理定理 令令G是一個(gè)有推廣鄰接矩陣是一個(gè)有推廣鄰接矩陣A的的 p階標(biāo)定圖，則階標(biāo)定圖，則An的的i 行行 j 列元素列元素aij(n)等于由等于由vi到到vj的長(zhǎng)度為的長(zhǎng)度為n的通道的數(shù)目。的通道的數(shù)目。證明證明 當(dāng)當(dāng)n = 0時(shí)，

41、時(shí)，A0 = In (n階單位矩陣階單位矩陣)，從任一點(diǎn)到自身有，從任一點(diǎn)到自身有一條長(zhǎng)度為零的通道，任何不同的兩點(diǎn)間沒(méi)有長(zhǎng)度為零的一條長(zhǎng)度為零的通道，任何不同的兩點(diǎn)間沒(méi)有長(zhǎng)度為零的通道，從而命題對(duì)通道，從而命題對(duì)n = 0成立。成立。由于由于aik是聯(lián)結(jié)是聯(lián)結(jié)vi和和vk的長(zhǎng)度為的長(zhǎng)度為1的通道的數(shù)目，的通道的數(shù)目，akj(n)是聯(lián)結(jié)是聯(lián)結(jié)vk和和vj的長(zhǎng)度為的長(zhǎng)度為n的通道的數(shù)目，所以的通道的數(shù)目，所以 aikakj(n) 表示由表示由vi經(jīng)過(guò)經(jīng)過(guò)vk到到vj的長(zhǎng)度為的長(zhǎng)度為n+1的通道的通道數(shù)目。數(shù)目。假設(shè)命題對(duì)假設(shè)命題對(duì)n成立，由成立，由An+1=AAn，故，故(1)( )1pnnij

42、ikkjkaa a。這表明命題對(duì)這表明命題對(duì)n+1成立。成立。于是對(duì)所有的于是對(duì)所有的k求和便得到求和便得到了由了由 vi 到到 vj 的長(zhǎng)度為的長(zhǎng)度為n+1的通道的通道數(shù)目，即數(shù)目，即 aij(n+1) 為由為由 vi 到到 vj 的長(zhǎng)度為的長(zhǎng)度為n+1的通道的通道數(shù)目。數(shù)目。推論推論 設(shè)設(shè)A為簡(jiǎn)單圖為簡(jiǎn)單圖G的鄰接矩陣，則的鄰接矩陣，則(1) A2 的元素的元素 aii(2) 是是 vi 的度數(shù)。的度數(shù)。A3 的元素的元素 aii(3) 是含是含 vi 的三角的三角形的數(shù)目的兩倍。形的數(shù)目的兩倍。(2) 若若G是連通的，對(duì)于是連通的，對(duì)于ij，vi 與與vj 之間的距離是使之間的距離是使A

43、n 的的aij(n) 0 的最小整數(shù)的最小整數(shù)n。二、關(guān)聯(lián)矩陣二、關(guān)聯(lián)矩陣定義定義 無(wú)環(huán)圖無(wú)環(huán)圖G的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣B(G) = bij (簡(jiǎn)記為簡(jiǎn)記為B)是一個(gè)是一個(gè)nm 矩陣，當(dāng)點(diǎn)矩陣，當(dāng)點(diǎn)vi 與邊與邊ej 關(guān)聯(lián)時(shí)關(guān)聯(lián)時(shí) bij =1，否則，否則 bij =0。例例B = e1 e2 e3 e4 e5 e6 e7v1v2v3v4v500110001001100010011000000111110001注：注：定義中定義中“無(wú)無(wú)環(huán)環(huán)”的條件可去掉，此時(shí)的條件可去掉，此時(shí)bij =點(diǎn)點(diǎn)vi 與邊與邊ej 關(guān)關(guān)聯(lián)的次數(shù)（聯(lián)的次數(shù)（0, 1, 2(環(huán)環(huán))）。）。例例e1v4v3v2v1e7e5

44、e4e3e2e61 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 e1 e5v2 v5 e6 e7 e2 e4v1v3 e3 v4性質(zhì)性質(zhì) 關(guān)聯(lián)矩陣的每列和為關(guān)聯(lián)矩陣的每列和為2；其行和為對(duì)應(yīng)頂點(diǎn)的度數(shù)。；其行和為對(duì)應(yīng)頂點(diǎn)的度數(shù)。三、鄰接譜三、鄰接譜12121( )( )nnnnnf GE AGaaaa定義定義 圖的鄰接矩陣圖的鄰接矩陣A(G)的特征多項(xiàng)式：的特征多項(xiàng)式：稱為稱為圖圖G的特征多項(xiàng)式的特征多項(xiàng)式。定義定義 圖的鄰接矩陣圖的鄰接矩陣A(G)的特征多項(xiàng)式的特征值及其重?cái)?shù)，的特征多項(xiàng)式的特征值及其重?cái)?shù)，稱為稱為圖圖G的

45、鄰接譜的鄰接譜，簡(jiǎn)稱，簡(jiǎn)稱譜譜，記為，記為Spec(G)。例例 求求Kn的譜。的譜。0111110111()11110nA K解解 Kn的鄰接矩陣為：的鄰接矩陣為：計(jì)算得計(jì)算得11111111()(1)(1)1111nnEA Kn -1。因此因此11Spec()11nnKn。例例 若兩個(gè)非同構(gòu)的圖具若兩個(gè)非同構(gòu)的圖具有相同的譜，則稱它們有相同的譜，則稱它們是同譜圖。求證：右面是同譜圖。求證：右面兩圖是同譜圖。兩圖是同譜圖。GH解解 G與與H顯然不同構(gòu)。顯然不同構(gòu)。通過(guò)直接計(jì)算得通過(guò)直接計(jì)算得6432( )()74741f GfH 。所以所以G與與H是同譜圖。是同譜圖。例例 設(shè)簡(jiǎn)單圖設(shè)簡(jiǎn)單圖G=

46、(n, m)的譜為的譜為1212Spec( )ssGmmm，則則212siiimm。證明證明 因因A的各特征值的平方組成矩陣的各特征值的平方組成矩陣A2的特征值，所以的特征值，所以2(2)11sniiiiiima。又因?yàn)橛忠驗(yàn)锳2的對(duì)角線元素的和為的對(duì)角線元素的和為(2)11( )2nniiiiiad vm，因此因此212siiimm。例例 設(shè)設(shè)是簡(jiǎn)是簡(jiǎn)單圖單圖G=(n, m)的任意特征值，則：的任意特征值，則：2(1)m nn。證明證明 設(shè)設(shè)=1, 2, ,n是是G 的全部特征值。的全部特征值。因?yàn)橐驗(yàn)镚是簡(jiǎn)是簡(jiǎn)單圖，從而單圖，從而A(G)的對(duì)角元全為零，所以的對(duì)角元全為零，所以123n 。

47、22221232nm，又因?yàn)橛忠驗(yàn)閷?duì)向量對(duì)向量(1, 1,1)與與(2,3,4,n) )應(yīng)用柯西應(yīng)用柯西- -施瓦茨不等式，施瓦茨不等式，得得22223231111nnn。將上述兩式分別代入第一個(gè)式子的左端和右端，便可得證。將上述兩式分別代入第一個(gè)式子的左端和右端，便可得證。注：注：對(duì)于圖譜的研究，開(kāi)始于對(duì)于圖譜的研究，開(kāi)始于20世紀(jì)世紀(jì)60年代。形成了代數(shù)圖年代。形成了代數(shù)圖論的主要研究方向之一。圖譜研究在流體力學(xué)，量子化學(xué)，論的主要研究方向之一。圖譜研究在流體力學(xué)，量子化學(xué)，量子物理與非線性物理以及網(wǎng)絡(luò)技術(shù)中都有重要的應(yīng)用。量子物理與非線性物理以及網(wǎng)絡(luò)技術(shù)中都有重要的應(yīng)用。四、圖的鄰接代數(shù)

48、四、圖的鄰接代數(shù)定義定義 設(shè)設(shè)A是無(wú)環(huán)圖是無(wú)環(huán)圖G的鄰接矩陣，容易驗(yàn)證的鄰接矩陣，容易驗(yàn)證01(),kkiGa Ia Aa AaC kZ對(duì)于矩陣的加法和數(shù)與矩陣的乘法來(lái)說(shuō)構(gòu)成復(fù)數(shù)域?qū)τ诰仃嚨募臃ê蛿?shù)與矩陣的乘法來(lái)說(shuō)構(gòu)成復(fù)數(shù)域C上的向上的向量空間，稱該空間為量空間，稱該空間為圖圖G的鄰接代數(shù)的鄰接代數(shù)。定理定理 設(shè)設(shè)G為為n階無(wú)環(huán)連通圖，則階無(wú)環(huán)連通圖，則 d(G)1dim(G)n。證明證明 由矩陣?yán)碚撝徑哟鷶?shù)的維數(shù)等于鄰接矩陣的最小由矩陣?yán)碚撝?，鄰接代?shù)的維數(shù)等于鄰接矩陣的最小多項(xiàng)式的次數(shù)。多項(xiàng)式的次數(shù)。111()0,nnnnfAAa AaAa I所以最小多項(xiàng)式的次數(shù)不超過(guò)所以最小多項(xiàng)式的

49、次數(shù)不超過(guò)n，因此，因此dim(G)n。下面證明下面證明I, A, A2, Ad(G) 線性無(wú)關(guān)。線性無(wú)關(guān)。若不然，則存在不全為零的數(shù)若不然，則存在不全為零的數(shù)a0, a1, ad(G)使得使得2()012()0d Gd Ga Ia Aa AaA。設(shè)設(shè)al- -10，但當(dāng)，但當(dāng)l k d(G) 時(shí)，有時(shí)，有ak =0，從而，從而2101210lla Ia Aa AaA。由哈密爾頓由哈密爾頓凱萊定理知?jiǎng)P萊定理知顯然，顯然，d(G) n。于是，于是，d(v1, vk ) = k- -1，(k=1, 2, d(G)+1)。注意到：注意到：Ak 的元素的元素a1 l(k)在在 k 0。第第1行第行第

50、l 列的元素為列的元素為al- -1a1 l ( l- -1 )0。210121lla Ia Aa AaA所以矩陣所以矩陣因此因此2101210lla Ia Aa AaA，產(chǎn)生矛盾！產(chǎn)生矛盾！假定假定v1v2vd(G)+1 是是G中一條最短的中一條最短的 (v1, vd(G)+1)路。路。定理定理 設(shè)設(shè)G 為為n階連通無(wú)環(huán)圖，則階連通無(wú)環(huán)圖，則A(G)的不同特征值的個(gè)數(shù)的不同特征值的個(gè)數(shù) s 滿足不等式滿足不等式證明證明 s n 顯然成立。顯然成立。dim()()1sGd G 。由矩陣?yán)碚撝悍秦?fù)對(duì)稱矩陣的不同特征值的個(gè)數(shù)等于其最由矩陣?yán)碚撝悍秦?fù)對(duì)稱矩陣的不同特征值的個(gè)數(shù)等于其最小多項(xiàng)式的次

51、數(shù)，而最小多項(xiàng)式的次數(shù)等于小多項(xiàng)式的次數(shù)，而最小多項(xiàng)式的次數(shù)等于G的鄰接代數(shù)的的鄰接代數(shù)的維數(shù)，所以：維數(shù)，所以：()1d Gsn 。注：注：具有具有n個(gè)點(diǎn)的路的直徑顯然為個(gè)點(diǎn)的路的直徑顯然為n- -1，因此，因此n點(diǎn)路的鄰接代點(diǎn)路的鄰接代數(shù)的維數(shù)為數(shù)的維數(shù)為n。注：注：n點(diǎn)路的不同特征值的個(gè)數(shù)為點(diǎn)路的不同特征值的個(gè)數(shù)為n。完全圖。完全圖Kn的直徑顯然為的直徑顯然為1，不同特征值的個(gè)數(shù)恰好為，不同特征值的個(gè)數(shù)恰好為2。五、圖空間五、圖空間具有具有m條邊的簡(jiǎn)單圖的生成子圖的個(gè)數(shù)顯然為條邊的簡(jiǎn)單圖的生成子圖的個(gè)數(shù)顯然為2m。設(shè)設(shè)G1, G2, GN（N=2m）表示簡(jiǎn)單圖）表示簡(jiǎn)單圖G的全部生成子圖

52、。的全部生成子圖。定理定理 集合集合M=G1, G2, GN在對(duì)稱差運(yùn)算在對(duì)稱差運(yùn)算與數(shù)乘運(yùn)算與數(shù)乘運(yùn)算0 Gi= ， 1 Gi= Gi下，構(gòu)成數(shù)域下，構(gòu)成數(shù)域F=0, 1上的一個(gè)上的一個(gè)m維向量空間。維向量空間。注：注：圖空間是網(wǎng)絡(luò)圖論中的一個(gè)基本概念。學(xué)習(xí)網(wǎng)絡(luò)圖論的圖空間是網(wǎng)絡(luò)圖論中的一個(gè)基本概念。學(xué)習(xí)網(wǎng)絡(luò)圖論的主要基礎(chǔ)是電工學(xué)與矩陣?yán)碚撝R(shí)。研究通信網(wǎng)絡(luò)，如果涉主要基礎(chǔ)是電工學(xué)與矩陣?yán)碚撝R(shí)。研究通信網(wǎng)絡(luò)，如果涉及圖論方法，建議參看及圖論方法，建議參看陳樹(shù)柏，陳樹(shù)柏，網(wǎng)絡(luò)圖論及其應(yīng)用網(wǎng)絡(luò)圖論及其應(yīng)用，科學(xué)出版社，科學(xué)出版社，1982年。年。1.6 極圖極圖 P. Erdos是該研究領(lǐng)域的

53、杰出人物，也是數(shù)學(xué)界的傳奇是該研究領(lǐng)域的杰出人物，也是數(shù)學(xué)界的傳奇人物，國(guó)際圖論大師，獲過(guò)人物，國(guó)際圖論大師，獲過(guò)Wolf數(shù)學(xué)獎(jiǎng)。他是數(shù)學(xué)獎(jiǎng)。他是20世紀(jì)最偉大世紀(jì)最偉大的數(shù)學(xué)家之一，也是人類歷史上發(fā)表數(shù)學(xué)論文最多的數(shù)學(xué)家的數(shù)學(xué)家之一，也是人類歷史上發(fā)表數(shù)學(xué)論文最多的數(shù)學(xué)家(1525篇篇)，第二名是歐拉，第二名是歐拉(850余篇余篇)，第三名是柯西，第三名是柯西(789篇篇)。他于他于1996年年9月月20日因心臟病去世，享年日因心臟病去世，享年83歲，他的逝世當(dāng)歲，他的逝世當(dāng)時(shí)驚動(dòng)了整個(gè)數(shù)學(xué)界。時(shí)驚動(dòng)了整個(gè)數(shù)學(xué)界。 極圖屬于極圖屬于極值圖論極值圖論的范疇，主要研究滿足某個(gè)條件下的范疇，主要研

54、究滿足某個(gè)條件下的最大圖或最小圖問(wèn)題。的最大圖或最小圖問(wèn)題。 20世紀(jì)世紀(jì)70年代末，極值圖論已經(jīng)形成了相對(duì)完整的理論年代末，極值圖論已經(jīng)形成了相對(duì)完整的理論體系，但還有很多引人入勝的公開(kāi)性問(wèn)題沒(méi)有解決，所以，體系，但還有很多引人入勝的公開(kāi)性問(wèn)題沒(méi)有解決，所以，直到現(xiàn)在，它仍然是重要研究方向。但是，該方向是比較困直到現(xiàn)在，它仍然是重要研究方向。但是，該方向是比較困難的數(shù)學(xué)研究方向之一。難的數(shù)學(xué)研究方向之一。一、一、l 部圖的概念與特征部圖的概念與特征定義定義 若簡(jiǎn)單圖若簡(jiǎn)單圖G的點(diǎn)集的點(diǎn)集V有一個(gè)劃分：有一個(gè)劃分：1, , liijiVVVVij 且所有的且所有的Vi 非空，非空，Vi 內(nèi)的點(diǎn)

55、均不鄰接，稱內(nèi)的點(diǎn)均不鄰接，稱G是一個(gè)是一個(gè) l 部圖部圖。4部圖部圖例例注：注：(1) 如果如果l=2，則，則G 就是偶圖就是偶圖;(2) 任何一個(gè)任何一個(gè)n階圖必是一個(gè)階圖必是一個(gè)n部圖部圖;(3) 若若l1l2n，任意的，任意的l1部圖也是部圖也是 l2部圖。部圖。定義定義 如果在一個(gè)如果在一個(gè)l 部圖部圖G中中, |Vi|=ni, 任何兩點(diǎn)任何兩點(diǎn)uVi , v Vj , ij , i, j =1, 2, l 均鄰接，則稱均鄰接，則稱G為為完全完全l 部圖部圖。記作。記作12,lnnnGK。例例注；注；完全完全l 部圖也可表示為部圖也可表示為 。llnnnnnnKKKK2121,lji

56、jinn1邊數(shù)：邊數(shù)：liin1點(diǎn)數(shù)：點(diǎn)數(shù)： v1 v2 v3 v4 v6v5K1,2,3定義定義 如果在一個(gè)如果在一個(gè)n個(gè)點(diǎn)的完全個(gè)點(diǎn)的完全l 部圖部圖G中，中，n=kl + r (0r l) |V1| = |V2| = = |Vr| = k + 1, |Vr+1| = |Vr+2 | = = |Vl | = k則稱則稱G 為為n 階階完全完全l 幾乎等部圖幾乎等部圖，記為，記為T(mén)l, n。|V1| = |V2| = = |Vl | 的完全的完全l 幾乎等部圖稱為幾乎等部圖稱為完全完全l 等部圖等部圖。v1 v2 v3v4 v5 v6考察考察1. 這是一個(gè)連通的這是一個(gè)連通的3部圖部圖, 點(diǎn)

57、集點(diǎn)集V 的劃分的劃分為為V1= v4，V2 = v3, v5，V3 =v1, v2, v6 ;2. V 的劃分也可為的劃分也可為V1= v1, v5，V2 = v2, v3，V3 = v4, v6 ; 3. 這也是一個(gè)這也是一個(gè)2部圖部圖, 點(diǎn)集的劃分為點(diǎn)集的劃分為V1= v4, v2, v6 ，V2 = v1, v3, v5 且劃分唯一且劃分唯一 。定理定理 連通偶圖的連通偶圖的2部劃分是唯一的。部劃分是唯一的。證明證明 設(shè)連通偶圖設(shè)連通偶圖G的的2部劃分為部劃分為V1V2 =V。 取取vV1，由于，由于G 連通，對(duì)任何連通，對(duì)任何uV1V2， G中有聯(lián)結(jié)中有聯(lián)結(jié)u 和和v的路，故的路，故

58、d (v, u)有定義。有定義。 因?yàn)槿魏我粭l以因?yàn)槿魏我粭l以v為起點(diǎn)的路交替地經(jīng)過(guò)為起點(diǎn)的路交替地經(jīng)過(guò)V1和和V2 的點(diǎn)，可知的點(diǎn)，可知一個(gè)點(diǎn)一個(gè)點(diǎn)uV2 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)d (v, u)是奇數(shù)。是奇數(shù)。該準(zhǔn)則唯一地決定了該準(zhǔn)則唯一地決定了G 的的2部劃分。部劃分。定理定理 n 階完全偶圖階完全偶圖Kn1, n2的邊數(shù)的邊數(shù)m=n1n2，且，且2/4mn。證明證明 m=n1n2顯然。下面證明第二結(jié)論：顯然。下面證明第二結(jié)論：1222222,222()()()()424n nn nnnnnm Km Knnnn。定理定理 n階階l 部圖部圖G 有最多邊數(shù)的充要條件是有最多邊數(shù)的充要條件是 G T

59、l, n。證明證明 首先首先12,()()lnnnm Gm K。其次，考慮其次，考慮121(,), s.t. llijiijif n nnn nnn，則則 f 取最大值的充分必要條件：對(duì)任何的取最大值的充分必要條件：對(duì)任何的1 i j l，有，有| |ni- -nj | |1。此時(shí)此時(shí)G 的對(duì)應(yīng)的頂點(diǎn)劃分形成的的對(duì)應(yīng)的頂點(diǎn)劃分形成的 l 部圖正好為部圖正好為T(mén)l, n。從而定理得證。從而定理得證。二、二、 Turn定理定理定義定義 設(shè)設(shè)G 和和H是兩個(gè)是兩個(gè)n階圖，稱階圖，稱G度弱于度弱于H，如果存在雙射，如果存在雙射：V ( G )V( H )，使得對(duì)任何點(diǎn)使得對(duì)任何點(diǎn)vV( G )，有，有( )( ( )GHdvdv。注：注：若若G度弱于度弱于