Ma trận Laplace

Trong lý thuyết đồ thị, ma trận Laplace, hay còn gọi là ma trận Kirchhoff, hoặc ma trận dẫn nạp, là một cách biểu diễn đồ thị bằng ma trận. Theo định lý Kirchhoff, nó có thể dùng để tính số cây bao trùm của đồ thị. Ma trận Laplace cũng cung cấp nhiều thông tin khác về đồ thị; có thể xem chi tiết hơn ở lý thuyết phổ đồ thị. Bất đẳng thức Cheeger trong hình học Riemann cũng có một dạng rời rạc sử dụng ma trận Laplace. Nó có thể dùng để tính xấp xỉ lát cắt thưa nhất (tiếng Anh - sparsest cut) của đồ thị thông qua giá trị đặc trưng thứ hai của ma trận Laplace.

Định nghĩa

Cho một đồ thị G = (V, E) với tập hợp đỉnh V và tập hợp cạnh E, cùng với một hàm trọng số $w:E\rightarrow \mathbb {R} ^{+}$ ($\mathbb {R} ^{+}$ dùng để chỉ tập hợp số thực dương). Ma trận kề A_G của đồ thị được định nghĩa như sau:

$A_{G}(i,j):={\begin{cases}w(i,j)&khi\ (i,j)\in E\\0&khi\ (i,j)\not \in E\end{cases}}$

Ma trận bậc D_G là một ma trận đường chéo được định nghĩa như sau:

$D_{G}(i,i):=\sum _{j}A_{G}(i,j)$

Ma trận Laplace L_G được định nghĩa bởi

$L_{G}=D_{G}-A_{G}$

Có một định nghĩa khác tương đương như sau. Định nghĩa ma trận Laplace L_e của một cạnh e=(i,j) là ma trận với L_e(i,i)=L_e(j,j)=1 và L_e(i,j)=L_e(j,i)=-1. Ma trận L_G được định nghĩa bởi

$L_{G}=\sum _{e\in E}w_{e}L_{e}$

Ví dụ

Dưới đây là một ví dụ đơn giản về một đồ thị có nhãn, vô hướng và ma trận Laplace của nó.

Dán nhãn đồ thị	Ma trận bậc	Ma trận kề	Ma trận Laplace
	${\textstyle \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)}$	${\textstyle \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)}$	${\textstyle \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)}$

Tính chất

Với bất kì đồ thị G nào cùng với ma trận Laplace tương ứng với các giá trị đặc trưng $\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}$:

• L luôn xác định không âm ($\forall i,\lambda _{i}\geq 0;\quad \lambda _{0}=0$).
• Số giá trị đặc trưng của ma trận Laplace nhận giá trị 0 là số thành phần liên thông của đồ thị.
• $\lambda _{0}$ luôn bằng 0 do mọi ma trận Laplace đều có vectơ đặc trưng $[1,1,\dots ,1]$ tương ứng với giá trị đặc trưng 0.