鄰接矩陣及拉普拉斯矩陣

鄰接矩陣及拉普拉斯矩陣鄰接矩陣圖的鄰接矩陣能夠很方便的表示圖的很多信息，且具有描述簡單、直觀的特點(diǎn)。無向簡單圖的鄰接矩陣定義如下：設(shè)圖G = (V，E ) ，有n 1 個(gè)頂點(diǎn),分別為：則G 的鄰接矩陣 A是按如下定義的一個(gè)n階方陣。直觀上，由鄰接矩陣我們可以得到如下信息： 1.鄰接矩陣是一個(gè)0，1的對稱矩陣，對角線元素為0。 2.矩陣的各個(gè)行和（列和）是各個(gè)頂點(diǎn)的度。所有元素相加和為邊數(shù)的二倍。 3. An 的i, j 位置元素為之間的長度等于n的通路的數(shù)目，而i，j位置的元素為到自身的回路的數(shù)目。特別的的i,i位置元素是的度；的i,i位置元素是含的三角形數(shù)目的二倍。4.由3.設(shè)，則中位置元素為頂點(diǎn)與之間長度小于或等于l的通路的個(gè)數(shù)。若，則說明與之間沒有通路。由此我們可以得到一個(gè)判斷圖G的聯(lián)通新的重要準(zhǔn)則：對于矩陣，若S中所有元素都非零則G是連通圖，否則圖G是非連通圖。5.設(shè)G 是連通圖，將矩陣 A的所有是1的元素?fù)Q成1，并且把對角線元素?fù)Q成相應(yīng)頂點(diǎn)的度，則所得到的矩陣的任何元素的代數(shù)余子式都相等，等于G 的生成樹的數(shù)目。拉普拉斯矩陣Laplacian matrix的定義拉普拉斯矩陣（Laplacian matrix)），也稱為基爾霍夫矩陣,是表示圖的一種矩陣。給定一個(gè)有n個(gè)頂點(diǎn)的圖，其拉普拉斯矩陣被定義為: 其中為圖的度矩陣，為圖的鄰接矩陣。舉個(gè)例子。給定一個(gè)簡單的圖，如下： 把此“圖”轉(zhuǎn)換為鄰接矩陣的形式，記為： 把的每一列元素加起來得到個(gè)數(shù)，然后把它們放在對角線上（其它地方都是零），組成一個(gè)的對角矩陣，記為度矩陣，如下圖所示： 根據(jù)拉普拉斯矩陣的定義，可得拉普拉斯矩陣為：拉普拉斯矩陣的性質(zhì) 介紹拉普拉斯矩陣的性質(zhì)之前，首先定義兩個(gè)概念，如下：對于鄰接矩陣，定義圖中A子圖與B子圖之間所有邊的權(quán)值之和如下： 其中，定義為節(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è)度矩陣（對角陣） 拉普拉斯矩陣具有如下性質(zhì)： 是對稱半正定矩陣； ，即的最小特征值是0，相應(yīng)的特征向量是