Cấu trúc dữ liệu và Giải thuật Bài 134: Định lý Cây Khung Kirchhoff (Kirchhoff's Matrix Tree Theorem) - Đếm số lượng cây khung trên đồ thị tổng quát bằng ma trận Laplace.

Ở Bài 133, chúng ta đã chứng minh công thức Cayley bằng mã Prüfer, xác định số lượng cây khung có nhãn trên đồ thị đầy đủ $K_n$ là $n^{n-2}$. Tuy nhiên, trong thực tế thiết kế vi mạch, phân tích độ bền mạng viễn thông, hay lý thuyết mạng lưới phức tạp, đồ thị hiếm khi ở dạng đầy đủ. Một câu hỏi cốt lõi được đặt ra: Làm thế nào để đếm chính xác số lượng cây khung trên một đồ thị bất kỳ $G = (V, E)$ chứa cấu trúc cạnh tùy ý, đa cạnh (multigraph), cạnh có trọng số, hoặc thậm chí là cạnh có hướng?

Năm 1847, xuất phát từ việc phân tích mạng lưới mạch điện và các định luật dòng điện/điện thế, nhà vật lý học Gustav Kirchhoff đã phát hiện ra mối liên hệ giữa đại số tuyến tính và lý thuyết đồ thị: Định lý Cây Khung Kirchhoff (Kirchhoff's Matrix Tree Theorem). Định lý này chuyển bài toán đếm tổ hợp phức tạp thành bài toán tính định thức của Ma trận Laplace (Laplacian Matrix) trong thời gian đa thức $O(V^3)$.

1. Cơ sở Toán học: Ma trận Laplace (Laplacian Matrix)

Cho một đồ thị vô hướng $G = (V, E)$ gồm $n$ đỉnh (không chứa khuyên tự nối - self-loops, nhưng có thể chứa đa cạnh giữa hai đỉnh).

Định nghĩa Ma trận Laplace

Ma trận Laplace $L$ kích thước $n \times n$ của đồ thị $G$ được định nghĩa bằng hiệu giữa Ma trận bậc (Degree Matrix - $D$) và Ma trận kề (Adjacency Matrix - $A$):

$$L = D - A$$

Chi tiết các phần tử của ma trận $L = [L_{i, j}]$:

• Trên đường chéo chính ($i = j$): $L_{i, i} = \deg(v_i)$ (bậc của đỉnh $v_i$, tức số cạnh nối với $v_i$).

• Ngoài đường chéo ($i \neq j$): $L_{i, j} = -a_{i, j}$, trong đó $a_{i, j}$ là số lượng cạnh nối trực tiếp giữa hai đỉnh $v_i$ và $v_j$.

       Đồ thị vô hướng 4 đỉnh:                  Ma trận Laplace L:
               (0) --- (1)                       [  2  -1  -1   0 ]
                |   X   |                        [ -1   3  -1  -1 ]
               (2) --- (3)                       [ -1  -1   3  -1 ]
              (có cạnh 0-3)                      [  0  -1  -1   2 ]

Các tính chất đại số quan trọng của Ma trận Laplace

1. Tổng mỗi hàng và mỗi cột luôn bằng 0:

   $$\sum_{j=1}^n L_{i, j} = \deg(v_i) - \sum_{j \neq i} a_{i, j} = 0$$

2. Không khả nghịch: Do vector toàn số 1 ($\mathbf{1} = [1, 1, \dots, 1]^T$) thỏa mãn $L \mathbf{1} = \mathbf{0}$, ma trận $L$ luôn có ít nhất một giá trị riêng bằng 0, dẫn đến $\det(L) = 0$.

3. Hạng của ma trận: Nếu đồ thị $G$ liên thông, hạng của ma trận Laplace đúng bằng $n - 1$.

2. Phát biểu Định lý Cây Khung Kirchhoff

Định lý Cây Khung Kirchhoff: Cho $G$ là một đồ thị vô hướng liên thông gồm $n$ đỉnh với ma trận Laplace $L$. Gọi $L^{(k, k)}$ là ma trận con cấp $(n - 1) \times (n - 1)$ thu được bằng cách loại bỏ hàng thứ $k$ và cột thứ $k$ bất kỳ khỏi $L$. Khi đó, số lượng cây khung $\tau(G)$ của đồ thị $G$ đúng bằng định thức của $L^{(k, k)}$:

$$\tau(G) = \det(L^{(k, k)})$$

Hơn nữa, với mọi cặp chỉ số $i, j$ bất kỳ ($1 \le i, j \le n$), phần bù đại số (cofactor) $(-1)^{i+j} \det(L^{(i, j)})$ đều mang cùng một giá trị bằng $\tau(G)$.

Trực giác đằng sau định lý: Công thức Binet-Cauchy

Ma trận Laplace có thể phân rã thành $L = B \cdot B^T$, trong đó $B$ là ma trận liên thuộc đỉnh - cạnh (Incidence Matrix) có kích thước $n \times m$. Khi áp dụng công thức Binet-Cauchy để tính định thức của ma trận con cấp $n-1$, mỗi số hạng khác 0 trong khai triển định thức tương ứng 1-1 với một tập con gồm $n-1$ cạnh độc lập tuyến tính, tức là đúng một cây khung hợp lệ.

3. Các biến thể mở rộng của Định lý Kirchhoff

A. Cây khung có trọng số (Weighted Spanning Trees)

Nếu mỗi cạnh $e = (u, v)$ có một trọng số thực $w(e)$:

• $L_{i, i} = \sum_{v \in \text{adj}(u)} w(u, v)$

• $L_{i, j} = -w(i, j)$ với $i \neq j$

• Định thức con $\det(L^{(k, k)})$ lúc này sẽ bằng tổng tích trọng số của tất cả các cây khung:

  $$\det(L^{(k, k)}) = \sum_{T \in \text{SpanningTrees}(G)} \left( \prod_{e \in T} w(e) \right)$$

B. Cây phân nhánh trên đồ thị có hướng (Directed Matrix Tree Theorem)

Trên đồ thị có hướng, ta dùng Bán bậc vào (In-degree) hoặc Bán bậc ra (Out-degree) để định nghĩa ma trận Laplace có hướng:

• $L_{i, i}^{\text{in}} = \text{deg}^{\text{in}}(v_i)$, $L_{i, j}^{\text{in}} = -(\text{số cung từ } v_j \to v_i)$.

• Khi đó, định thức con bỏ hàng $r$ và cột $r$ của $L^{\text{in}}$ sẽ bằng số lượng Cây phân nhánh (Arborescences) có gốc tại $r$ với các cung hướng ra ngoài từ gốc.

4. Thuật toán Tính Định thức bằng Khử Gauss (Gaussian Elimination)

Vì số lượng cây khung tăng trưởng theo hàm mũ, các bài toán tổ hợp thường yêu cầu tính kết quả theo modulo một số nguyên tố lớn $P$ (ví dụ: $10^9 + 7$).

Ta áp dụng Thuật toán Khử Gauss để đưa ma trận con $(n-1) \times (n-1)$ về ma trận tam giác trên trong thời gian $O(n^3)$:

1. Với mỗi cột $i$ từ $0$ đến $n-2$:

   • Tìm hàng $r \ge i$ có phần tử $A[r][i] \neq 0$ để làm pivot. Nếu không tìm thấy, $\det = 0$ (đồ thị mất liên thông).

   • Đổi chỗ hai hàng $i$ và $r$ (mỗi lần đổi chỗ hàng, đổi dấu định thức: $\det \gets -\det$).

   • Dùng phép biến đổi hàng sơ cấp để triệt tiêu các phần tử bên dưới pivot:

     $$A[k][j] \gets A[k][j] - \left( A[k][i] \cdot A[i][i]^{-1} \right) \cdot A[i][j] \pmod P$$

2. Định thức là tích các phần tử trên đường chéo chính của ma trận tam giác:

   $$\det = \prod_{i=0}^{n-2} A[i][i] \pmod P$$

5. Hiện thực hóa bằng Golang

Chương trình Golang dưới đây xây dựng Ma trận Laplace từ danh sách cạnh vô hướng và tính số lượng cây khung modulo $10^9 + 7$ bằng phép khử Gauss:

Go

package main

import (
	"fmt"
)

const MOD int64 = 1_000_000_007

type Edge struct {
	u, v int
}

// Lũy thừa nhị phân tính (base^exp) % MOD
func modPow(base, exp int64) int64 {
	res := int64(1)
	base %= MOD
	if base < 0 {
		base += MOD
	}
	for exp > 0 {
		if exp%2 == 1 {
			res = (res * base) % MOD
		}
		base = (base * base) % MOD
		exp /= 2
	}
	return res
}

// Nghịch đảo modulo qua định lý Fermat nhỏ: a^(MOD - 2) % MOD
func modInv(n int64) int64 {
	return modPow(n, MOD-2)
}

// Tính định thức của ma trận vuông k x k theo modulo MOD bằng Khử Gauss: O(k^3)
func determinantMod(mat [][]int64, k int) int64 {
	det := int64(1)
	sign := int64(1)

	// Chuẩn hóa ma trận trong trường Z_MOD
	a := make([][]int64, k)
	for i := 0; i < k; i++ {
		a[i] = make([]int64, k)
		for j := 0; j < k; j++ {
			a[i][j] = (mat[i][j]%MOD + MOD) % MOD
		}
	}

	for i := 0; i < k; i++ {
		// 1. Tìm pivot khác 0 tại cột i
		pivot := -1
		for r := i; r < k; r++ {
			if a[r][i] != 0 {
				pivot = r
				break
			}
		}

		if pivot == -1 {
			return 0 // Định thức bằng 0, đồ thị không liên thông
		}

		// 2. Đổi chỗ hàng i và pivot nếu cần
		if pivot != i {
			a[i], a[pivot] = a[pivot], a[i]
			sign = -sign
		}

		invPivot := modInv(a[i][i])

		// 3. Khử các hàng bên dưới
		for r := i + 1; r < k; r++ {
			if a[r][i] == 0 {
				continue
			}
			factor := (a[r][i] * invPivot) % MOD
			for c := i; c < k; c++ {
				diff := (factor * a[i][c]) % MOD
				a[r][c] = (a[r][c] - diff + MOD) % MOD
			}
		}

		det = (det * a[i][i]) % MOD
	}

	if sign < 0 {
		det = (MOD - det) % MOD
	}
	return det
}

// Đếm số lượng cây khung của đồ thị n đỉnh bằng Matrix Tree Theorem
func CountSpanningTrees(n int, edges []Edge) int64 {
	if n <= 1 {
		return 1
	}

	// 1. Xây dựng Ma trận Laplace kích thước n x n
	L := make([][]int64, n)
	for i := 0; i < n; i++ {
		L[i] = make([]int64, n)
	}

	for _, e := range edges {
		if e.u == e.v {
			continue // Khuyên không ảnh hưởng đến số cây khung
		}
		u, v := e.u, e.v
		L[u][u]++
		L[v][v]++
		L[u][v]--
		L[v][u]--
	}

	// 2. Trích xuất ma trận con cấp (n-1) x (n-1) bằng cách bỏ hàng 0 và cột 0
	subMat := make([][]int64, n-1)
	for i := 1; i < n; i++ {
		subMat[i-1] = make([]int64, n-1)
		for j := 1; j < n; j++ {
			subMat[i-1][j-1] = L[i][j]
		}
	}

	// 3. Tính định thức của ma trận con
	return determinantMod(subMat, n-1)
}

func main() {
	// Kiểm thử 1: Đồ thị đầy đủ K_4 (4 đỉnh, 6 cạnh)
	// Theo Cayley: 4^(4-2) = 16 cây khung
	n1 := 4
	edgesK4 := []Edge{
		{0, 1}, {0, 2}, {0, 3},
		{1, 2}, {1, 3}, {2, 3},
	}
	ansK4 := CountSpanningTrees(n1, edgesK4)
	fmt.Printf("Đồ thị đầy đủ K_4: %d cây khung (Kỳ vọng Cayley: 16)\n", ansK4)

	// Kiểm thử 2: Đồ thị chu trình C_4 (4 đỉnh, 4 cạnh tạo vòng khép kín)
	// Bỏ đi 1 cạnh bất kỳ trong 4 cạnh sẽ được 1 cây khung -> Kỳ vọng: 4 cây khung
	edgesC4 := []Edge{
		{0, 1}, {1, 2}, {2, 3}, {3, 0},
	}
	ansC4 := CountSpanningTrees(4, edgesC4)
	fmt.Printf("Đồ thị chu trình C_4: %d cây khung (Kỳ vọng: 4)\n", ansC4)

	// Kiểm thử 3: Đồ thị hai phía đầy đủ K_{2, 3} (2 đỉnh bên trái, 3 đỉnh bên phải)
	// Công thức giải tích cho K_{m, n} là m^(n-1) * n^(m-1) = 2^(3-1) * 3^(2-1) = 4 * 3 = 12
	edgesK23 := []Edge{
		{0, 2}, {0, 3}, {0, 4},
		{1, 2}, {1, 3}, {1, 4},
	}
	ansK23 := CountSpanningTrees(5, edgesK23)
	fmt.Printf("Đồ thị hai phía K_{2, 3}: %d cây khung (Kỳ vọng: 12)\n", ansK23)
}

6. Phân tích độ phức tạp

Nếu modulo $P$ không phải là số nguyên tố mà là hợp số tùy ý, thay vì tính nghịch đảo qua Fermat nhỏ, ta sử dụng Thuật toán Euclid mở rộng kết hợp biến đổi hàng tương tự như thuật toán tìm ước chung lớn nhất (Euclidean-based Gaussian Elimination) với độ phức tạp $O(V^3 + V^2 \log P)$.

7. Ứng dụng thực tế

• Đánh giá Độ tin cậy mạng (Network All-Terminal Reliability): Trong mô hình mạng ngẫu nhiên mà mỗi liên kết có xác suất gặp sự cố $p$, số lượng cây khung của topo mạng là hệ số quan trọng nhất trong chuỗi đa thức biểu diễn xác suất mạng vẫn giữ được tính liên thông toàn diện.

• Mạch điện trở tương đương & Bước ngẫu nhiên (Random Walks on Networks): Điện trở tương đương giữa hai nút $u$ và $v$ trong một mạng điện trở có thể biểu diễn qua tỷ số giữa số lượng cây khung và số lượng rừng 2 cây chứa $u, v$ ở hai thành phần khác nhau.

• Mô hình Hóa học lượng tử & Hóa học cấu trúc: Xác định số đồng phân phân tử và tính toán chỉ số Wiener, năng lượng phân tử trong các hợp chất thơm dị vòng thông qua phổ ma trận Laplace.