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 圖論及其應用圖論及其應用 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第一章第一章 圖的基本概念圖的基本概念本次課主要內容本次課主要內容鄰接譜與圖的鄰接代數鄰接譜與圖的鄰接代數(一一)、鄰接譜、鄰接譜(二二)、圖的鄰接代數、圖的鄰接代數(三三)、圖空間簡介、圖空間簡介 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、圖的特征多項式、圖的特征多項式定義定義1：圖的鄰接矩陣：圖的鄰接矩陣A(G)的特征多項式：的特征多項式：稱為圖稱為圖G的特征多項式。的特征多項式。例例1、設單圖、設單圖G的特征多項式為：的特征多項式為：12121( , )nnnnnf GE Aaaaa求證求證: (1) a1=0 ; (2) a2= m (G) ;(3) a3是是G中含有不同的中含有不同的K3子圖的個數子圖的個數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證明：由矩陣理論：對每個證明：由矩陣理論：對每個1in,(

3、-1)n,(-1)i ia ai i是是A(G)A(G)的的所有所有i i階主子式之和。階主子式之和。(1) 由于由于A(G)的主對角元全為零，所以所有的主對角元全為零，所以所有1階主子階主子式全為零，即：式全為零，即：a1=0 ;01110 這樣的一個這樣的一個2階主子式對應階主子式對應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這樣的一個這樣的一個3階主子式對應階主子式對應G中的一個中的一個K3，反之亦然，反之亦然.設設G中有中有S個個K3, 則：則：(3) 對于單圖對于單圖G, A(G)中非零的中非零的3階主子式必為如下形階主子式必為如下形式：式：33(1)2aS事實上，有如下一般性定理：事實上，有如下一般性定理：(見李蔚萱，見李蔚萱，圖論圖論，湖，湖南科學技術出版社，南科學技術出版社，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的特征多項式的系數：的特征多項式的系數：(1)det(

5、,),1, 2,iiHaHs G Hin其中，其中，s (G, H)表示表示G的同構于的同構于H的導出子圖的數目。的導出子圖的數目。右邊對所有右邊對所有i階圖階圖H求和。求和。2、圖的鄰接譜、圖的鄰接譜定義定義2：圖的鄰接矩陣：圖的鄰接矩陣A(G)的特征多項式的特征值的特征多項式的特征值及其重數，稱為及其重數，稱為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，若兩個非同構的圖具有相同的譜，則稱它們是同，若兩個非同構的圖具有相同的譜，則稱它們是同譜圖。求證：下面兩圖是同譜圖。譜圖。求證：下面兩圖是同譜圖。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顯然不同構。顯然不同構。通過直接計算：通過直接計

7、算：6432( , )( , )74741f Gf H所以所以G與與H是同譜圖。是同譜圖。例例4，設單圖，設單圖A(G)的譜為：的譜為：1212( )ssSpec Gmmm則：則：212 ( )Siiimm G證明：由矩陣理論：證明：由矩陣理論：2(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)表示點表示點vi的度數，由握手定理：的度數，由握手定理：即：即：2(2)111()2()Snniiiiiiiimad vm G212()Siiimm G例例5，設，設是是單圖單圖G = (n,

8、 m)的任意特征值，則：的任意特征值，則：2(1)m nn證明：不失一般性，設證明：不失一般性，設= =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注：對于圖譜的研究，開始于二十世紀注：對于圖譜的研究，開始于二十世紀60年代。形成年代。形成了代數圖論的主要研究方向之一。圖譜研究在流體力了代數圖論的主要研究方向之一。圖譜研究在流體力學，量子化學里有重要的應用。國內，中國科技大學學，量子化學里有重要的應用。國內，中國科技大學數學系是最早展開該課題研究的單位數學系是最早展開該課題研究的單位(1978年就有很好年就有很好的研究成果的研究成果)。他們對圖論的研究主要有兩個方面：一。他們對圖論的研究主要有兩個方面：一是圖譜問題，二是組合網絡研

10、究，也有達到國際水平是圖譜問題，二是組合網絡研究，也有達到國際水平的研究成果的研究成果(1994年開始年開始).關于組合網絡問題，將在第關于組合網絡問題，將在第三章作一些介紹。三章作一些介紹。 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(二二)、圖的鄰接代數、圖的鄰接代數1、圖的鄰接代數的定義、圖的鄰接代數的定義定義定義3：設：設A是無環圖是無環圖G的鄰接矩陣，稱：的鄰接矩陣，稱：01(),kkiGa Ea Aa AaC kZ對于矩陣的加法和數與矩陣的乘法來說作成數域對于矩陣的加法和數與矩陣的乘法來說作成數域C上的上的向量空

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

12、：E, A, A2, , A d (G)線性無關！線性無關！若不然，則存在不全為零的數若不然，則存在不全為零的數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設設a m-10 , 但當但當k m 時，有時，有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產生矛盾！產生矛盾！定理結果分析：不等式右端的界是緊的！定理結果分析：不等式右端的界是緊的！因為：因為：n點路的直徑為點路的直徑為n-1, 所以，此時該路的鄰接代數所以，此時該路的

14、鄰接代數的維數正好為的維數正好為n。此外：當此外：當G為為K n時，有：時，有：2dim()nKn例例6，設，設G 為為n階連通圖，則階連通圖，則G的不同特征值的個數的不同特征值的個數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由矩陣理論知：對稱矩陣的不同特征值的個數等于其由矩陣理論知：對稱矩陣的不同特征值的個數等于其最小多項式的次數，而最小多項式的次數等于最小多項式的次數，而最小多項式的次數等于G的鄰接的鄰接代數的維數，所以：代

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

16、信網絡，如果要用圖論方法，建議參看陳樹柏的通信網絡，如果要用圖論方法，建議參看陳樹柏的網絡圖論及其應用網絡圖論及其應用，科學出版社，科學出版社，1982年。學習年。學習網絡圖論的主要基礎是電工學與矩陣理論知識。網絡圖論的主要基礎是電工學與矩陣理論知識。 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上的向量空間，只需要驗證上的向量空間，只需要驗證“兩閉兩閉”與與“八條八條”即可。即可。(2) M(2) M的維數為的維數為m m令令又令：又令：,(1)iigG eim可以證明：可以證明：g g1 1,g,g2 2,g,gm m為為M M的一組基！的一組基！事實上：對事實上：對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