(完整版)鄰接矩陣及拉普拉斯矩陣

1、鄰接矩陣及拉普拉斯矩陣鄰接矩陣圖的鄰接矩陣能夠很方便的表示圖的很多信息，且具有描述簡(jiǎn)單、直觀的特點(diǎn)。無(wú)向簡(jiǎn)單圖的鄰接矩陣定義如下：設(shè)圖G=(V,E)，有n三1個(gè)頂點(diǎn)，分別為：v，v，Lv，12n則G的鄰接矩陣A是按如下定義的一個(gè)n階方陣。f1，(v,v)eEA=(a)，a=5ijnxnij0,否則直觀上，由鄰接矩陣我們可以得到如下信息：1. 鄰接矩陣是一個(gè)0，1的對(duì)稱矩陣，對(duì)角線元素為0。2. 矩陣的各個(gè)行和(列和)是各個(gè)頂點(diǎn)的度。所有元素相加和為邊數(shù)的二倍。3. An的ZJ位置元素為V與v之間的長(zhǎng)度等于n的通路的數(shù)目，而i，j位置的元素為ijv到自身的回路的數(shù)目。特別的A2的i,i位置元素是

2、v的度；A3的車(chē)位置元素是含v的iii三角形數(shù)目的二倍。4由3設(shè)S=Ak(l1)，則S中i,j位置元素s(i)為頂點(diǎn)v與v.之間長(zhǎng)度小于或lli，jijk=1等于1的通路的個(gè)數(shù)。若S(n-1)=0，則說(shuō)明V與v之間沒(méi)有通路。由此我們可以得到一個(gè)i，jij判斷圖G的聯(lián)通新的重要準(zhǔn)則：對(duì)于矩陣S=Ak，若S中所有元素都非零則G是連k=1通圖，否則圖G是非連通圖。5設(shè)G是連通圖，將矩陣A的所有是1的元素?fù)Q成1,并且把對(duì)角線元素a換成相ii應(yīng)頂點(diǎn)v.的度，(i=1，2L，n)，則所得到的矩陣的任何元素的代數(shù)余子式都相等，等于Gi的生成樹(shù)的數(shù)目。拉普拉斯矩陣Laplacianmatri的定義拉普拉斯矩陣

3、(Laplacianmatrix),也稱為基爾霍夫矩陣，是表示圖的一種矩陣。給定一個(gè)有n個(gè)頂點(diǎn)的圖G=(V,E)，其拉普拉斯矩陣被定義為：其中門(mén)為圖的度矩陣，；為圖的鄰接矩陣。舉個(gè)例子。給定一個(gè)簡(jiǎn)單的圖，如下：把此“圖”轉(zhuǎn)換為鄰接矩陣的形式，記為：；:010010101010010100)0101111010000100把:的每一列元素加起來(lái)得到上個(gè)數(shù)，然后把它們放在對(duì)角線上(其它地方都是零)，組成一個(gè)卞X(qián)N的對(duì)角矩陣，記為度矩陣D,如下圖所示：f200000、03000000200()00030000003()0000丿根據(jù)拉普拉斯矩陣的定義一：!，可得拉普拉斯矩陣二為:2-100-10-1

4、3-10-100-12-10000-13-1-1-1-10一130000一101丿拉普拉斯矩陣的性質(zhì)介紹拉普拉斯矩陣的性質(zhì)之前，首先定義兩個(gè)概念，如下： 對(duì)于鄰接矩陣，定義圖中A子圖與B子圖之間所有邊的權(quán)值之和如下：W(A,B)=YwijiwA,jwB其中，W定義為節(jié)點(diǎn)i到節(jié)點(diǎn)j的權(quán)值，如果兩個(gè)節(jié)點(diǎn)不是相連的，權(quán)值為零。 與某結(jié)點(diǎn)鄰接的所有邊的權(quán)值和定義為該頂點(diǎn)的度d,多個(gè)d形成一個(gè)度矩陣口(對(duì)角陣)d=Ywiijj=1拉普拉斯矩陣二具有如下性質(zhì)： 是對(duì)稱半正定矩陣； L-1=01,即二的最小特征值是0相應(yīng)的特征向量是1。證明：L-1=(D-W)-1=0=0-1上有n個(gè)非負(fù)實(shí)特征值。=九4=LX12n且對(duì)于任何一個(gè)屬于實(shí)向量fwRn，有以下式子成立fLf=1迓w(f-f)22ijiji,j=1其中，L=D-W,d=Ynw,W(A,B)=Yw。證明：iijijj=1iwA,jwBfLf=fDf-fWf=Yndf2-Ynffwii