拉普拉斯矩陣

拉普拉斯矩陣（英文：Laplacian matrix），簡稱拉氏矩陣，係圖論裏便嘅一種矩陣、描述圖啲綟戥啲檠之間拏褦嘅，由次數矩陣（對角陣）減去鄰接矩陣（對角線始終係零）得到。拉氏矩陣仲着攞嚟計生成樹嘅數量同埋估計正則圖嘅擴展性。拉氏矩陣係拉普拉斯算符嘅離散版本。

拉普拉斯矩陣同埋矩陣啲細特徵值嘅特徵向量有用喺譜聚類（聚類分析嘅一種方法）入便。

定義

一幅圖個拉氏矩陣$L$、幅有綟集$V$同埋檠集$E$嘅，係一個$|V|\times |V|$矩陣。拉氏矩陣定義係$L:=D-A$ ，其中$D$係圖嘅次數矩陣，$A$係圖嘅鄰接矩陣。綟$v_{i}$同$v_{j}$個拉氏矩陣相應就有：

$L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{falls}}\ i=j\\-1&{\mbox{falls}}\ i\neq j\ {\mbox{und}}\ v_{i}{\mbox{ adjazent zu }}v_{j}\\0&{\mbox{sonst}}\end{cases}}$

其中，圖啲檠可以加有權重，係噉鄰接矩陣嘅元素就嘸一定係1，即係$W_{ij}$；相對應拉氏矩陣嘅啲值就係$-W_{ij}$。

特別嚟講，拉普拉斯矩陣係一幅有單位矩陣$I$嘅$d$ -正則圖：

$L=d\cdot I-A$

例

啲綟編號	次數矩陣	鄰接矩陣	拉普拉斯矩陣
	$\left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)$	$\left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)$	$\left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)$

戥關聯矩陣嘅拏褦

拉氏矩陣亦都可以由關聯矩陣計得出。令$B$係一隻$|E|\times |V|$關聯矩陣，係噉拉氏矩陣有下式畀得出：

$L=B^{\top }B$

特徵值同埋特徵向量

拉氏矩陣啲特徵值$\lambda$同埋特徵向量$f$可以簡單噉攞下低條式表示：

$f^{\mathrm {T} }Lf=\lambda$

一般攞$\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}$表示拉氏矩陣啲特徵值（有時下標從1開始計）。特別嘅，第二細嘅個特徵值$\lambda _{1}$叫做Fiedler值，代表幅圖嘅代數連通度。個值愈大代表幅圖啲綟互相之間褦得愈多；反之啲拏褦愈少。

特性

• $L$係對稱嘅。
• $L$係正半定嘅，特別係對所有啲 $i$都有$\lambda _{i}\geq 0$。
• $L$係一個M矩陣。
• 列累加、行累加係出零。特別係$\lambda _{0}=0$有特徵向量$\mathbf {v} _{0}=(1,1,\dots ,1)$。
• 特徵值$0$嘅重複次數係圖啲連通元件嘅數量；對於一幅連通嘅圖（成幅圖即係一隻連通元件），有且唯有$\lambda _{0}=0$。

睇埋

• 拉普拉斯算符