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ố  ( 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:

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

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

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

 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 Hình:6n-graf.svg   

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 :

 L luôn xác định không âm ().
 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ị.
  luôn bằng 0 do mọi ma trận Laplace đều có vectơ đặc trưng  tương ứng với giá trị đặc trưng 0.

Ghi chú

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