Mã Prüfer và đếm cây (công thức Cayley)
Mã Prüfer biểu diễn cây có nhãn n đỉnh bằng dãy độ dài n - 2, mã hoá và giải mã trong O(n). Từ đó suy ra công thức Cayley n^(n-2), đếm cây theo dãy bậc, rừng có gốc và số cách nối k thành phần thành cây.
Mã Prüfer (Prüfer code) là cách viết một cây có nhãn đỉnh (, đỉnh đánh số ) thành một dãy độ dài đúng gồm các số trong , sao cho giữa cây và dãy có song ánh. Hệ quả trực tiếp là công thức Cayley: có đúng cây có nhãn trên đỉnh. Mã hoá và giải mã làm được trong bằng một con trỏ chạy (thay vì nếu mỗi bước đi tìm lá nhỏ nhất, hay với heap). Từ mã Prüfer ta đếm được rất nhiều thứ: số cây có dãy bậc cho trước, số rừng có gốc, số cách nối thành phần liên thông thành một cây.
Ý tưởng / Trực giác
Định nghĩa (mã hoá). Lặp lại lần: chọn lá có nhãn nhỏ nhất, ghi lại nhãn đỉnh kề của nó (không ghi nhãn lá), rồi xoá lá đó khỏi cây. Sau bước còn lại đúng hai đỉnh nối với nhau bằng một cạnh, ta dừng.
Bậc bằng số lần xuất hiện cộng một. Mỗi lần một đỉnh được ghi vào dãy là lúc nó mất một cạnh (cạnh tới lá vừa xoá). Đỉnh chỉ bị xoá khi đã thành lá (còn đúng một cạnh), hoặc nằm trong hai đỉnh còn lại cuối cùng (cũng còn một cạnh). Vậy được ghi đúng lần:
Đặc biệt các lá chính là các nhãn không xuất hiện trong mã. Một hệ quả nhỏ hay dùng: đỉnh không bao giờ bị xoá (cây có ít nhất hai lá nên luôn có một lá nhỏ hơn ), vì vậy luôn nằm trong cạnh cuối cùng còn lại. Phần tử cuối của mã thì không nhất thiết là (ví dụ bên dưới cho với ).
Vì sao là song ánh (phác thảo). Quy nạp theo . Biết mã , ta biết bậc của mọi đỉnh, do đó biết tập lá ban đầu là các nhãn không có trong mã, và lá bị xoá đầu tiên là nhãn nhỏ nhất không có trong mã. Cạnh đầu tiên bắt buộc là . Bỏ đi, dãy chính là mã Prüfer của cây còn lại trên tập nhãn (định nghĩa chỉ dùng thứ tự các nhãn nên không cần nhãn liên tiếp). Theo quy nạp cây còn lại được khôi phục duy nhất, nên cả cây cũng vậy. Ngược lại, mọi dãy độ dài đều giải mã được thành một cây: ở mỗi bước luôn có ít nhất một đỉnh "đang là lá" (tổng bậc còn lại bằng số cạnh còn lại, mà số đỉnh nhiều hơn số cạnh), và thao tác giải mã đúng là đảo ngược thao tác mã hoá. Vậy
Giải mã. Tính bậc số lần xuất hiện . Với từng theo thứ tự: nối với lá nhỏ nhất hiện tại (đỉnh có chưa dùng), giảm đi một (nếu về thì thành lá mới). Cuối cùng còn đúng hai đỉnh có (một trong hai là ), nối chúng lại.
Mẹo : con trỏ chỉ tăng. Lá nhỏ nhất được chọn theo thứ tự tăng, trừ một trường hợp: khi xoá lá làm đỉnh kề thành lá mới và con trỏ hiện tại. Khi đó chắc chắn là lá nhỏ nhất (mọi lá cũ đều con trỏ), nên ta xử lý ngay mà không dời con trỏ. Nếu con trỏ thì con trỏ sẽ tự gặp nó sau. Con trỏ chỉ tiến từ tới , mỗi bước còn lại , tổng .
Ví dụ chạy tay
Cây đỉnh với các cạnh . Bậc ban đầu: cho đỉnh ; lá là . Bấm qua từng bước để xem quá trình mã hoá (đỏ là lá vừa xoá):
tree root=6 1 5 2 5 5 3 3 6 6 4 6 7 step Ban đầu: lá là 1, 2, 4, 7. Con trỏ ptr = 1 highlight green 1 2 4 7 step Xoá lá 1, ghi 5. deg(5) = 2, chưa thành lá; ptr tiến tới 2 highlight red 1 1-5 label 1 a1=5 step Xoá lá 2, ghi 5. deg(5) = 1 nhưng 5 > ptr = 2, để con trỏ tự gặp sau; ptr bỏ qua 3 (bậc 2), dừng ở 4 highlight red 2 2-5 label 2 a2=5 step Xoá lá 4, ghi 6. deg(6) = 2; ptr tiến tới 5, lúc này 5 đã là lá highlight red 4 6-4 label 4 a3=6 step Xoá lá 5, ghi 3. deg(3) = 1 và 3 < ptr = 5: 3 là lá nhỏ nhất, xoá ngay highlight red 5 5-3 label 5 a4=3 step Xoá lá 3, ghi 6. Đã đủ n - 2 = 5 số, còn lại cạnh 6-7 highlight red 3 3-6 label 3 a5=6 highlight orange 6 7 6-7
| bước | ptr | lá bị xoá | ghi | bậc sau bước của đỉnh kề |
|---|---|---|---|---|
| 1 | 1 | 1 | 5 | |
| 2 | 2 | 2 | 5 | , nhưng |
| 3 | 4 | 4 | 6 | |
| 4 | 5 | 5 | 3 | và : xử lý ngay |
| 5 | 5 | 3 | 6 | , |
Mã Prüfer: . Kiểm tra quy tắc bậc: xuất hiện lần nên ; xuất hiện lần nên ; xuất hiện lần nên ; các nhãn vắng mặt đúng là bốn lá.
Giải mã ngược . Bậc tính từ mã: , trùng với bậc ban đầu ở trên.
| đọc | lá nhỏ nhất | cạnh thêm | cập nhật |
|---|---|---|---|
| 5 | 1 | ; ptr tới 2 | |
| 5 | 2 | , ; ptr bỏ qua 3, tới 4 | |
| 6 | 4 | ; ptr tới 5 | |
| 3 | 5 | , : lá kế tiếp là 3 | |
| 6 | 3 | , ; ptr tới 6 | |
| hết | 6 | cạnh cuối nối lá còn lại với |
Ta thu lại đúng sáu cạnh ban đầu. Chương trình bên dưới với đầu vào này in code: 5 5 6 3 6 rồi sáu cạnh 1 5, 2 5, 4 6, 5 3, 3 6, 6 7.
Kiểm tra Cayley với : có mã. Mã có hai số khác nhau (ví dụ ) cho đường đi có lá, có mã như vậy; mã có hai số bằng nhau (ví dụ ) cho hình sao tâm có lá, có mã. Tổng .
Cài đặt
Chương trình đọc và cạnh, in mã Prüfer rồi giải mã lại và in các cạnh. Khi mã hoá ta treo cây ở gốc : đỉnh không bao giờ bị xoá, nên lá nào bị xoá cũng có đúng một đỉnh kề còn lại là cha của nó, không cần duyệt danh sách kề.
#include <bits/stdc++.h>
using namespace std;
// Encode a labeled tree (vertices 1..n, n >= 2) into its Prufer code in O(n).
// Idea: walk a pointer ptr upward over labels; whenever removing a leaf makes
// its neighbor a new leaf with a label smaller than ptr, remove it right away.
vector<int> prufer_encode(int n, const vector<pair<int,int>>& edges) {
vector<vector<int>> adj(n + 1);
for (auto [u, v] : edges) {
adj[u].push_back(v);
adj[v].push_back(u);
}
// Root the tree at n: n is never removed, so every removed leaf has a parent
vector<int> parent(n + 1, 0), deg(n + 1);
vector<int> st = {n};
parent[n] = -1;
while (!st.empty()) {
int u = st.back(); st.pop_back();
for (int v : adj[u])
if (v != parent[u]) { parent[v] = u; st.push_back(v); }
}
for (int v = 1; v <= n; v++) deg[v] = adj[v].size();
vector<int> code;
int ptr = 1;
while (deg[ptr] != 1) ptr++;
int leaf = ptr;
for (int i = 0; i < n - 2; i++) {
int p = parent[leaf]; // the only remaining neighbor of leaf
code.push_back(p);
if (--deg[p] == 1 && p < ptr) {
leaf = p; // new leaf smaller than ptr: it is the minimum now
} else {
ptr++;
while (deg[ptr] != 1) ptr++;
leaf = ptr;
}
}
return code;
}
// Decode a Prufer code of length n - 2 back into the n - 1 edges, O(n).
vector<pair<int,int>> prufer_decode(const vector<int>& code) {
int n = code.size() + 2;
vector<int> deg(n + 1, 1); // degree = occurrences + 1
for (int x : code) deg[x]++;
vector<pair<int,int>> edges;
int ptr = 1;
while (deg[ptr] != 1) ptr++;
int leaf = ptr;
for (int x : code) {
edges.push_back({leaf, x});
if (--deg[x] == 1 && x < ptr) {
leaf = x; // x just became the smallest leaf
} else {
ptr++;
while (deg[ptr] != 1) ptr++;
leaf = ptr;
}
}
edges.push_back({leaf, n}); // the last two vertices are leaf and n
return edges;
}
int main() {
int n;
cin >> n;
vector<pair<int,int>> edges(n - 1);
for (auto& [u, v] : edges) cin >> u >> v;
vector<int> code = prufer_encode(n, edges);
cout << "code:";
for (int x : code) cout << ' ' << x;
cout << '\n';
for (auto [u, v] : prufer_decode(code)) cout << u << ' ' << v << '\n';
}
import sys
def prufer_encode(n, edges):
"""Prufer code of a labeled tree on 1..n (n >= 2), O(n)."""
adj = [[] for _ in range(n + 1)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
# Root at n so that every removed leaf has a parent
parent = [0] * (n + 1)
parent[n] = -1
stack = [n]
while stack:
u = stack.pop()
for v in adj[u]:
if v != parent[u]:
parent[v] = u
stack.append(v)
deg = [len(a) for a in adj]
code = []
ptr = 1
while deg[ptr] != 1:
ptr += 1
leaf = ptr
for _ in range(n - 2):
p = parent[leaf]
code.append(p)
deg[p] -= 1
if deg[p] == 1 and p < ptr:
leaf = p # new leaf smaller than ptr
else:
ptr += 1
while deg[ptr] != 1:
ptr += 1
leaf = ptr
return code
def prufer_decode(code):
"""Edges of the tree whose Prufer code is <!--LCODE7-->, O(n)."""
n = len(code) + 2
deg = [1] * (n + 1) # degree = occurrences + 1
for x in code:
deg[x] += 1
edges = []
ptr = 1
while deg[ptr] != 1:
ptr += 1
leaf = ptr
for x in code:
edges.append((leaf, x))
deg[x] -= 1
if deg[x] == 1 and x < ptr:
leaf = x
else:
ptr += 1
while deg[ptr] != 1:
ptr += 1
leaf = ptr
edges.append((leaf, n))
return edges
def main():
data = list(map(int, sys.stdin.read().split()))
n = data[0]
edges = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n - 1)]
code = prufer_encode(n, edges)
print("code:", *code)
for u, v in prufer_decode(code):
print(u, v)
main()
Phiên bản heap . Dễ viết hơn, đúng theo định nghĩa: đưa mọi lá vào min-heap, mỗi bước lấy lá nhỏ nhất. Hữu ích khi biến thể của bài đổi thứ tự chọn lá (ví dụ chọn theo một khoá khác nhãn), lúc đó mẹo con trỏ không còn áp dụng.
#include <bits/stdc++.h>
using namespace std;
// O(n log n) version: keep all current leaves in a min-heap.
vector<int> prufer_encode_heap(int n, const vector<pair<int,int>>& edges) {
vector<set<int>> adj(n + 1);
for (auto [u, v] : edges) { adj[u].insert(v); adj[v].insert(u); }
priority_queue<int, vector<int>, greater<int>> leaves;
for (int v = 1; v <= n; v++)
if (adj[v].size() == 1) leaves.push(v);
vector<int> code;
for (int i = 0; i < n - 2; i++) {
int leaf = leaves.top(); leaves.pop();
int p = *adj[leaf].begin(); // its only neighbor
code.push_back(p);
adj[p].erase(leaf);
if (adj[p].size() == 1) leaves.push(p);
}
return code;
}
vector<pair<int,int>> prufer_decode_heap(const vector<int>& code) {
int n = code.size() + 2;
vector<int> deg(n + 1, 1);
for (int x : code) deg[x]++;
priority_queue<int, vector<int>, greater<int>> leaves;
for (int v = 1; v <= n; v++)
if (deg[v] == 1) leaves.push(v);
vector<pair<int,int>> edges;
for (int x : code) {
int leaf = leaves.top(); leaves.pop();
edges.push_back({leaf, x});
if (--deg[x] == 1) leaves.push(x);
}
int u = leaves.top(); leaves.pop(); // exactly two vertices remain
int v = leaves.top();
edges.push_back({u, v});
return edges;
}
int main() {
int n;
cin >> n;
vector<pair<int,int>> edges(n - 1);
for (auto& [u, v] : edges) cin >> u >> v;
vector<int> code = prufer_encode_heap(n, edges);
cout << "code:";
for (int x : code) cout << ' ' << x;
cout << '\n';
for (auto [u, v] : prufer_decode_heap(code)) cout << u << ' ' << v << '\n';
}
import heapq
import sys
def prufer_encode_heap(n, edges):
"""O(n log n): pop the smallest leaf from a min-heap."""
adj = [set() for _ in range(n + 1)]
for u, v in edges:
adj[u].add(v)
adj[v].add(u)
leaves = [v for v in range(1, n + 1) if len(adj[v]) == 1]
heapq.heapify(leaves)
code = []
for _ in range(n - 2):
leaf = heapq.heappop(leaves)
p = next(iter(adj[leaf])) # its only neighbor
code.append(p)
adj[p].discard(leaf)
if len(adj[p]) == 1:
heapq.heappush(leaves, p)
return code
def prufer_decode_heap(code):
n = len(code) + 2
deg = [1] * (n + 1)
for x in code:
deg[x] += 1
leaves = [v for v in range(1, n + 1) if deg[v] == 1]
heapq.heapify(leaves)
edges = []
for x in code:
leaf = heapq.heappop(leaves)
edges.append((leaf, x))
deg[x] -= 1
if deg[x] == 1:
heapq.heappush(leaves, x)
u = heapq.heappop(leaves) # exactly two vertices remain
v = heapq.heappop(leaves)
edges.append((u, v))
return edges
def main():
data = list(map(int, sys.stdin.read().split()))
n = data[0]
edges = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n - 1)]
code = prufer_encode_heap(n, edges)
print("code:", *code)
for u, v in prufer_decode_heap(code):
print(u, v)
main()
Các công thức đếm từ mã Prüfer
Mọi công thức dưới đây đã được kiểm tra bằng duyệt toàn bộ tập cạnh với .
1. Công thức Cayley. Số cây có nhãn đỉnh là (với quy ước là ). Số cây có gốc có nhãn là (chọn thêm gốc).
2. Cây có dãy bậc cho trước. Với và , cây có ứng với mã Prüfer chứa đúng lần nhãn . Đếm số cách xếp dãy có lặp (hệ số đa thức):
Nếu có hoặc tổng khác thì đáp án là . Ví dụ , bậc : cây. Hệ quả: số cây mà đỉnh có bậc đúng là (chọn vị trí cho nhãn , các vị trí khác nhận nhãn còn lại).
3. Rừng có gốc cho trước. Số rừng trên đỉnh có nhãn gồm đúng cây, trong đó các đỉnh nằm ở cây khác nhau (mỗi cây chứa đúng một trong chúng, coi là gốc):
Phác thảo: mã hoá kiểu Prüfer nhưng chỉ xoá lá nhỏ nhất không phải gốc, ghi đỉnh kề. Sau bước chỉ còn các gốc, ta được dãy độ dài ; phần tử đầu tuỳ ý trong , phần tử cuối là đỉnh kề của đỉnh cuối cùng bị xoá nên phải là một gốc, có lựa chọn. Ví dụ , : rừng. Với ta có lại Cayley: .
4. Nối thành phần thành một cây. Đồ thị đỉnh đã có sẵn thành phần liên thông kích thước . Số cách thêm đúng cạnh (nối các thành phần khác nhau) để đồ thị liên thông:
Phác thảo: co mỗi thành phần thành một siêu đỉnh. Các cạnh thêm vào tạo thành một cây trên siêu đỉnh; nếu siêu đỉnh có bậc thì mỗi cạnh chạm vào nó được chọn đầu mút trong đỉnh, cho cách. Lấy tổng theo công thức 2 trên siêu đỉnh:
với và bước cuối là định lý đa thức (multinomial). Vì nên ra . Ví dụ , ba thành phần kích thước : cách. Khi mọi () công thức lại là Cayley.
5. Liên hệ định lý ma trận cây Kirchhoff. Số cây khung của một đồ thị bất kỳ bằng định thức của ma trận Laplace sau khi bỏ một hàng và cột cùng chỉ số, tính bằng khử Gauss trong . Với đồ thị đầy đủ , ma trận con là cỡ (với toàn số ), có trị riêng (bội ) và , nên định thức bằng : một chứng minh khác của Cayley. Quy tắc chung: đồ thị đầy đủ hoặc có cấu trúc "mọi đỉnh nối với nhau" thì dùng Prüfer cho công thức đóng hoặc ; đồ thị tuỳ ý thì phải dùng Kirchhoff. Công thức 4 chính là số cây khung của đồ thị "đầy đủ giữa các thành phần" sau khi co mỗi thành phần.
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Mã hoá / giải mã bằng con trỏ | ||
| Mã hoá / giải mã bằng heap | ||
| Cayley, rừng có gốc, nối thành phần (modulo ) | lũy thừa nhanh, cho tích | |
| Cây có dãy bậc cho trước | sau khi có bảng giai thừa | |
| Kirchhoff trên đồ thị tuỳ ý |
Vì sao mẹo con trỏ là ? Con trỏ ptr chỉ tăng, tổng số lần tăng không quá . Mỗi bước trong bước làm thêm việc: giảm một bậc và có thể "nhảy" sang đỉnh kề vừa thành lá. Lần nhảy này không cần tìm kiếm vì đỉnh kề nhỏ hơn ptr chắc chắn là lá nhỏ nhất. Bản heap chậm hơn một thừa số do mỗi lá được đẩy và lấy ra khỏi heap đúng một lần. Bộ nhớ là danh sách kề hoặc mảng bậc, .
⚠️ Lỗi thường gặp
- Ghi nhãn lá thay vì đỉnh kề: mã Prüfer ghi đỉnh kề của lá bị xoá. Ghi nhãn lá cho một dãy khác (không còn tính chất "bậc = số lần xuất hiện ") và giải mã sai hoàn toàn. Kiểm tra nhanh: các lá của cây phải không xuất hiện trong mã.
- Sai độ dài mã: mã có phần tử, không phải . Nếu ghi tiếp bước thứ thì phần tử thêm vào luôn là (thông tin thừa). Trường hợp biên : mã rỗng, cây là cạnh ; : không có mã, quy ước cây. Code phải chạy được với mã rỗng.
- Không chọn lá nhỏ nhất: chọn lá bất kỳ (ví dụ lá đầu tiên tìm thấy trong DFS) vẫn tạo ra một dãy độ dài , nhưng ánh xạ không còn là song ánh nên giải mã không khôi phục được cây. Thứ tự chọn ở bước mã hoá và giải mã phải khớp nhau.
- Quên nhánh
p < ptrtrong bản : nếu luôn dời con trỏ, đỉnh vừa thành lá có nhãn nhỏ hơn con trỏ sẽ bị bỏ qua vĩnh viễn và vòngwhile (deg[ptr] != 1)chạy quá (truy cập ngoài mảng). Ngược lại, nếu "nhảy" cả khi ptr thì sẽ xoá trước các lá nhỏ hơn nó đang chờ. Ví dụ trên kiểm tra được cả hai nhánh (bước 2 và bước 4). - Công thức với hoặc : với là , và với là . Lũy thừa nhanh với số mũ âm sẽ treo hoặc sai; xử lý riêng (đáp án đều là ).
- Tràn số và modulo: vượt
long longtừ . Luôn tính modulo bằng lũy thừa nhanh, nhânlong longrồi lấy dư. Với công thức dãy bậc, mẫu số cần nghịch đảo modulo nên modulo phải nguyên tố và lớn hơn . - Nhầm cây có nhãn và cây không nhãn: đếm cây có nhãn (hai cây khác nhau nếu khác tập cạnh). Số cây không nhãn (không phân biệt đẳng cấu) không có công thức đóng, xem Đẳng cấu cây. Tương tự, cây có gốc có nhãn là , đừng dùng .
Biến thể / Mở rộng
- Đếm cây theo số lá: lá là các nhãn vắng mặt, nên số cây có đúng lá là , tính bằng số Stirling loại hai hoặc bao hàm loại trừ, xem Tổ hợp và Bao hàm loại trừ.
- Cây có trọng số trên cạnh, ràng buộc trên một đường đi: cố định đường đi giữa hai đỉnh gồm đỉnh trung gian, phần còn lại là một rừng có gốc cố định, dùng công thức 3.
- Hàm sinh: đa thức gói gọn công thức 2; các bài đếm theo trọng số đỉnh thường đi qua hàm sinh.
- Đồ thị hàm: số hàm là ; số "cây có gốc trỏ về gốc" trên đỉnh là , xem Đồ thị hàm.
- Cây khung trên đồ thị tuỳ ý: dùng định lý Kirchhoff với khử Gauss modulo; cây khung nhỏ nhất thì xem Cây khung nhỏ nhất.
Bài tập luyện
- Thiết kế hệ thống đèn (dhbb22_lisys): (Khó) Đếm số cách điền các bậc bị khuyết để được dãy bậc của một cây. Mã Prüfer chứng minh điều kiện "mọi , tổng " là đủ, phần còn lại là chia kẹo.
- Đếm cây gán nhãn (vtc14_treecnt): (Rất khó) Đếm số cây có nhãn đỉnh có đúng lá. Lá là nhãn vắng mặt trong mã, quy về đếm dãy độ dài dùng đúng nhãn (số Stirling loại hai).
- Dây đèn tự chế (garland): (Rất khó) Khôi phục cây có gốc từ dãy "bóng chính" ghi theo độ quan trọng giảm dần. Đây là giải mã kiểu Prüfer đọc ngược dãy, ghép mỗi phần tử với lá nhỏ nhất trong heap.
- Cây Đẹp (beautree): (Chuyên gia) Đếm cây có trọng số mà khoảng cách giữa và bằng đúng . Cố định số cạnh trên đường - (đường có đỉnh), phần còn lại là rừng có gốc cố định đếm bằng (công thức 3), kết hợp chia kẹo cho trọng số.
Bình luận