拉普拉斯矩陣

拉普拉斯矩陣（英文：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值，代表幅圖嘅代數連通度。個值愈大代表幅圖啲綟互相之間褦得愈多；反之啲拏褦愈少。