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]
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.
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.
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
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 nn−2, nên do tính chất của song ánh, công thức Cayley được chứng minh, nghĩa là:
có nn−2 cây gán nhãn có n đỉnh.