Cấu trúc dữ liệu và Giải thuật Bài 133: Mã Prüfer (Prüfer Code & Định lý Cayley) - Kỹ thuật nén cấu trúc cây và bài toán đếm cây có nhãn.

Trong lý thuyết đồ thị và tổ hợp đại số, bài toán xác định số lượng cây khung có nhãn (Labeled Trees) trên tập $n$ đỉnh là một cột mốc lịch sử. Năm 1889, nhà toán học Arthur Cayley công bố Công thức Cayley (Cayley's Formula), khẳng định rằng số lượng cây có nhãn khác nhau trên $n$ đỉnh ($n \ge 2$) chính xác là $n^{n-2}$. Tuy nhiên, chứng minh ban đầu của Cayley rất phức tạp và thiếu tính kiến thiết.

Năm 1918, nhà toán học người Đức Heinz Prüfer đã đưa ra một chứng minh mang tính đột phá: thiết lập một song ánh (bijection) hoàn hảo giữa tập hợp mọi cây có nhãn $n$ đỉnh và tập hợp mọi chuỗi số có độ dài $n - 2$ lấy từ bảng chữ cái $\{0, 1, \dots, n-1\}$ (hoặc $\{1, \dots, n\}$). Chuỗi số này được gọi là Mã Prüfer (Prüfer Code / Prüfer Sequence).

Không chỉ giải quyết bài toán đếm, mã Prüfer còn là một kỹ thuật nén dữ liệu cây không tổn hao và là công cụ tối ưu để sinh cây ngẫu nhiên phân phối đều (Uniform Random Tree Generation) trong các hệ thống mô phỏng đồ thị.

1. Định nghĩa Mã Prüfer và Tính chất Song ánh

Cho một cây vô hướng có nhãn $T = (V, E)$ gồm $n$ đỉnh ($n \ge 2$), với nhãn các đỉnh thuộc tập $\{0, 1, \dots, n-1\}$.

Quy trình xây dựng mã Prüfer (Tree $\to$ Sequence)

Chuỗi Prüfer $P$ có độ dài đúng $n - 2$, được tạo qua $n - 2$ bước:

1. Tìm nút lá (nút có bậc bằng 1) có nhãn nhỏ nhất hiện tại trong cây.

2. Ghi lại nhãn của đỉnh kề duy nhất với nút lá đó vào chuỗi Prüfer.

3. Xóa nút lá đó cùng cạnh nối của nó khỏi cây.

4. Lặp lại quá trình cho đến khi cây chỉ còn đúng 2 đỉnh.

       Cây ban đầu (n = 5):
          (0) --- (2) --- (3) --- (4)
                   |
                  (1)

       Bước 1: Lá nhỏ nhất là 0 (kề với 2) -> Ghi 2, xóa 0.
          (1) --- (2) --- (3) --- (4)

       Bước 2: Lá nhỏ nhất là 1 (kề với 2) -> Ghi 2, xóa 1.
          (2) --- (3) --- (4)

       Bước 3: Lá nhỏ nhất là 2 (kề với 3) -> Ghi 3, xóa 2.
          (3) --- (4) (Dừng lại vì còn 2 đỉnh)

       => Mã Prüfer thu được: [2, 2, 3] (độ dài 5 - 2 = 3)

Các tính chất toán học then chốt

1. Quan hệ giữa bậc đỉnh và tần suất xuất hiện: Một đỉnh $v$ có bậc $d(v)$ trong cây ban đầu sẽ xuất hiện đúng $d(v) - 1$ lần trong mã Prüfer.

   • Các nút lá ($d = 1$) không bao giờ xuất hiện trong chuỗi Prüfer ($1 - 1 = 0$ lần).

   • Đỉnh có bậc càng cao thì xuất hiện càng nhiều lần trong chuỗi.

2. Chứng minh Định lý Cayley:

   • Có $n$ cách chọn cho mỗi vị trí trong chuỗi Prüfer độ dài $n - 2$.

   • Tổng số chuỗi Prüfer khả dĩ là $n \times n \times \dots \times n = n^{n-2}$.

   • Vì ánh xạ giữa cây và chuỗi là một song ánh 1-1, số lượng cây có nhãn phân biệt trên $n$ đỉnh chính bằng $n^{n-2}$.

3. Mở rộng Cayley: Đếm cây với dãy bậc cố định:

   Nếu cho trước bậc của từng đỉnh là $d_1, d_2, \dots, d_n$ thỏa mãn $\sum_{i=1}^n d_i = 2n - 2$ ($d_i \ge 1$), số lượng cây có nhãn thỏa mãn chính là số hoán vị lặp (hệ số đa thức - Multinomial Coefficient) của chuỗi Prüfer:

   $$\frac{(n-2)!}{(d_1-1)! \, (d_2-1)! \, \cdots \, (d_n-1)!}$$

2. Thuật toán Mã hóa và Giải mã Tuyến tính $O(n)$

Cách tiếp cận ngây thơ sử dụng hàng đợi ưu tiên (Min-Heap) để tìm lá nhỏ nhất ở mỗi bước sẽ tiêu tốn $O(n \log n)$ thời gian. Tuy nhiên, bằng kỹ thuật con trỏ trượt không quay lui (Two Pointers / Moving Pointer), ta có thể thực hiện cả việc mã hóa và giải mã trong thời gian tuyến tính $O(n)$.

Thuật toán Mã hóa Tuyến tính (Linear Encode)

1. Chọn đỉnh $n-1$ làm gốc tạm thời của cây và dùng DFS xác định mảng parent[u] cho mọi đỉnh $u \neq n-1$. Do đỉnh $n-1$ có nhãn lớn nhất, nó không bao giờ bị xóa trước hai đỉnh cuối cùng, nên đỉnh kề của mọi lá $u$ bị xóa luôn chính là parent[u].

2. Khởi tạo con trỏ ptr = 0. Tìm lá đầu tiên có nhãn nhỏ nhất: tăng ptr cho đến khi gặp đỉnh có $\text{deg}[\text{ptr}] = 1$.

3. Gán leaf = ptr. Lặp qua $n - 2$ bước:

   • Thêm $p = \text{parent}[\text{leaf}]$ vào mã Prüfer.

   • Giảm bậc: $\text{deg}[p] \gets \text{deg}[p] - 1$.

   • Điểm mấu chốt: Nếu sau khi giảm bậc, $p$ trở thành nút lá ($\text{deg}[p] = 1$) và $p < \text{ptr}$, thì $p$ lập tức trở thành nút lá nhỏ nhất toàn cục mới. Ta gán ngay leaf = p cho bước tiếp theo mà không cần tăng ptr.

   • Ngược lại, tiếp tục tăng ptr cho đến khi tìm thấy nút lá tiếp theo và gán leaf = ptr.

Thuật toán Giải mã Tuyến tính (Linear Decode)

1. Tính mảng bậc ban đầu từ chuỗi Prüfer: gán $\text{deg}[i] = 1$ cho mọi $i \in [0, n-1]$, sau đó với mỗi giá trị $x$ trong chuỗi, tăng $\text{deg}[x] \gets \text{deg}[x] + 1$.

2. Khởi tạo con trỏ ptr = 0. Tăng ptr đến khi tìm được đỉnh đầu tiên có $\text{deg}[\text{ptr}] = 1$. Gán leaf = ptr.

3. Duyệt tuần tự từng phần tử $v$ trong chuỗi Prüfer:

   • Nối cạnh giữa leaf và $v$.

   • Giảm bậc: $\text{deg}[\text{leaf}] \gets \text{deg}[\text{leaf}] - 1$ và $\text{deg}[v] \gets \text{deg}[v] - 1$.

   • Nếu $\text{deg}[v] = 1$ và $v < \text{ptr}$, gán trực tiếp leaf = v.

   • Ngược lại, tăng ptr đến khi gặp đỉnh có $\text{deg}[\text{ptr}] = 1$ và gán leaf = ptr.

4. Sau khi duyệt hết chuỗi, còn lại đúng 2 đỉnh có bậc bằng 1 (trong đó một đỉnh là leaf và đỉnh kia chính là $n-1$). Nối cạnh cuối cùng giữa leaf và $n-1$.

3. Hiện thực hóa Mã Prüfer bằng Golang

Đoạn mã Golang dưới đây cài đặt hoàn chỉnh hai hàm Encode và Decode với độ phức tạp thời gian và không gian tối ưu $O(n)$, kèm theo hàm kiểm chứng tính toàn vẹn (Round-trip verification):

Go

package main

import (
	"fmt"
	"reflect"
	"sort"
)

type Edge struct {
	u, v int
}

// Chuẩn hóa danh sách cạnh để so sánh hai cây
func normalizeEdges(edges []Edge) []Edge {
	res := make([]Edge, len(edges))
	for i, e := range edges {
		if e.u > e.v {
			res[i] = Edge{u: e.v, v: e.u}
		} else {
			res[i] = e
		}
	}
	sort.Slice(res, func(i, j int) bool {
		if res[i].u != res[j].u {
			return res[i].u < res[j].u
		}
		return res[i].v < res[j].v
	})
	return res
}

// 1. Mã hóa cây thành Prüfer Code trong O(n)
func PrüferEncode(n int, edges []Edge) []int {
	if n <= 2 {
		return []int{}
	}

	adj := make([][]int, n)
	deg := make([]int, n)
	for _, e := range edges {
		adj[e.u] = append(adj[e.u], e.v)
		adj[e.v] = append(adj[e.v], e.u)
		deg[e.u]++
		deg[e.v]++
	}

	// Đặt gốc tại n - 1 và xác định parent của từng nút
	parent := make([]int, n)
	var dfs func(u, p int)
	dfs = func(u, p int) {
		parent[u] = p
		for _, v := range adj[u] {
			if v != p {
				dfs(v, u)
			}
		}
	}
	dfs(n-1, -1)

	// Tìm lá đầu tiên
	ptr := 0
	for ptr < n && deg[ptr] != 1 {
		ptr++
	}

	leaf := ptr
	code := make([]int, n-2)

	for i := 0; i < n-2; i++ {
		p := parent[leaf]
		code[i] = p
		deg[p]--

		if deg[p] == 1 && p < ptr {
			leaf = p
		} else {
			ptr++
			for ptr < n && deg[ptr] != 1 {
				ptr++
			}
			leaf = ptr
		}
	}

	return code
}

// 2. Giải mã Prüfer Code thành cây trong O(n)
func PrüferDecode(n int, code []int) []Edge {
	if n == 1 {
		return []Edge{}
	}
	if n == 2 {
		return []Edge{{u: 0, v: 1}}
	}

	deg := make([]int, n)
	for i := 0; i < n; i++ {
		deg[i] = 1
	}
	for _, v := range code {
		deg[v]++
	}

	// Tìm lá đầu tiên
	ptr := 0
	for ptr < n && deg[ptr] != 1 {
		ptr++
	}

	leaf := ptr
	edges := make([]Edge, 0, n-1)

	for _, v := range code {
		edges = append(edges, Edge{u: leaf, v: v})
		deg[leaf]--
		deg[v]--

		if deg[v] == 1 && v < ptr {
			leaf = v
		} else {
			ptr++
			for ptr < n && deg[ptr] != 1 {
				ptr++
			}
			leaf = ptr
		}
	}

	// Cạnh cuối cùng nối leaf với đỉnh n - 1
	edges = append(edges, Edge{u: leaf, v: n - 1})
	return edges
}

func main() {
	// Khởi tạo cây gồm 6 đỉnh (0 đến 5)
	// Cấu trúc cây:
	//       0 --- 2 --- 3 --- 5
	//             |     |
	//             1     4
	n := 6
	originalEdges := []Edge{
		{u: 0, v: 2},
		{u: 1, v: 2},
		{u: 2, v: 3},
		{u: 3, v: 4},
		{u: 3, v: 5},
	}

	fmt.Printf("Số lượng đỉnh: %d\n", n)
	fmt.Printf("Danh sách cạnh gốc: %+v\n", originalEdges)

	// 1. Mã hóa cây sang Prüfer Code
	code := PrüferEncode(n, originalEdges)
	fmt.Printf("Mã Prüfer tạo thành (độ dài %d): %v\n", len(code), code)

	// 2. Giải mã Prüfer Code ngược lại thành các cạnh
	reconstructedEdges := PrüferDecode(n, code)
	fmt.Printf("Danh sách cạnh khôi phục: %+v\n", reconstructedEdges)

	// 3. Kiểm chứng tính bảo toàn cấu trúc
	origNorm := normalizeEdges(originalEdges)
	reconNorm := normalizeEdges(reconstructedEdges)
	isIdentical := reflect.DeepEqual(origNorm, reconNorm)
	fmt.Printf("Cấu trúc được khôi phục chính xác 100%%? -> %t\n", isIdentical)
}

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

Tại sao con trỏ trượt ptr đạt độ phức tạp $O(n)$?

• Con trỏ ptr chỉ di chuyển theo chiều tăng dần từ $0$ đến $n-1$, không bao giờ bị giảm giá trị. Tổng số lần dịch chuyển của ptr trên toàn bộ thuật toán bị chặn trên bởi $n$.

• Khi một nút cha $p$ bị giảm bậc xuống 1:

  • Nếu $p < \text{ptr}$, ta xử lý ngay $p$ mà không làm thay đổi ptr. Vì trước đó mọi nút nhỏ hơn ptr đều đã có bậc $\neq 1$ (hoặc đã bị xóa), $p$ là nút duy nhất nhỏ hơn ptr có bậc bằng 1.

  • Nếu $p > \text{ptr}$, $p$ sẽ được con trỏ ptr quét qua trong tương lai.

• Do đó, mọi đỉnh và cạnh đều được xử lý trong thời gian hằng số $O(1)$, mang lại tổng thời gian chạy tuyến tính tuyệt đối.

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

• Sinh ngẫu nhiên Cây có nhãn theo phân phối đều (Uniform Random Tree Generator): Trong việc kiểm thử tự động (Stress Testing) và đánh giá thuật toán mạng, để sinh một cây ngẫu nhiên phân phối đều trong số $n^{n-2}$ cây, ta chỉ cần sinh ngẫu nhiên một mảng gồm $n - 2$ số nguyên trong đoạn $[0, n-1]$, sau đó gọi hàm PrüferDecode trong $O(n)$.

• Thiết kế Cây mạng thỏa mãn giới hạn cổng mạng (Degree-Constrained Network Synthesis): Khi thiết lập mạng kết nối giữa các máy chủ mà mỗi máy chủ $i$ chỉ có tối đa $d_i$ cổng mạng (ports), công thức Cayley mở rộng qua mã Prüfer cho phép tính toán chính xác số lượng topo mạng khả thi mà không cần duyệt đồ thị.

• Thuật toán Di truyền trên Cây (Genetic Algorithms for Spanning Trees): Biểu diễn nhiễm sắc thể (chromosome) của cây khung dưới dạng chuỗi Prüfer giúp các toán tử lai ghép (Crossover) và đột biến (Mutation) diễn ra như trên mảng 1D thông thường, luôn đảm bảo con sinh ra là một cây hợp lệ mà không lo bị tạo chu trình hay mất tính liên thông.