Chuỗi Prüfer

Trong toán tổ hợp, chuỗi Prüfer (hay mã Prüfer) của một cây được gán nhãn là một chuỗi duy nhất có biểu diễn cây đó. Chuỗi Prüfer của một cây n đỉnh có độ dài n − 2 và có thể tạo ra bằng một thuật toán lặp đơn giản. Chuỗi Prüfer được Heinz Prüfer lần đầu tiên sử dụng để chứng minh công thức Cayley năm 1918.^[1]

Thuật toán chuyển đổi cây thành chuỗi Prüfer

Có thể sinh chuỗi Prüfer bằng cách lần lượt xóa các đỉnh đến khi cây chỉ còn lại hai đỉnh. Xét trường hợp cây T được gán nhãn {1, 2,..., n}. Tại bước thứ i, ta xóa nút lá có nhãn nhỏ nhất và chèn nhãn của phần tử kề của lá đó vào chuỗi Prüfer.

Chuỗi tạo thành hiển nhiên duy nhất và có độ dài n − 2.

Ví dụ

Cây với mã Prüfer 4445.

Ta quan sát thuật toán trên hoạt động với ví dụ trong hình bên phải. Thoạt tiên, đỉnh 1 là có nhãn nhỏ nhất, nó bị xóa và "4" được thêm vào chuỗi Prüfer. Đỉnh 2 và 3 bị xóa sau đó và "4" được thêm vào hai lần nữa. Đến lúc này, đỉnh 4 trở thành là và có nhãn nhỏ nhất nên nó bị xóa và ta thêm "5" vào chuỗi. Lúc này cây chỉ còn hai đỉnh, thuật toán kết thúc. Chuỗi kết quả là 4445.

Thuật toán tạo cây từ chuỗi Prüfer

Xét chuỗi Prüfer {a[1], a[2],..., a[n]}:

Cây cần dựng sẽ có n+2 nút, đánh số từ 1 đến n+2. Với mỗi nút, gán bậc của nó bằng số lần nó xuất hiện trong chuỗi cộng 1. Chẳng hạn, dùng giả mã:

 Convert-Prüfer-to-Tree(a)
 1 n ← length[a]
 2 T ← tree with nodes 1 to n + 2
 3 for each node i in T
 4     do degree[i] ← 1
 5 for each value i in a
 6     do degree[i] ← degree[i] + 1

Sau đó, với mỗi số trong chuỗi a[i], tìm được nút đầu tiên (được đánh số nhỏ nhất) j có bậc bằng 1, thêm cạnh (j, a[i]) vào cây, giảm bậc của j và a[i]. Giả mã:

 7 for each value i in a
 8     for each node j in T
 9         if degree[j] = 1
10             then Insert edge[i, j] into T
11                  degree[i] ← degree[i] - 1
12                  degree[j] ← degree[j] - 1
13                  break

Sau khi kết thúc vòng lặp, còn lại hai nút với bậc 1 (gọi là u, v). Cuối cùng, ta thêm cạnh (u,v) vào cây.^[2]

14 u ← v ← 0
15 for each node i in T
16     if degree[i] = 1
17         then if u = 0
18             then u ← i
19             else v ← i
20                  break
21 Insert edge[u, v] into T
22 degree[u] ← degree[u] - 1
23 degree[v] ← degree[v] - 1
24 return T

Công thức Cayley

Chuỗi Prüfer của cây n đỉnh được gán nhãn là duy nhất và có độ dài n − 2 với các số từ 1 đến n và ngược lại, với mỗi chuỗi như thế xác định một cây n đỉnh được gán nhãn..

Vậy, chuỗi Prüfer cho ta một song ánh giữa tập các cây n đỉnh được đánh gán nhãn và tập các chuỗi độ dài n–2 với các số từ 1 đến n. Tập thứ hai có lực lượng nⁿ⁻², nên do tính chất của song ánh, công thức Cayley được chứng minh, nghĩa là:

có nⁿ⁻² cây gán nhãn có n đỉnh.

Các ứng dụng khác

• Có thể làm mạnh công thức Cayley để chứng minh những mệnh đề sau:

Số cây khung của một đồ thị đầy đủ ${\displaystyle K_{n}}$ với các bậc ${\displaystyle d_{1},d_{2},...,d_{n}}$ bằng

${\displaystyle {\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots (d_{n}-1)!}}.}$

Lưu ý rằng trong chuỗi Prüfer, số ${\displaystyle i}$ xuất hiện đúng ${\displaystyle (d_{i}-1)}$ lần.

• Tổng quát hóa công thức Cayley: cây gán nhãn thực chất là cây khung của một đồ thị đầy đủ được gán nhãn. Bằng cách hạn chế bớt chuỗi Prüfer, phương pháp tương tự có thể được dùng để đến số cây khung của đồ thị hai phía đầy đủ. Cho G là một đồ thị hai phía đầy đủ với các đỉnh từ 1 đến n₁ ở một phía còn các đỉnh từ n₁ + 1 đến n về phía còn lại, số cây khung của G là ${\displaystyle n_{1}^{n_{2}-1}n_{2}^{n_{1}-1}}$, trong đó n₂ = n − n₁.

Tham khảo

1. Prüfer, H. (1918). “Neuer Beweis eines Satzes über Permutationen”. Arch. Math. Phys. 27: 742–744.
2. Jens Gottlieb, Bryant A. Julstrom, Günther R. Raidl, and Franz Rothlauf. (2001). “Prüfer numbers: A poor representation of spanning trees for evolutionary search” (PDF). Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001): 343–350. Bản gốc (PDF) lưu trữ ngày 26 tháng 9 năm 2006. Truy cập ngày 17 tháng 2 năm 2010.

Liên kết ngoài

• Prüfer code – trên MathWorld