Bước tới nội dung

Chuỗi Prüfer

Bách khoa toàn thư mở Wikipedia

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

[sửa | sửa mã nguồn]

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.

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

[sửa | sửa mã nguồn]

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 nlength[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 uv ← 0
15 for each node i in T
16     if degree[i] = 1
17         then if u = 0
18             then ui
19             else vi
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

[sửa | sửa mã nguồn]

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à:

nn−2 cây gán nhãn có n đỉnh.

Các ứng dụng khác

[sửa | sửa mã nguồn]
  • 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 đủ với các bậc bằng
Lưu ý rằng trong chuỗi Prüfer, số xuất hiện đúng 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 n1 ở một phía còn các đỉnh từ n1   1 đến n về phía còn lại, số cây khung của G, trong đó n2 = n − n1.

Tham khảo

[sửa | sửa mã nguồn]
  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.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)

Liên kết ngoài

[sửa | sửa mã nguồn]