Xem mã nguồn của 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ị (lý thuyết đồ thị)|đồ 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ố <math>w:E\rightarrow \mathbb{R}^+</math> (<math>\mathbb{R}^+</math> dùng để chỉ tập hợp số thực dương). [[Ma trận kề]] ''A<sub>G</sub>'' của đồ thị được định nghĩa như sau:
:<math>A_G(i,j):=
\begin{cases}
w(i,j) & khi\ (i,j)\in E\\
0 & khi\ (i,j)\not\in E
\end{cases}
</math>
[[Ma trận bậc]] ''D<sub>G</sub>'' là một ma trận đường chéo được định nghĩa như sau:
:<math>D_G(i,i):=\sum_j A_G(i,j)</math>
Ma trận Laplace ''L<sub>G</sub>'' được định nghĩa bởi<ref name="mathworld">{{MathWorld |urlname=LaplacianMatrix |title=Laplacian Matrix}}</ref><ref>{{chú thích web|url=http://www.cs.yale.edu/homes/spielman/561/lect02-09.pdf|title=Bài giảng thứ 2 lớp của Dan Spielman|ngày truy cập=2011-09-11|archive-date = ngày 24 tháng 1 năm 2012 |archive-url=https://web.archive.org/web/20120124191749/http://www.cs.yale.edu/homes/spielman/561/lect02-09.pdf}}</ref>
:<math>L_G = D_G - A_G</math>

Có một định nghĩa khác tương đương như sau. Định nghĩa ma trận Laplace ''L<sub>e</sub>'' của một cạnh ''e=(i,j)'' là ma trận với ''L<sub>e</sub>(i,i)''=''L<sub>e</sub>(j,j)''=1 và ''L<sub>e</sub>(i,j)''=''L<sub>e</sub>(j,i)''=-1. Ma trận ''L<sub>G</sub>'' được định nghĩa bởi
:<math>L_G = \sum_{e\in E}w_e L_e</math>

== 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ó.

{|class="wikitable"
! [[Dán nhãn đồ thị]]
! [[Ma trận bậc]]
! [[Ma trận kề]]
! Ma trận Laplace
|-
| [[Hình:6n-graf.svg]]
| <math display="inline">\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)</math>
| <math display="inline">\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)</math>
| <math display="inline">\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)</math>
|}

==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]] <math>\lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}</math>:

* ''L'' luôn [[ma trận xác định không âm|xác định không âm]] (<math>\forall i, \lambda_i \ge 0;\quad \lambda_0 = 0</math>).
* 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ị.
* <math>\lambda_0</math> luôn bằng 0 do mọi ma trận Laplace đều có vectơ đặc trưng <math>[1,1,\dots,1]</math> tương ứng với giá trị đặc trưng 0.

==Ghi chú==
{{Tham khảo}}

[[Thể loại:Ma trận]]
[[Thể loại:Lý thuyết đồ thị đại số]]