圖論第一章圖的基本概念(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 1 圖論及其應(yīng)用圖論及其應(yīng)用 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ù)(三三)、圖空間簡介、圖空間簡介 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 312121( , )nnnnnf GE

2、Aaaaa(一一)、鄰接譜、鄰接譜1、圖的特征多項(xiàng)式、圖的特征多項(xiàng)式定義定義1：圖的鄰接矩陣：圖的鄰接矩陣A(G)的特征多項(xiàng)式：的特征多項(xiàng)式：稱為圖稱為圖G的特征多項(xiàng)式。的特征多項(xiàng)式。例例1、設(shè)單圖、設(shè)單圖G的特征多項(xiàng)式為：的特征多項(xiàng)式為：12121( , )nnnnnf GE Aaaaa求證求證: (1) a1=0 ; (2) a2= m (G) ;(3) a3是是G中含有不同的中含有不同的K3子圖的個(gè)數(shù)子圖的個(gè)數(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 4證明：由矩陣?yán)碚摚簩γ總€(gè)證明：由矩陣?yán)碚摚簩γ總€(gè)1in,(

3、-1)n,(-1)i ia ai i是是A(G)A(G)的的所有所有i i階主子式之和。階主子式之和。(1) 由于由于A(G)的主對角元全為零，所以所有的主對角元全為零，所以所有1階主子階主子式全為零，即：式全為零，即：a1=0 ;01110 這樣的一個(gè)這樣的一個(gè)2階主子式對應(yīng)階主子式對應(yīng)G中的一條邊，反之亦然，中的一條邊，反之亦然，所以，有：所以，有：(2) 對于單圖對于單圖G, A(G)中非零的中非零的2階主子式必為如下形階主子式必為如下形式：式：22(1)()am G 2()am 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

4、n 50111012110這樣的一個(gè)這樣的一個(gè)3階主子式對應(yīng)階主子式對應(yīng)G中的一個(gè)中的一個(gè)K3，反之亦然，反之亦然.設(shè)設(shè)G中有中有S個(gè)個(gè)K3, 則：則：(3) 對于單圖對于單圖G, A(G)中非零的中非零的3階主子式必為如下形階主子式必為如下形式：式：33(1)2aS事實(shí)上，有如下一般性定理：事實(shí)上，有如下一般性定理：(見李蔚萱，見李蔚萱，圖論圖論，湖，湖南科學(xué)技術(shù)出版社，南科學(xué)技術(shù)出版社，1980年年4月月) 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：圖：圖G的特征多項(xiàng)式的系數(shù)：的特征多項(xiàng)式的系數(shù)：(1)det(

5、,),1, 2,iiHaHs G Hin其中，其中，s (G, H)表示表示G的同構(gòu)于的同構(gòu)于H的導(dǎo)出子圖的數(shù)目。的導(dǎo)出子圖的數(shù)目。右邊對所有右邊對所有i階圖階圖H求和。求和。2、圖的鄰接譜、圖的鄰接譜定義定義2：圖的鄰接矩陣：圖的鄰接矩陣A(G)的特征多項(xiàng)式的特征值的特征多項(xiàng)式的特征值及其重?cái)?shù)，稱為及其重?cái)?shù)，稱為G的鄰接譜。的鄰接譜。例例2、求出、求出K n的譜。的譜。解：解：K 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 70111110111()111110nA K于是：于是：11111111

6、()11111nEA K11111111111111nnn 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 8111111111111111n 1 (1)nn 所以：所以：11()11nnSpec Kn例例3，若兩個(gè)非同構(gòu)的圖具有相同的譜，則稱它們是同，若兩個(gè)非同構(gòu)的圖具有相同的譜，則稱它們是同譜圖。求證：下面兩圖是同譜圖。譜圖。求證：下面兩圖是同譜圖。GH 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 9證明：證明：G與與H顯然不同構(gòu)。顯然不同構(gòu)。通過直接計(jì)算：通過直接計(jì)

7、算：6432( , )( , )74741f Gf H所以所以G與與H是同譜圖。是同譜圖。例例4，設(shè)單圖，設(shè)單圖A(G)的譜為：的譜為：1212( )ssSpec Gmmm則：則：212 ( )Siiimm G證明：由矩陣?yán)碚摚鹤C明：由矩陣?yán)碚摚?(2)11Sniiiiiima 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 10a ii (2)表示點(diǎn)表示點(diǎn)vi的度數(shù)，由握手定理：的度數(shù)，由握手定理：即：即：2(2)111()2()Snniiiiiiiimad vm G212()Siiimm G例例5，設(shè)，設(shè)是是單圖單圖G = (n,

8、 m)的任意特征值，則：的任意特征值，則：2(1)m nn證明：不失一般性，設(shè)證明：不失一般性，設(shè)= =1 1，2 2，,n n是是G G的全體的全體特征值。特征值。G是是單圖，有：單圖，有：123(1)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 11又由例又由例4，有：，有：對向量對向量(1,1,1)與與(2 2, ,3 3, ,4 4,n n) )用柯西不等式用柯西不等式得：得：22223231111nnn22221232(2)nm所以，有：所以，有：222223231nnn由由(1)與與(2)得：得：2(1)m nn 0

9、.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注：對于圖譜的研究，開始于二十世紀(jì)注：對于圖譜的研究，開始于二十世紀(jì)60年代。形成年代。形成了代數(shù)圖論的主要研究方向之一。圖譜研究在流體力了代數(shù)圖論的主要研究方向之一。圖譜研究在流體力學(xué)，量子化學(xué)里有重要的應(yīng)用。國內(nèi)，中國科技大學(xué)學(xué)，量子化學(xué)里有重要的應(yīng)用。國內(nèi)，中國科技大學(xué)數(shù)學(xué)系是最早展開該課題研究的單位數(shù)學(xué)系是最早展開該課題研究的單位(1978年就有很好年就有很好的研究成果的研究成果)。他們對圖論的研究主要有兩個(gè)方面：一。他們對圖論的研究主要有兩個(gè)方面：一是圖譜問題，二是組合網(wǎng)絡(luò)研

10、究，也有達(dá)到國際水平是圖譜問題，二是組合網(wǎng)絡(luò)研究，也有達(dá)到國際水平的研究成果的研究成果(1994年開始年開始).關(guān)于組合網(wǎng)絡(luò)問題，將在第關(guān)于組合網(wǎng)絡(luò)問題，將在第三章作一些介紹。三章作一些介紹。 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(二二)、圖的鄰接代數(shù)、圖的鄰接代數(shù)1、圖的鄰接代數(shù)的定義、圖的鄰接代數(shù)的定義定義定義3：設(shè)：設(shè)A是無環(huán)圖是無環(huán)圖G的鄰接矩陣，稱：的鄰接矩陣，稱：01(),kkiGa Ea Aa AaC kZ對于矩陣的加法和數(shù)與矩陣的乘法來說作成數(shù)域?qū)τ诰仃嚨募臃ê蛿?shù)與矩陣的乘法來說作成數(shù)域C上的上的向量空

11、間，稱該空間為圖向量空間，稱該空間為圖G的鄰接代數(shù)。的鄰接代數(shù)。注：注： 向量空間的定義可簡單地記為向量空間的定義可簡單地記為“非空非空”、“兩閉兩閉”、“八條八條” 2、圖的鄰接代數(shù)的維數(shù)特征、圖的鄰接代數(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 14定理定理1：G為為n階連通圖，則：階連通圖，則：()1dim()d GGn證明：由哈密爾頓證明：由哈密爾頓凱萊定理凱萊定理(見北大數(shù)學(xué)力學(xué)系見北大數(shù)學(xué)力學(xué)系高高等代數(shù)等代數(shù))：2012()0nnf Aa Ea Aa Aa A所以：所以：dim()Gn下面證明：下面證明

12、：E, A, A2, , A d (G)線性無關(guān)！線性無關(guān)！若不然，則存在不全為零的數(shù)若不然，則存在不全為零的數(shù)a0 ,a1 , , a d (G) ,使：使：2()012()0d Gd Ga Ea Aa AaA 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è)a m-10 , 但當(dāng)?shù)?dāng)k m 時(shí)，有時(shí)，有a k =0. 于是有：于是有：假定：假定：v1 v2 v d(G)+1 是是G中一條最短的中一條最短的 (v1, v d(G)+1)路，路，易知：易知：d (G) n.21012110,(0)mmma Ea Aa AaAa

13、于是，于是，d(v1, v m ) = m-1 , (m=1, 2, , d (G)+1)注意到：注意到：A k的元素的元素a1m (k)在在 k 0所以，所以， 的一行的一行m列元為列元為am-1a1m (m-1)0，這樣有：210121mma Ea Aa AaA 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 162101210mma Ea Aa AaA產(chǎn)生矛盾！產(chǎn)生矛盾！定理結(jié)果分析：不等式右端的界是緊的！定理結(jié)果分析：不等式右端的界是緊的！因?yàn)椋阂驗(yàn)椋簄點(diǎn)路的直徑為點(diǎn)路的直徑為n-1, 所以，此時(shí)該路的鄰接代數(shù)所以，此時(shí)該路的

14、鄰接代數(shù)的維數(shù)正好為的維數(shù)正好為n。此外：當(dāng)此外：當(dāng)G為為K n時(shí)，有：時(shí)，有：2dim()nKn例例6，設(shè)，設(shè)G 為為n階連通圖，則階連通圖，則G的不同特征值的個(gè)數(shù)的不同特征值的個(gè)數(shù)S滿滿足：足：()1d GSn 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證明：證明：S nn是顯然的！是顯然的！dim()()1SGd G由矩陣?yán)碚撝簩ΨQ矩陣的不同特征值的個(gè)數(shù)等于其由矩陣?yán)碚撝簩ΨQ矩陣的不同特征值的個(gè)數(shù)等于其最小多項(xiàng)式的次數(shù)，而最小多項(xiàng)式的次數(shù)等于最小多項(xiàng)式的次數(shù)，而最小多項(xiàng)式的次數(shù)等于G的鄰接的鄰接代數(shù)的維數(shù)，所以：代

15、數(shù)的維數(shù)，所以：注注 : (1) n點(diǎn)路的不同特征值有點(diǎn)路的不同特征值有n個(gè)；個(gè)；(2) K n的不同特征值有的不同特征值有2個(gè)。個(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 18定理定理2：集合：集合：對于圖的對稱差運(yùn)算和數(shù)乘運(yùn)算：對于圖的對稱差運(yùn)算和數(shù)乘運(yùn)算：(三三)、圖空間簡介、圖空間簡介12,2mNiMG GGGGN為單圖的子圖，0,1iiiGGG 來說作成數(shù)域來說作成數(shù)域 F = 0, 1 上的上的m維向量空間。維向量空間。注：圖空間概念是網(wǎng)絡(luò)圖論中的一個(gè)基本概念。研究注：圖空間概念是網(wǎng)絡(luò)圖論中的一個(gè)基本概念。研究通

16、信網(wǎng)絡(luò)，如果要用圖論方法，建議參看陳樹柏的通信網(wǎng)絡(luò)，如果要用圖論方法，建議參看陳樹柏的網(wǎng)絡(luò)圖論及其應(yīng)用網(wǎng)絡(luò)圖論及其應(yīng)用，科學(xué)出版社，科學(xué)出版社，1982年。學(xué)習(xí)年。學(xué)習(xí)網(wǎng)絡(luò)圖論的主要基礎(chǔ)是電工學(xué)與矩陣?yán)碚撝R。網(wǎng)絡(luò)圖論的主要基礎(chǔ)是電工學(xué)與矩陣?yán)碚撝R。 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 1912(),mE Ge ee證明證明: (1) 證明證明M是是F上的向量空間，只需要驗(yàn)證上的向量空間，只需要驗(yàn)證“兩閉兩閉”與與“八條八條”即可。即可。(2) M(2) M的維數(shù)為的維數(shù)為m m令令又令：又令：,(1)iigG eim可以證明：可以證明：g g1 1,g,g2 2,g,gm m為為M M的一組基！的一組基！事實(shí)上：對事實(shí)上：對iGM若若E(GE(Gi i)=e)=ei1i1,e,ei2i2,e,eikik,則：則：12iiiikGggg 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另一方面：若另一方面：若則：則：c c1 1=c=c2 2= = c= = cm m =0=01