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

圖論及其應(yīng)用1第一章圖的基本概念本次課主要內(nèi)容鄰接譜與圖的鄰接代數(shù)(一)、鄰接譜(二)、圖的鄰接代數(shù)(三)、圖空間簡介2(一)、鄰接譜1、圖的特征多項式定義1：圖的鄰接矩陣A(G)的特征多項式：稱為圖G的特征多項式。例1、設(shè)單圖G的特征多項式為：求證:(1)a1=0;(2)–a2=m(G);(3)–a3是G中含有不同的K3子圖的個數(shù)2倍。3這樣的一個3階主子式對應(yīng)G中的一個K3，反之亦然.設(shè)G中有S個K3,則：(3)對于單圖G,

A(G)中非零的3階主子式必為如下形式：事實上，有如下一般性定理：(見李蔚萱，《圖論》，湖南科學(xué)技術(shù)出版社，1980年4月)5定理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于是：7證明：G與H顯然不同構(gòu)。通過直接計算：所以G與H是同譜圖。例4，設(shè)單圖A(G)的譜為：則：證明：由矩陣?yán)碚摚?aii(2)表示點vi的度數(shù)，由握手定理：即：例5，設(shè)λ是單圖G=(n,m)的任意特征值，則：證明：不失一般性，設(shè)λ=λ1，λ2，…,λn是G的全體特征值。G是單圖，有：10又由例4，有：對向量(1,1,…,1)與(λ2,λ3,λ4,…,λn)用柯西不等式得：所以，有：由(1)與(2)得：11(二)、圖的鄰接代數(shù)1、圖的鄰接代數(shù)的定義定義3：設(shè)A是無環(huán)圖G的鄰接矩陣，稱：對于矩陣的加法和數(shù)與矩陣的乘法來說作成數(shù)域C上的向量空間，稱該空間為圖G的鄰接代數(shù)。注：向量空間的定義可簡單地記為“非空”、“兩閉”、“八條”2、圖的鄰接代數(shù)的維數(shù)特征13定理1：G為n階連通圖，則：證明：由哈密爾頓—凱萊定理(見北大數(shù)學(xué)力學(xué)系《高等代數(shù)》)：所以：下面證明：E,A,A2,…,Ad(G)線性無關(guān)！若不然，則存在不全為零的數(shù)a0,a1,…,ad(G),使：14設(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證明：S≦n是顯然的！由矩陣?yán)碚撝簩ΨQ矩陣的不同特征值的個數(shù)等于其最小多項式的次數(shù)，而最小多項式的次數(shù)等于G的鄰接代數(shù)的維數(shù)，所以：注

:(1)n點路的不同特征值有n個；(2)Kn的不同特征值有2個。17定理2：集合：對于圖的對稱差運算和數(shù)乘運算：(三)、圖空間簡介來說作成數(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證明:(1)證明M是F上的向量空間，只需要驗證“兩閉”與“八條”即可。(2)M的維數(shù)為m令又令：可以證明：g1,g2,…,gm為M的一組基！事實上：對若E(Gi)={ei1,ei2,…,eik},則：19作業(yè)設(shè)