Cấu trúc dữ liệu và Giải thuật Bài 135: Định lý BEST (BEST Theorem) - Đếm số lượng chu trình Euler trên đồ thị có hướng kết hợp Matrix Tree Theorem.

Ở các bài toán đồ thị cơ bản, thuật toán Hierholzer hoặc Fleury cho phép tìm kiếm một chu trình Euler trong thời gian tuyến tính $O(V + E)$ nếu đồ thị thỏa mãn điều kiện Euler. Tuy nhiên, bài toán đặt ra trong giải mã trình tự gen (Genome Assembly), sinh chuỗi de Bruijn trong mật mã học, hay cơ học thống kê lại là: Có chính xác bao nhiêu chu trình Euler phân biệt tồn tại trên đồ thị?

Trên đồ thị vô hướng, bài toán đếm số chu trình Euler là một bài toán cực kỳ khó — đã được Leslie Ann Goldberg và Mark Jerrum chứng minh là thuộc lớp #P-complete (không tồn tại thuật toán thời gian đa thức trừ khi P = NP).

Ngược lại, trên đồ thị có hướng (Directed Graphs), bài toán này có thể giải quyết chính xác trong thời gian đa thức $O(V^3)$ . Kết quả kinh điển này được phát hiện bởi bốn nhà toán học: Bruijn, van Aardenne-Ehrenfest, Smith và Tutte (1951), được gọi là Định lý BEST (BEST Theorem) — một cầu nối giữa lý thuyết đồ thị Euler và Định lý Cây Khung Kirchhoff (Bài 134).

1. Phát biểu Định lý BEST

Cho $G = (V, E)$ là một đồ thị có hướng liên thông (bỏ qua các đỉnh cô lập có bậc 0) và thỏa mãn điều kiện Euler:

$\deg^+(v) = \deg^-(v) = d_v \quad (\forall v \in V)$

với $d_v$ là bán bậc ra (cũng chính là bán bậc vào) của đỉnh $v$ .

Định lý BEST: Số lượng chu trình Euler có hướng phân biệt $\text{ec}(G)$ (tính theo lớp tương đương dịch vòng của dãy cạnh) được tính bằng công thức:

$\text{ec}(G) = t_r(G) \cdot \prod_{v \in V} (d_v - 1)!$
Trong đó:

$t_r(G)$ là số lượng Cây phân nhánh hướng tâm (In-Arborescence / In-Tree) có gốc tại một đỉnh $r$ tùy ý (tức là cây khung có hướng mà từ mọi đỉnh $v \neq r$ đều có duy nhất một đường đi đến $r$ ).

Đại lượng $t_r(G)$ mang giá trị giống hệt nhau đối với mọi cách chọn gốc $r \in V$ .

Lưu ý về quy ước đếm

Chu trình Euler (Eulerian Circuits / Tours up to cyclic equivalence): Hai chu trình được coi là giống nhau nếu chúng là hoán vị vòng quanh của cùng một chuỗi các cạnh.
Nếu xét chu trình Euler có đỉnh bắt đầu cố định tại $r$ :

$\text{ec}_r(G) = d_r \cdot \text{ec}(G) = t_r(G) \cdot d_r! \cdot \prod_{v \neq r} (d_v - 1)!$
Nếu xét chu trình Euler bắt đầu bằng một cạnh có hướng cố định $e$ : Số lượng chu trình chính xác bằng $\text{ec}(G)$ (vì mỗi cạnh xuất hiện đúng một lần trong mỗi chu trình).

2. Bản chất Tổ hợp: Song ánh giữa Chu trình Euler và Cây khung In-Tree

Tại sao công thức lại xuất hiện thừa số $(d_v - 1)!$ và số cây khung $t_r(G)$ ?

Xét một chu trình Euler bất kỳ xuất phát và kết thúc tại đỉnh $r$ :

Khi chu trình di chuyển qua đồ thị, mỗi đỉnh $v \neq r$ sẽ được thăm và rời đi đúng $d_v$ lần.
Với mỗi đỉnh $v \neq r$ , ta đánh dấu cạnh cuối cùng được sử dụng để rời khỏi $v$ (Last Exit Edge) trong hành trình Euler.
Tính chất then chốt: Tập hợp gồm $\vert{}V\vert{} - 1$ cạnh "lần rời đi cuối cùng" này bắt buộc phải tạo thành một Cây phân nhánh hướng về $r$ (In-Tree rooted at $r$ ):
- Mỗi đỉnh $v \neq r$ có đúng 1 cạnh đi ra.
- Tập cạnh này không thể chứa chu trình có hướng (vì nếu tạo chu trình, chu trình Euler sẽ bị kẹt bên trong đó và không thể quay về đỉnh kết thúc $r$ ).
Đối với mỗi đỉnh $v \neq r$ : Trong số $d_v$ lần rời khỏi $v$ , cạnh rời đi cuối cùng đã bị cố định bởi cấu trúc cây khung, còn $d_v - 1$ cạnh rời đi trước đó có thể xuất hiện theo bất kỳ thứ tự nào trong $(d_v - 1)!$ hoán vị.
Đối với gốc $r$ : Lần rời đi cuối cùng của $r$ cũng bị ràng buộc bởi thời điểm hoàn tất toàn bộ chu trình, để lại $(d_r - 1)!$ cách sắp xếp các lần xuất phát trước đó.

Do mỗi cặp gồm một In-Tree và một bộ thứ tự cạnh rời đi xác định duy nhất một chu trình Euler hợp lệ và ngược lại, ta thiết lập được một song ánh tổ hợp hoàn hảo.

       Chu trình Euler hoàn chỉnh: (r -> ... -> v -> ... -> r)
       
       Tại đỉnh v (bậc d_v = 3):
       - Lần rời 1: Cạnh e_1   \  Có (3 - 1)! = 2! cách
       - Lần rời 2: Cạnh e_2   /  sắp xếp thứ tự
       - Lần rời 3: Cạnh e_last --------> Nằm trong In-Tree hướng về r

3. Tính toán $t_r(G)$ qua Ma trận Laplace có hướng

Theo biến thể của Định lý Matrix Tree (Bài 134), số lượng cây phân nhánh hướng về gốc $r$ được tính bằng định thức của ma trận con Laplace:

Ma trận Laplace có hướng cho In-Tree

Ma trận $L$ kích thước $n \times n$ được định nghĩa:

Trên đường chéo chính: $L_{i, i} = \deg^+(v_i) = d_{v_i}$ (bán bậc ra của đỉnh $v_i$ ).
Ngoài đường chéo chính: $L_{i, j} = -A_{i, j}$ (với $A_{i, j}$ là số cạnh có hướng nối trực tiếp từ $v_i \to v_j$ ).

Khi đó, số cây phân nhánh hướng tâm về $r$ bằng định thức của ma trận con bỏ đi hàng $r$ và cột $r$ :

$t_r(G) = \det(L^{(r, r)})$

Vì đồ thị có hướng là đồ thị Euler ( $\deg^+(v) = \deg^-(v)$ ), tổng các phần tử trên mỗi hàng và mỗi cột của $L$ đều bằng 0. Theo tính chất đại số tuyến tính, mọi phần bù đại số cấp $(n-1)$ của $L$ đều bằng nhau, chứng minh toán học độc lập rằng $t_r(G)$ không đổi với bất kỳ gốc $r$ nào.

4. Hiện thực hóa Thuật toán BEST bằng Golang

Chương trình Golang dưới đây thực hiện:

Kiểm tra tính liên thông yếu và điều kiện cân bằng bậc Euler: $\deg^+(v) = \deg^-(v)$ .
Dựng Ma trận Laplace có hướng.
Tính định thức con $t_r(G) = \det(L^{(0, 0)})$ theo modulo $10^9 + 7$ bằng phép khử Gauss.
Nhân với tích các giai thừa $\prod_{v \in V} (d_v - 1)! \pmod{10^9 + 7}$ .

package main

import (
	"fmt"
)

const MOD int64 = 1_000_000_007

type DirectedEdge struct {
	u, v int
}

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
}

func modInv(n int64) int64 {
	return modPow(n, MOD-2)
}

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

	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++ {
		pivot := -1
		for r := i; r < k; r++ {
			if a[r][i] != 0 {
				pivot = r
				break
			}
		}

		if pivot == -1 {
			return 0
		}

		if pivot != i {
			a[i], a[pivot] = a[pivot], a[i]
			sign = -sign
		}

		invPivot := modInv(a[i][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ố chu trình Euler phân biệt trên đồ thị có hướng bằng BEST Theorem
func CountEulerianCircuits(n int, edges []DirectedEdge) int64 {
	if len(edges) == 0 {
		return 0
	}

	inDeg := make([]int, n)
	outDeg := make([]int, n)
	adjCount := make([][]int64, n)
	for i := 0; i < n; i++ {
		adjCount[i] = make([]int64, n)
	}

	for _, e := range edges {
		outDeg[e.u]++
		inDeg[e.v]++
		adjCount[e.u][e.v]++
	}

	// 1. Kiểm tra điều kiện Euler: in-degree == out-degree cho mọi đỉnh
	for i := 0; i < n; i++ {
		if inDeg[i] != outDeg[i] {
			return 0 // Không phải đồ thị Euler
		}
	}

	// 2. Xây dựng Ma trận Laplace có hướng cho In-Tree
	// L[i][i] = outDeg[i], L[i][j] = -adjCount[i][j]
	L := make([][]int64, n)
	for i := 0; i < n; i++ {
		L[i] = make([]int64, n)
		L[i][i] = int64(outDeg[i])
		for j := 0; j < n; j++ {
			if i != j {
				L[i][j] = -adjCount[i][j]
			}
		}
	}

	// 3. 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]
		}
	}

	// 4. Tính số In-Tree t_r(G)
	t_r := determinantMod(subMat, n-1)
	if t_r == 0 {
		return 0 // Đồ thị không liên thông đến gốc
	}

	// 5. Tính tích giai thừa: prod = prod_{v in V} (d_v - 1)!
	fact := make([]int64, len(edges)+1)
	fact[0] = 1
	for i := 1; i <= len(edges); i++ {
		fact[i] = (fact[i-1] * int64(i)) % MOD
	}

	ans := t_r
	for i := 0; i < n; i++ {
		d := outDeg[i]
		if d > 0 {
			ans = (ans * fact[d-1]) % MOD
		}
	}

	return ans
}

func main() {
	// Kiểm thử 1: Đồ thị 2 đỉnh với 2 cạnh khứ hồi (0 -> 1 và 1 -> 0)
	// Chỉ có duy nhất 1 chu trình Euler: 0 -> 1 -> 0
	edgesSimple := []DirectedEdge{
		{0, 1},
		{1, 0},
	}
	fmt.Printf("Đồ thị 2 đỉnh (vòng lặp đơn): %d chu trình Euler\n",
		CountEulerianCircuits(2, edgesSimple))

	// Kiểm thử 2: Đồ thị đa cạnh gồm 2 đỉnh với 2 cạnh xuôi và 2 cạnh ngược
	// Cạnh: a1, a2 (0 -> 1) và b1, b2 (1 -> 0)
	// Có 2 cách chọn cạnh về và 2 cách ghép -> Kỳ vọng: 2 chu trình phân biệt
	edgesMulti := []DirectedEdge{
		{0, 1}, {0, 1},
		{1, 0}, {1, 0},
	}
	fmt.Printf("Đồ thị đa cạnh 2 đỉnh (2 xuôi, 2 ngược): %d chu trình Euler\n",
		CountEulerianCircuits(2, edgesMulti))

	// Kiểm thử 3: Đồ thị de Bruijn B(2, 2) sinh chuỗi nhị phân tuần hoàn bậc 3
	// Gồm 4 đỉnh (00, 01, 10, 11) tương ứng (0, 1, 2, 3), mỗi đỉnh có bán bậc ra = vào = 2
	edgesDeBruijn := []DirectedEdge{
		{0, 0}, {0, 1}, // 00 -> 00, 00 -> 01
		{1, 2}, {1, 3}, // 01 -> 10, 01 -> 11
		{2, 0}, {2, 1}, // 10 -> 00, 10 -> 01
		{3, 2}, {3, 3}, // 11 -> 10, 11 -> 11
	}
	// Theo lý thuyết chuỗi de Bruijn: Số chuỗi de Bruijn B(k, n) là (k!)^(k^(n-1)) / k^n
	// Với k = 2, n = 3: (2!)^(2^2) / 2^3 = 16 / 8 = 2 chu trình Euler phân biệt
	fmt.Printf("Đồ thị de Bruijn B(2, 2): %d chu trình Euler (Kỳ vọng: 2)\n",
		CountEulerianCircuits(4, edgesDeBruijn))
}

5. Phân tích độ phức tạp thuật toán

Thao tác	Thuật toán	Độ phức tạp thời gian	Chi phí bộ nhớ
Kiểm tra bậc Euler	Đếm bậc đỉnh	$O(V + E)$	$O(V)$
Dựng Ma trận Laplace	Ánh xạ bán bậc ra & kề	$O(V^2 + E)$	$O(V^2)$
Tính $t_r(G)$ (Định thức)	Khử Gauss theo Modulo	$O(V^3)$	$O(V^2)$
Tích giai thừa $\prod(d_v - 1)!$	Tiền xử lý giai thừa	$O(E + V)$	$O(E)$
Tổng thể thuật toán	—	$O(V^3 + E)$	$O(V^2 + E)$

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

Định lượng Độ mơ hồ trong Lắp ráp Bộ gen (Genome Assembly Ambiguity): Trong kỹ thuật giải mã gen thế hệ mới (NGS), đoạn đọc DNA ngắn được cắt thành các $k$ -mer để dựng đồ thị de Bruijn. Định lý BEST cho phép tính chính xác số lượng bộ gen hợp lệ có thể được tái tạo từ tập dữ liệu giải trình tự, giúp đánh giá độ tin cậy của thuật toán ghép gen.
Đếm và Sinh chuỗi de Bruijn trong Mật mã học: Chuỗi de Bruijn bậc $n$ trên bảng chữ cái kích thước $k$ tương đương với một chu trình Euler trên đồ thị de Bruijn $B(k, n-1)$ . Định lý BEST cung cấp chứng minh giải tích chính xác cho công thức nổi tiếng:

$N = \frac{(k!)^{k^{n-1}}}{k^n}$
Mô hình Dòng hạt trong Vật lý thống kê (Directed Sandpile Models): Định lý BEST được áp dụng để xác định số lượng cấu hình dừng (recurrent configurations) và đường đi của dòng hạt phân rã trên các mạng tinh thể có hướng.

cấu trúc dữ liệu