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.

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] = 110             then Insert edge[i, j] into T11                  degree[i] ← degree[i] - 112                  degree[j] ← degree[j] - 113                  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 ← 015 for each node i in T16     if degree[i] = 117         then if u = 018             then u ← i19             else v ← i20                  break21 Insert edge[u, v] into T22 degree[u] ← degree[u] - 123 degree[v] ← degree[v] - 124 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 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ó 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₁.

• Prüfer code – trên MathWorld