圖論課件鄰接譜與圖的鄰接代數(shù)

圖論課件鄰接譜與圖的鄰接代數(shù)1第一頁，共二十二頁，編輯于2023年，星期二第一章圖的基本概念本次課主要內(nèi)容鄰接譜與圖的鄰接代數(shù)(一)、鄰接譜(二)、圖的鄰接代數(shù)(三)、圖空間簡介2第二頁，共二十二頁，編輯于2023年，星期二(一)、鄰接譜1、圖的特征多項式定義1：圖的鄰接矩陣A(G)的特征多項式：稱為圖G的特征多項式。例1、設(shè)單圖G的特征多項式為：求證:(1)a1=0;(2)–a2=m(G);(3)–a3是G中含有不同的K3子圖的個數(shù)2倍。3第三頁，共二十二頁，編輯于2023年，星期二證明：由矩陣?yán)碚摚簩γ總€1≦i≦n,(-1)iai是A(G)的所有i階主子式之和。(1)由于A(G)的主對角元全為零，所以所有1階主子式全為零，即：a1=0;這樣的一個2階主子式對應(yīng)G中的一條邊，反之亦然，所以，有：(2)對于單圖G,

A(G)中非零的2階主子式必為如下形式：4第四頁，共二十二頁，編輯于2023年，星期二這樣的一個3階主子式對應(yīng)G中的一個K3，反之亦然.設(shè)G中有S個K3,則：(3)對于單圖G,

A(G)中非零的3階主子式必為如下形式：事實(shí)上，有如下一般性定理：(見李蔚萱，《圖論》，湖南科學(xué)技術(shù)出版社，1980年4月)5第五頁，共二十二頁，編輯于2023年，星期二定理1：圖G的特征多項式的系數(shù)：其中，s(G,H)表示G的同構(gòu)于H的導(dǎo)出子圖的數(shù)目。右邊對所有i階圖H求和。2、圖的鄰接譜定義2：圖的鄰接矩陣A(G)的特征多項式的特征值及其重數(shù)，稱為G的鄰接譜。例2、求出Kn的譜。解：Kn的鄰接矩陣為：6第六頁，共二十二頁，編輯于2023年，星期二于是：7第七頁，共二十二頁，編輯于2023年，星期二所以：例3，若兩個非同構(gòu)的圖具有相同的譜，則稱它們是同譜圖。求證：下面兩圖是同譜圖。GH8第八頁，共二十二頁，編輯于2023年，星期二證明：G與H顯然不同構(gòu)。通過直接計算：所以G與H是同譜圖。例4，設(shè)單圖A(G)的譜為：則：證明：由矩陣?yán)碚摚?第九頁，共二十二頁，編輯于2023年，星期二aii(2)表示點(diǎn)vi的度數(shù)，由握手定理：即：例5，設(shè)λ是單圖G=(n,m)的任意特征值，則：證明：不失一般性，設(shè)λ=λ1，λ2，…,λn是G的全體特征值。G是單圖，有：10第十頁，共二十二頁，編輯于2023年，星期二又由例4，有：對向量(1,1,…,1)與(λ2,λ3,λ4,…,λn)用柯西不等式得：所以，有：由(1)與(2)得：11第十一頁，共二十二頁，編輯于2023年，星期二注：對于圖譜的研究，開始于二十世紀(jì)60年代。形成了代數(shù)圖論的主要研究方向之一。圖譜研究在流體力學(xué)，量子化學(xué)里有重要的應(yīng)用。國內(nèi)，中國科技大學(xué)數(shù)學(xué)系是最早展開該課題研究的單位(1978年就有很好的研究成果)。他們對圖論的研究主要有兩個方面：一是圖譜問題，二是組合網(wǎng)絡(luò)研究，也有達(dá)到國際水平的研究成果(1994年開始).關(guān)于組合網(wǎng)絡(luò)問題，將在第三章作一些介紹。12第十二頁，共二十二頁，編輯于2023年，星期二(二)、圖的鄰接代數(shù)1、圖的鄰接代數(shù)的定義定義3：設(shè)A是無環(huán)圖G的鄰接矩陣，稱：對于矩陣的加法和數(shù)與矩陣的乘法來說作成數(shù)域C上的向量空間，稱該空間為圖G的鄰接代數(shù)。注：向量空間的定義可簡單地記為“非空”、“兩閉”、“八條”2、圖的鄰接代數(shù)的維數(shù)特征13第十三頁，共二十二頁，編輯于2023年，星期二定理1：G為n階連通圖，則：證明：由哈密爾頓—凱萊定理(見北大數(shù)學(xué)力學(xué)系《高等代數(shù)》)：所以：下面證明：E,A,A2,…,Ad(G)線性無關(guān)！若不然，則存在不全為零的數(shù)a0,a1,…,ad(G),使：14第十四頁，共二十二頁，編輯于2023年，星期二設(shè)am-1≠0,但當(dāng)k≥m時，有ak=0.于是有：假定：v1v2…vd(G)+1是G中一條最短的(v1,vd(G)+1)路，易知：d(G)<n.于是，d(v1,vm)=m-1,(m=1,2,…,d(G)+1)注意到：Ak的元素a1m(k)在k<m-1時為零，而a1m(m-1)>0所以，的一行m列元為am-1a1m(m-1)≠0，這樣有：15第十五頁，共二十二頁，編輯于2023年，星期二產(chǎn)生矛盾！定理結(jié)果分析：不等式右端的界是緊的！因?yàn)椋簄點(diǎn)路的直徑為n-1,所以，此時該路的鄰接代數(shù)的維數(shù)正好為n。此外：當(dāng)G為Kn時，有：例6，設(shè)G為n階連通圖，則G的不同特征值的個數(shù)S滿足：16第十六頁，共二十二頁，編輯于2023年，星期二證明：S≦n是顯然的！由矩陣?yán)碚撝簩ΨQ矩陣的不同特征值的個數(shù)等于其最小多項式的次數(shù)，而最小多項式的次數(shù)等于G的鄰接代數(shù)的維數(shù)，所以：注

:(1)n點(diǎn)路的不同特征值有n個；(2)Kn的不同特征值有2個。17第十七頁，共二十二頁，編輯于2023年，星期二定理2：集合：對于圖的對稱差運(yùn)算和數(shù)乘運(yùn)算：(三)、圖空間簡介來說作成數(shù)域F={0,1}上的m維向量空間。注：圖空間概念是網(wǎng)絡(luò)圖論中的一個基本概念。研究通信網(wǎng)絡(luò)，如果要用圖論方法，建議參看陳樹柏的《網(wǎng)絡(luò)圖論及其應(yīng)用》，科學(xué)出版社，1982年。學(xué)習(xí)網(wǎng)絡(luò)圖論的主要基礎(chǔ)是電工學(xué)與矩陣?yán)碚撝R。18第十八頁，共二十二頁，編輯于2023年，星期二證明:(1)證明M是F上的向量空間，只需要驗(yàn)證“兩閉”與“八條”即可。(2)M的維數(shù)為m令又令：可以證明：g1,g2,…,gm為M的一組基！事實(shí)上：對若E(Gi)={ei1,ei2,…,eik},則：19第十九頁，共二十二頁，編輯于2023年，星期二另一方面：若則：c1=c2=…=cm=0所以：20第二十頁，共二十二頁，編輯于2023年，星期二