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

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

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

3、(Laplacianmatrix),也稱為基爾霍夫矩陣，是表示圖的一種矩陣。給定一個有n個頂點的圖G=(V,E)，其拉普拉斯矩陣被定義為：其中門為圖的度矩陣，；為圖的鄰接矩陣。舉個例子。給定一個簡單的圖，如下：把此“圖”轉(zhuǎn)換為鄰接矩陣的形式，記為：；:010010101010010100)0101111010000100把:的每一列元素加起來得到上個數(shù)，然后把它們放在對角線上(其它地方都是零)，組成一個卞XN的對角矩陣，記為度矩陣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ì)之前，首先定義兩個概念，如下： 對于鄰接矩陣，定義圖中A子圖與B子圖之間所有邊的權(quán)值之和如下：W(A,B)=YwijiwA,jwB其中，W定義為節(jié)點i到節(jié)點j的權(quán)值，如果兩個節(jié)點不是相連的，權(quán)值為零。 與某結(jié)點鄰接的所有邊的權(quán)值和定義為該頂點的度d,多個d形成一個度矩陣口(對角陣)d=Ywiijj=1拉普拉斯矩陣二具有如下性質(zhì)： 是對稱半正定矩陣； L-1=01,即二的最小特征值是0相應(yīng)的特征向量是1。證明：L-1=(D-W)-1=0=0-1上有n個非負(fù)實特征值。=九4=LX12n且對于任何一個屬于實向量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