Wiki › Thuật toán › Toán học › Mã Prüfer và đếm cây (công thức Cayley)

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.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 21 phút 3 lượt xem

Mã Prüfer (Prüfer code) là cách viết một cây có nhãn n đỉnh (n≥2, đỉnh đánh số 1..n) thành một dãy độ dài đúng n−2 gồm các số trong [1,n], 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 nn−2 cây có nhãn trên n đỉnh. Mã hoá và giải mã làm được trong O(n) bằng một con trỏ chạy (thay vì O(n2) nếu mỗi bước đi tìm lá nhỏ nhất, hay O(nlogn) 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 k 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 n−2 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 n−2 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 v đượ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 v 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 v được ghi đúng deg(v)−1 lần:

deg(v)=(số lần v xuất hiện trong mã)+1.

Đặ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 n 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 n), vì vậy n 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à n (ví dụ bên dưới cho 6 với n=7).

Vì sao là song ánh (phác thảo). Quy nạp theo n. Biết mã (a1,…,an−2), 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à ℓ1= nhãn nhỏ nhất không có trong mã. Cạnh đầu tiên bắt buộc là (ℓ1,a1). Bỏ ℓ1 đi, dãy (a2,…,an−2) chính là mã Prüfer của cây còn lại trên tập nhãn {1..n}⧵{ℓ1} (đị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 n−2 đề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 2× 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

#{cây có nhãn n đỉnh}=#{dãy [1,n]n−2}=nn−2.

Giải mã. Tính bậc deg(v)= số lần xuất hiện +1. Với từng ai theo thứ tự: nối ai với lá nhỏ nhất hiện tại (đỉnh có deg=1 chưa dùng), giảm deg(ai) đi một (nếu về 1 thì ai thành lá mới). Cuối cùng còn đúng hai đỉnh có deg=1 (một trong hai là n), nối chúng lại.

Mẹo O(n): 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ề p thành lá mới và p< con trỏ hiện tại. Khi đó p chắc chắn là lá nhỏ nhất (mọi lá cũ đều ≥ con trỏ), nên ta xử lý p ngay mà không dời con trỏ. Nếu p> con trỏ thì con trỏ sẽ tự gặp nó sau. Con trỏ chỉ tiến từ 1 tới n, mỗi bước còn lại O(1), tổng O(n).

Ví dụ chạy tay

Cây 7 đỉnh với các cạnh 1-5, 2-5, 5-3, 3-6, 6-4, 6-7. Bậc ban đầu: deg=(1,1,2,1,3,3,1) cho đỉnh 1..7; lá là 1,2,4,7. 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 deg(5)=2
2 2 2 5 deg(5)=1, nhưng 5>2
3 4 4 6 deg(6)=2
4 5 5 3 deg(3)=1 và 3<5: xử lý ngay
5 5 3 6 deg(6)=1, 6>5

Mã Prüfer: (5,5,6,3,6). Kiểm tra quy tắc bậc: 5 xuất hiện 2 lần nên deg(5)=3; 6 xuất hiện 2 lần nên deg(6)=3; 3 xuất hiện 1 lần nên deg(3)=2; các nhãn 1,2,4,7 vắng mặt đúng là bốn lá.

Giải mã ngược (5,5,6,3,6). Bậc tính từ mã: (1,1,2,1,3,3,1), trùng với bậc ban đầu ở trên.

đọc ai lá nhỏ nhất cạnh thêm cập nhật
5 1 (1,5) deg(5)=2; ptr tới 2
5 2 (2,5) deg(5)=1, 5>2; ptr bỏ qua 3, tới 4
6 4 (4,6) deg(6)=2; ptr tới 5
3 5 (5,3) deg(3)=1, 3<5: lá kế tiếp là 3
6 3 (3,6) deg(6)=1, 6>5; ptr tới 6
hết 6 (6,7) cạnh cuối nối lá còn lại với n=7

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 n=4: có 42=16 mã. Mã có hai số khác nhau (ví dụ (2,3)) cho đường đi có 2 lá, có 4·3=12 mã như vậy; mã có hai số bằng nhau (ví dụ (2,2)) cho hình sao tâm 2 có 3 lá, có 4 mã. Tổng 12+4=16.

Cài đặt

Chương trình đọc n và n−1 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 n: đỉnh n 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ề.

C++
#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';
}
Python
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 O(nlogn). 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.

C++
#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';
}
Python
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 n≤6.

1. Công thức Cayley. Số cây có nhãn n đỉnh là nn−2 (với n=1 quy ước là 1). Số cây có gốc có nhãn là n·nn−2=nn−1 (chọn thêm gốc).

2. Cây có dãy bậc cho trước. Với d1,…,dn≥1 và ∑di=2n−2, cây có deg(i)=di ứng với mã Prüfer chứa đúng di−1 lần nhãn i. Đếm số cách xếp dãy có lặp (hệ số đa thức):

#{cây với bậc d1,…,dn}=(n−2)!(d1−1)!(d2−1)!⋯(dn−1)!.

Nếu có di=0 hoặc tổng khác 2n−2 thì đáp án là 0. Ví dụ n=6, bậc (3,2,1,1,1,2): 4!2!1!0!0!0!1!=12 cây. Hệ quả: số cây mà đỉnh 1 có bậc đúng d là (n−2d−1)(n−1)n−1−d (chọn d−1 vị trí cho nhãn 1, các vị trí khác nhận n−1 nhãn còn lại).

3. Rừng có gốc cho trước. Số rừng trên n đỉnh có nhãn gồm đúng k cây, trong đó các đỉnh 1,2,…,k nằm ở k cây khác nhau (mỗi cây chứa đúng một trong chúng, coi là gốc):

F(n,k)=k·nn−k−1(1≤k<n),F(n,n)=1.

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 n−k bước chỉ còn các gốc, ta được dãy độ dài n−k; n−k−1 phần tử đầu tuỳ ý trong [1,n], 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ó k lựa chọn. Ví dụ n=4, k=2: 2·41=8 rừng. Với k=1 ta có lại Cayley: 1·nn−2.

4. Nối k thành phần thành một cây. Đồ thị n đỉnh đã có sẵn k thành phần liên thông kích thước s1,…,sk. Số cách thêm đúng k−1 cạnh (nối các thành phần khác nhau) để đồ thị liên thông:

T=nk−2∏i=1ksi(k≥2),T=1 khi k=1.

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 k siêu đỉnh; nếu siêu đỉnh i có bậc di thì mỗi cạnh chạm vào nó được chọn đầu mút trong si đỉnh, cho sidi cách. Lấy tổng theo công thức 2 trên k siêu đỉnh:

T=∑d(k−2)!∏(di−1)!∏sidi=∏si·∑e1+⋯+ek=k−2(k−2)!∏ei!∏siei=∏si·(s1+⋯+sk)k−2,

với ei=di−1 và bước cuối là định lý đa thức (multinomial). Vì ∑si=n nên ra nk−2∏si. Ví dụ n=5, ba thành phần kích thước 2,2,1: 51·2·2·1=20 cách. Khi mọi si=1 (k=n) 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 L=D−A sau khi bỏ một hàng và cột cùng chỉ số, tính bằng khử Gauss trong O(n3). Với đồ thị đầy đủ Kn, ma trận con là nI−J cỡ n−1 (với J toàn số 1), có trị riêng n (bội n−2) và 1, nên định thức bằng nn−2: 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 O(n) hoặc O(logn); đồ 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ỏ O(n) O(n)
Mã hoá / giải mã bằng heap O(nlogn) O(n)
Cayley, rừng có gốc, nối thành phần (modulo p) O(logn) lũy thừa nhanh, O(k) cho tích si O(1)
Cây có dãy bậc cho trước O(n) sau khi có bảng giai thừa O(n)
Kirchhoff trên đồ thị tuỳ ý O(n3) O(n2)

Vì sao mẹo con trỏ là O(n)? Con trỏ ptr chỉ tăng, tổng số lần tăng không quá n. Mỗi bước trong n−2 bước làm thêm O(1) 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ố logn 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, O(n).

⚠️ 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 +1") 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ó n−2 phần tử, không phải n−1. Nếu ghi tiếp bước thứ n−1 thì phần tử thêm vào luôn là n (thông tin thừa). Trường hợp biên n=2: mã rỗng, cây là cạnh (1,2); n=1: không có mã, quy ước 1 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 n−2, 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 < ptr trong bản O(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òng while (deg[ptr] != 1) chạy quá n (truy cập ngoài mảng). Ngược lại, nếu "nhảy" cả khi p> ptr thì sẽ xoá p 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 k=1 hoặc k=n: nk−2 với k=1 là n−1, và nn−k−1 với k=n là n−1. Lũy thừa nhanh với số mũ âm sẽ treo hoặc sai; xử lý riêng (đáp án đều là 1).
  • Tràn số và modulo: nn−2 vượt long long từ n≈17. Luôn tính modulo bằng lũy thừa nhanh, nhân long long rồi lấy dư. Với công thức dãy bậc, mẫu số ∏(di−1)! cần nghịch đảo modulo nên modulo phải nguyên tố và lớn hơn n.
  • Nhầm cây có nhãn và cây không nhãn: nn−2 đế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à nn−1, đừng dùng nn−2.

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 k lá là (nk)·(số toàn ánh từ n−2 vị trí lên n−k nhãn), 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 a,b gồm k đỉnh trung gian, phần còn lại là một rừng có k+2 gốc cố định, dùng công thức 3.
  • Hàm sinh: đa thức ∑T∏vxvdeg(v)=x1⋯xn(x1+⋯+xn)n−2 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 f:[1,n]→[1,n] là nn; số "cây có gốc trỏ về gốc" trên n đỉnh là nn−1, 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 di≥1, tổng 2n−2" 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 n đỉnh có đúng k lá. Lá là nhãn vắng mặt trong mã, quy về đếm dãy độ dài n−2 dùng đúng n−k 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 a và b bằng đúng m. Cố định số cạnh k trên đường a-b (đường có k+1 đỉnh), phần còn lại là rừng có gốc cố định đếm bằng (k+1)·nn−k−2 (công thức 3), kết hợp chia kẹo cho trọng số.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0