Cấu trúc dữ liệu và Giải thuật Bài 125: Đẳng cấu cây (Tree Isomorphism & Thuật toán AHU / Tree Hashing) - Nhận diện và phân loại cấu trúc cây tương đương trong thời gian tuyến tính.

Trong lý thuyết đồ thị tổng quát, bài toán Đẳng cấu đồ thị (Graph Isomorphism) là một trong những bài toán tính toán nổi tiếng nhất: nó chưa được chứng minh là thuộc lớp P (thời gian đa thức) và cũng chưa được chứng minh là NP-complete (nằm trong lớp độ phức tạp riêng gọi là GI-intermediate).

Tuy nhiên, khi đồ thị bị ràng buộc vào cấu trúc Cây (Tree) — một đồ thị vô hướng liên thông và không có chu trình — bài toán nhận diện hai cấu trúc cây có "đồng dạng" hay không lại có thể giải quyết triệt để trong thời gian tuyến tính $O(N)$ .

Khả năng xác định đẳng cấu cây đóng vai trò then chốt trong:

Tối ưu hóa trình biên dịch (Compiler Design): Nhận diện các cây cú pháp trừu tượng (Abstract Syntax Tree - AST) trùng lặp để thực hiện tối ưu hóa biểu thức con chung (Common Subexpression Elimination - CSE).
Hóa học tính toán & Tin sinh học (Chemoinformatics): Kiểm tra xem hai công thức phân tử hữu cơ mạch hở có cùng cấu trúc liên kết hóa học hay không (nhận diện các đồng phân cấu tạo).
Cơ sở dữ liệu đồ thị (Graph Databases): Đánh chỉ mục (Indexing) và phân nhóm các mẫu đồ thị con dạng cây để tăng tốc truy vấn tương đồng.

1. Định nghĩa toán học: Đẳng cấu cây có gốc và không gốc

Cho hai cây $T_1 = (V_1, E_1)$ và $T_2 = (V_2, E_2)$ có cùng số lượng đỉnh $\vert{}V_1\vert{} = \vert{}V_2\vert{} = N$ .

$T_1$ và $T_2$ được gọi là đẳng cấu (isomorphic) với nhau (ký hiệu $T_1 \simeq T_2$ ) nếu và chỉ nếu tồn tại một song ánh $f: V_1 \to V_2$ sao cho:

$\forall u, v \in V_1: \quad (u, v) \in E_1 \iff (f(u), f(v)) \in E_2$

Nói một cách trực quan: Hai cây là đẳng cấu nếu ta có thể vẽ lại, xoay các nhánh, hoặc đánh số lại các đỉnh của $T_1$ để thu được cấu trúc hoàn toàn trùng khít với $T_2$ .

Phân loại bài toán

Đẳng cấu cây có gốc (Rooted Tree Isomorphism): Gốc của $T_1$ ( $r_1$ ) và gốc của $T_2$ ( $r_2$ ) đã được cố định trước. Điều kiện bổ sung là $f(r_1) = r_2$ .
Đẳng cấu cây không gốc (Unrooted Tree Isomorphism): Không có đỉnh gốc nào được chỉ định trước. Các đỉnh có thể được nối theo bất kỳ thứ tự nào.

2. Quy bài toán cây không gốc về cây có gốc qua Trọng tâm (Centroid)

Để kiểm tra hai cây không gốc có đẳng cấu hay không, ta không thể thử chọn lần lượt từng cặp gốc bất kỳ vì sẽ tốn $O(N^2)$ . Thay vào đó, ta sử dụng tính chất bất biến cấu trúc của Trọng tâm cây (Centroid) đã nghiên cứu ở Bài 120:

Một cây bất kỳ chỉ có tối đa hai trọng tâm.
Trọng tâm được xác định thuần túy dựa trên cấu trúc phân bố kích thước của cây. Do đó, nếu hai cây $T_1$ và $T_2$ đẳng cấu, thì tập các trọng tâm của $T_1$ bắt buộc phải ánh xạ tương ứng vào tập các trọng tâm của $T_2$ .

Chiến lược giải quyết:

Tìm tập trọng tâm $C_1$ của $T_1$ và $C_2$ của $T_2$ .
Nếu $\vert{}C_1\vert{} \neq \vert{}C_2\vert{}$ , kết luận ngay: $T_1$ và $T_2$ không đẳng cấu.
Nếu $\vert{}C_1\vert{} = \vert{}C_2\vert{} = 1$ : Chọn trọng tâm duy nhất này làm gốc cho mỗi cây, sau đó chuyển về bài toán Đẳng cấu cây có gốc.
Nếu $\vert{}C_1\vert{} = \vert{}C_2\vert{} = 2$ : Giả sử $C_1 = \{c_{1a}, c_{1b}\}$ và $C_2 = \{c_{2a}, c_{2b}\}$ . Ta chỉ cần kiểm tra xem $T_1$ (chọn gốc $c_{1a}$ ) có đẳng cấu với $T_2$ (chọn gốc $c_{2a}$ hoặc $c_{2b}$ ) hay không.

3. Hai phương pháp nhận diện đẳng cấu cây có gốc

A. Thuật toán AHU (Aho-Hopcroft-Ullman) - Phương pháp tất định (Deterministic)

Thuật toán AHU mã hóa cấu trúc của từng cây con thành một chuỗi chính quy (canonical string representation) bằng các dấu ngoặc hoặc bit 0/1:

Mỗi nút lá biểu diễn bằng chuỗi "01".
Với mỗi nút cha $u$ , chuỗi mã hóa của $u$ được tạo thành bằng cách:
- Thu thập chuỗi mã hóa của tất cả các nút con của $u$ .
- Sắp xếp các chuỗi con này theo thứ tự từ điển (để triệt tiêu ảnh hưởng của thứ tự duyệt con).
- Ghép các chuỗi con lại với nhau và bọc bên ngoài bởi cặp ngoặc: Canonical(u) = "0" + Ghép(Sorted(Canonical(v))) + "1".
Hai cây có gốc đẳng cấu khi và chỉ khi chuỗi chính quy tại gốc của chúng giống hệt nhau.

Độ phức tạp: Có thể tối ưu về $O(N)$ bằng cách gán số nguyên định danh (Integer IDs) theo từng tầng thay vì thao tác trên chuỗi.

B. Phương pháp Tree Hashing (Băm cấu trúc cây) - Ngắn gọn và Hiệu năng cao

Trong thực tế lập trình hệ thống và thi đấu thuật toán, Tree Hashing được ưa chuộng hơn AHU vì cài đặt ngắn gọn, bộ nhớ cố định $O(N)$ và không cần sắp xếp chuỗi.

Mục tiêu là thiết kế một hàm băm $H(u)$ ánh xạ cấu trúc cây con gốc $u$ thành một số nguyên 64-bit (uint64) thỏa mãn hai điều kiện:

Tính chất giao hoán (Commutative / Order-independent): Giá trị băm của $u$ không phụ thuộc vào thứ tự duyệt các con của nó.
Kháng va chạm (Collision-resistant): Hai cây con có cấu trúc khác nhau phải có xác suất trùng mã băm gần bằng 0.

Một hàm băm cây chuẩn mực và an toàn thường sử dụng kỹ thuật ánh xạ giả ngẫu nhiên kết hợp phép cộng modulo hoặc hàm băm SplitMix64:

$H(u) = 1 + \sum_{v \in \text{children}(u)} f(H(v))$

Trong đó $f(x)$ là một hàm hoán vị phi tuyến (non-linear permutation function), ví dụ:

$f(x) = \text{SplitMix64}(x)$

Vì phép cộng có tính chất giao hoán ( $A + B = B + A$ ), thứ tự duyệt các con không làm thay đổi giá trị của $H(u)$ . Đồng thời, việc truyền giá trị qua $\text{SplitMix64}$ làm phân tán ngẫu nhiên các bit, triệt tiêu nguy cơ cộng dồn triệt tiêu hoặc va chạm.

4. Hiện thực hóa kiểm tra Đẳng cấu cây bằng Golang

Chương trình dưới đây cài đặt hoàn chỉnh việc kiểm tra hai cây không gốc có đẳng cấu hay không bằng cách kết hợp Tìm trọng tâm (Centroid) và Tree Hashing với SplitMix64:

package main

import (
	"fmt"
)

// Hàm hoán vị SplitMix64 để phân tán bit cho mã băm cây con
func splitmix64(x uint64) uint64 {
	x += 0x9e3779b97f4a7c15
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
	x = (x ^ (x >> 27)) * 0x94d049bb133111eb
	return x ^ (x >> 31)
}

type Tree struct {
	n   int
	adj [][]int
}

func NewTree(n int) *Tree {
	return &Tree{
		n:   n,
		adj: make([][]int, n),
	}
}

func (t *Tree) AddEdge(u, v int) {
	t.adj[u] = append(t.adj[u], v)
	t.adj[v] = append(t.adj[v], u)
}

// 1. Tìm tất cả trọng tâm của cây (tối đa 2 trọng tâm)
func (t *Tree) FindCentroids() []int {
	sz := make([]int, t.n)
	var centroids []int

	var getSizes func(u, p int)
	getSizes = func(u, p int) {
		sz[u] = 1
		for _, v := range t.adj[u] {
			if v != p {
				getSizes(v, u)
				sz[u] += sz[v]
			}
		}
	}
	getSizes(0, -1)

	var dfsCentroid func(u, p int)
	dfsCentroid = func(u, p int) {
		isCentroid := true
		for _, v := range t.adj[u] {
			if v != p {
				dfsCentroid(v, u)
				if sz[v] > t.n/2 {
					isCentroid = false
				}
			}
		}
		if t.n-sz[u] > t.n/2 {
			isCentroid = false
		}
		if isCentroid {
			centroids = append(centroids, u)
		}
	}
	dfsCentroid(0, -1)

	return centroids
}

// 2. Tính giá trị Tree Hash có gốc tại 'u'
func (t *Tree) GetRootedHash(u, p int) uint64 {
	var h uint64 = 1
	for _, v := range t.adj[u] {
		if v != p {
			childHash := t.GetRootedHash(v, u)
			h += splitmix64(childHash)
		}
	}
	return h
}

// 3. Kiểm tra xem hai cây không gốc có đẳng cấu hay không
func IsIsomorphic(t1, t2 *Tree) bool {
	if t1.n != t2.n {
		return false
	}

	c1 := t1.FindCentroids()
	c2 := t2.FindCentroids()

	// Số lượng trọng tâm phải bằng nhau (cùng là 1 hoặc cùng là 2)
	if len(c1) != len(c2) {
		return false
	}

	// Chọn c1[0] làm gốc cố định cho cây 1
	root1 := c1[0]
	hash1 := t1.GetRootedHash(root1, -1)

	// Thử ghép c1[0] với từng trọng tâm ứng viên của cây 2
	for _, root2 := range c2 {
		hash2 := t2.GetRootedHash(root2, -1)
		if hash1 == hash2 {
			return true
		}
	}

	return false
}

func main() {
	// Khởi tạo Cây 1 gồm 5 đỉnh (đỉnh 0 đến 4)
	// Cấu trúc: 0 nối 1, 1 nối 2, 1 nối 3, 3 nối 4
	t1 := NewTree(5)
	t1.AddEdge(0, 1)
	t1.AddEdge(1, 2)
	t1.AddEdge(1, 3)
	t1.AddEdge(3, 4)

	// Khởi tạo Cây 2 gồm 5 đỉnh (được đánh số và đảo lộn thứ tự các cạnh)
	// Cấu trúc tương đương: 4 nối 2, 2 nối 0, 2 nối 3, 3 nối 1
	t2 := NewTree(5)
	t2.AddEdge(4, 2)
	t2.AddEdge(2, 0)
	t2.AddEdge(2, 3)
	t2.AddEdge(3, 1)

	// Khởi tạo Cây 3 có cấu trúc khác biệt hoàn toàn (dạng hình sao)
	t3 := NewTree(5)
	t3.AddEdge(0, 1)
	t3.AddEdge(0, 2)
	t3.AddEdge(0, 3)
	t3.AddEdge(0, 4)

	fmt.Printf("Cây 1 và Cây 2 có đẳng cấu không? -> %t (Kỳ vọng: true)\n", IsIsomorphic(t1, t2))
	fmt.Printf("Cây 1 và Cây 3 có đẳng cấu không? -> %t (Kỳ vọng: false)\n", IsIsomorphic(t1, t3))
}

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

Thao tác	Độ phức tạp thời gian	Bộ nhớ bổ sung	Ghi chú
Tìm Trọng tâm (Centroids)	$O(N)$	$O(N)$	Duyệt DFS 2 lượt trên cây
Tính Tree Hash (Rooted Hash)	$O(N)$	$O(N)$	Mỗi đỉnh duyệt qua đúng 1 lần; $f(x)$ chạy trong $O(1)$
So khớp Đẳng cấu toàn phần	$O(N)$	$O(N)$	Thử tối đa 2 lần tính hash tương ứng 2 trọng tâm

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

Tối ưu hóa cây cú pháp trong Trình biên dịch (AST Deduplication): Khi phân tích mã nguồn, trình biên dịch có thể chuyển từng hàm hoặc khối lệnh thành cây cú pháp có gốc, tính giá trị Tree Hash cho từng cây con để phát hiện các đoạn code trùng lặp (duplication) hoặc tái sử dụng kết quả trung gian.
Định danh phân tử hóa học (Canonical SMILES Generation): Các cấu trúc phân tử vô hướng được chuẩn hóa bằng cách tìm trọng tâm đồ thị khung và áp dụng thuật toán AHU để sinh ra một chuỗi định danh duy nhất (Canonical ID), giúp tra cứu trong cơ sở dữ liệu hóa chất với thời gian $O(1)$ .
Bảo vệ toàn vẹn dữ liệu trong Blockchain & Git (Merkle Trees): Cấu trúc Merkle Tree bản chất là một dạng Tree Hashing có thứ tự, bảo đảm rằng nếu cấu trúc dữ liệu hoặc nội dung thay đổi ở bất kỳ nhánh nào, mã băm tại gốc sẽ thay đổi ngay lập tức.

cấu trúc dữ liệu