Định lý Kirchhoff

Trong lý thuyết đồ thị, định lý Kirchhoff, hay định lý Kirchhoff cho ma trận và cây, đặt tên theo Gustav Kirchhoff, là một định lý về số cây bao trùm của một đồ thị. Nó là một tổng quát hóa của công thức Cayley cho số cây bao trùm của đồ thị đầy đủ.

Định lý Kirchhoff sử dụng khái niệm ma trận Laplace của đồ thị. Ma trận Laplace là hiệu của ma trận bậc (ma trận đường chéo chứa bậc của các đỉnh) và ma trận kề (ma trận (0, 1) với các số 1 tương ứng với các cạnh của đồ thị).

Cho một đồ thị liên thông G với n đỉnh, và λ₁, λ₂,...,λ_n-1 là các giá trị đặc trưng khác 0 của ma trận Laplace của G. Số cây bao trùm của G đúng bằng

t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}

Một cách tương đương, số cây bao trùm đúng bằng giá trị tuyệt đối của một phần bù đại số bất kì của ma trận Laplace của G.

Một ví dụ sử dụng định lý ma trận-cây

Ta xây dựng ma trận Laplace L của đồ thị cánh diều G trong hình vẽ bên phải.

L=\left[{\begin{array}{rrrr}3&-1&-1&-1\\-1&2&-1&0\\-1&-1&3&-1\\-1&0&-1&2\end{array}}\right].

Bây giờ ta xây dựng ma trận L* bằng cách xóa đi hàng s và cột t từ L để tính phần bù đại số (s và t không nhất thiết phải khác nhau). Trong ví dụ này, ta xóa cột 1 và hàng 1.

L^{\ast }=\left[{\begin{array}{rrr}2&-1&0\\-1&3&-1\\0&-1&2\end{array}}\right].

Cuối cùng ta tính định thức của L* để tính t(G). Trong ví dụ này t(G)=8.

Tóm tắt chứng minh

Trước hết, nhận thấy rằng ma trận Laplace có tính chất mọi hàng và mọi cột đều có tổng bằng 0. Do đó có thể chuyển một ma trận con thành một ma trận con bất kì khác bằng cách tính tổng các hàng và cột, đổi chỗ chúng, và nhân một hàng hay một cột với −1. Do đó các phần phụ đại số có giá trị tuyệt đối bằng nhau, và có thể kiểm chứng rằng chúng có cùng dấu.

Ta sẽ chứng minh định thức của ma trận con M₁₁ (ma trận Laplace L xóa đi hàng 1 và cột 1) đúng bằng số cây bao trùm. Giả sử n là số đỉnh và m là số cạnh của đồ thị. Ma trận liên thuộc E là một ma trận (0, 1) có n hàng và m cột. Nếu (i, j) là cạnh thứ k của đồ thị và i < j thì E_ik = 1, và E_jk = −1, và tất cả các vị trí khác trên cột k nhận giá trị 0. Trong ví dụ trên với n=4 và m=5,

E={\begin{bmatrix}1&1&1&0&0\\-1&0&0&1&0\\0&-1&0&-1&1\\0&0&-1&0&-1\\\end{bmatrix}}.

Nhận thấy rằng ma trận Laplace L có thể được phân tích thành tích của ma trận liên thuộc và chuyển vị của nó, nghĩa là L = EE^T. Ngoài ra, đặt F là ma trận E xóa đi hàng 1, thì FF^T =M₁₁. Theo công thức Cauchy-Binet,

\det(M_{11})=\sum _{S}\det(F_{S})\det(F_{S}^{T})=\sum _{S}\det(F_{S})^{2}

trong đó S nhận giá trị là mọi tập con của [m] \ {1} kích thước n− 1 và F_S ký hiệu ma trận vuông kích thước n − 1 chứa các cột của F có số thứ tự nằm trong S. Mỗi S xác định một tập n − 1 cạnh của đồ thị ban đầu, và có thể chứng minh rằng các cạnh này tạo thành một cây bao trùm khi và chỉ khi định thức của F_S là +1 hoặc − 1 và chúng không tạo thành một cây bao trùm khi và chỉ khi định thức bằng 0. Từ đó suy ra biểu thức cần chứng minh.

Tham khảo

John M. Harris, Jeffry L. Hirst, Michael J. Mossinghoff (2008). Combinatorics and Graph Theory. Undergraduate Texts in Mathematics (ấn bản thứ 2). Springer.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
Tutte, W. T. (2001), Graph Theory, Cambridge University Press, tr. 138, ISBN 978-0-521-79489-3

Tham khảo