Ma trận Laplace

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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[sửa | sửa mã nguồn]

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ề AG 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 DG 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 LG được định nghĩa bởi[1][2]

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 Le của một cạnh e=(i,j) là ma trận với Le(i,i)=Le(j,j)=1 và Le(i,j)=Le(j,i)=-1. Ma trận LG được định nghĩa bởi

L_G = \sum_{e\in E}w_e L_e

Ví dụ[sửa | sửa mã nguồn]

Sau đây là một ví dụ với một đồ thị và ma trận Laplace tương ứng.

đồ thị Ma trận Laplace
6n-graf.svg \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[sửa | sửa mã nguồn]

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 \le \lambda_1 \le \cdots \le \lambda_{n-1}:

  • L luôn xác định không âm (\forall i, \lambda_i \ge 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.

Ghi chú[sửa | sửa mã nguồn]