跳转至

Prüfer 序列

Note

本文翻譯自 e-maxx Prüfer Code。另外解釋一下，原文的結點是從 \(0\) 開始標號的，本文按照大多數人的習慣改成了從 \(1\) 標號。

這篇文章介紹 Prüfer 序列 (Prüfer code)，這是一種將帶標號的樹用一個唯一的整數序列表示的方法。

使用 Prüfer 序列可以證明 凱萊公式(Cayley's formula)。並且我們也會講解如何計算在一個圖中加邊使圖連通的方案數。

注意：我們不考慮含有 \(1\) 個結點的樹。

Prüfer 序列

引入

Prüfer 序列可以將一個帶標號 \(n\) 個結點的樹用 \([1,n]\) 中的 \(n-2\) 個整數表示。你也可以把它理解為完全圖的生成樹與數列之間的雙射。常用組合計數問題中。

Heinz Prüfer 於 1918 年發明這個序列來證明 凱萊公式。

對樹建立 Prüfer 序列

Prüfer 是這樣建立的：每次選擇一個編號最小的葉結點並刪掉它，然後在序列中記錄下它連接到的那個結點。重複 \(n-2\) 次後就只剩下兩個結點，算法結束。

顯然使用堆可以做到 \(O(n\log n)\) 的複雜度

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 代碼摘自原文，結點是從 0 標號的
vector<vector<int>> adj;

vector<int> pruefer_code() {
  int n = adj.size();
  set<int> leafs;
  vector<int> degree(n);
  vector<bool> killed(n, false);
  for (int i = 0; i < n; i++) {
    degree[i] = adj[i].size();
    if (degree[i] == 1) leafs.insert(i);
  }

  vector<int> code(n - 2);
  for (int i = 0; i < n - 2; i++) {
    int leaf = *leafs.begin();
    leafs.erase(leafs.begin());
    killed[leaf] = true;
    int v;
    for (int u : adj[leaf])
      if (!killed[u]) v = u;
    code[i] = v;
    if (--degree[v] == 1) leafs.insert(v);
  }
  return code;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 結點是從 0 標號的
adj = [[]]

def pruefer_code():
    n = len(adj)
    leafs = set()
    degree = [0] * n
    killed = [False] * n
    for i in range(1, n):
        degree[i] = len(adj[i])
        if degree[i] == 1:
            leafs.intersection(i)
    code = [0] * (n - 2)
    for i in range(1, n - 2):
        leaf = leafs[0]
        leafs.pop()
        killed[leaf] = True
        for u in adj[leaf]:
            if killed[u] == False:
                v = u
        code[i] = v
        if degree[v] == 1:
            degree[v] = degree[v] - 1
            leafs.intersection(v)
    return code

例如，這是一棵 7 個結點的樹的 Prüfer 序列構建過程：

Prüfer

最終的序列就是 \(2,2,3,3,2\)。

當然，也有一個線性的構造算法。

Prüfer 序列的線性構造算法

線性構造的本質就是維護一個指針指向我們將要刪除的結點。首先發現，葉結點數是非嚴格單調遞減的，刪去一個葉結點，葉結點總數要麼不變要麼減 1。

於是我們考慮這樣一個過程：維護一個指針 \(p\)。初始時 \(p\) 指向編號最小的葉結點。同時我們維護每個結點的度數，方便我們知道在刪除結點的時侯是否產生新的葉結點。操作如下：

  1. 刪除 \(p\) 指向的結點，並檢查是否產生新的葉結點。
  2. 如果產生新的葉結點，假設編號為 \(x\)，我們比較 \(p,x\) 的大小關係。如果 \(x>p\)，那麼不做其他操作；否則就立刻刪除 \(x\)，然後檢查刪除 \(x\) 後是否產生新的葉結點，重複 \(2\) 步驟，直到未產生新節點或者新節點的編號 \(>p\)。
  3. 讓指針 \(p\) 自增直到遇到一個未被刪除葉結點為止；

正確性

循環上述操作 \(n-2\) 次，就完成了序列的構造。接下來考慮算法的正確性。

\(p\) 是當前編號最小的葉結點，若刪除 \(p\) 後未產生葉結點，我們就只能去尋找下一個葉結點；若產生了葉結點 \(x\)：

  • 如果 \(x>p\)，則反正 \(p\) 往後掃描都會掃到它，於是不做操作；
  • 如果 \(x<p\)，因為 \(p\) 原本就是編號最小的，而 \(x\) 比 \(p\) 還小，所以 \(x\) 就是當前編號最小的葉結點，優先刪除。刪除 \(x\) 繼續這樣的考慮直到沒有更小的葉結點。

算法複雜度分析，發現每條邊最多被訪問一次（在刪度數的時侯），而指針最多遍歷每個結點一次，因此複雜度是 \(O(n)\) 的。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 從原文摘的代碼，同樣以 0 為起點
vector<vector<int>> adj;
vector<int> parent;

void dfs(int v) {
  for (int u : adj[v]) {
    if (u != parent[v]) parent[u] = v, dfs(u);
  }
}

vector<int> pruefer_code() {
  int n = adj.size();
  parent.resize(n), parent[n - 1] = -1;
  dfs(n - 1);

  int ptr = -1;
  vector<int> degree(n);
  for (int i = 0; i < n; i++) {
    degree[i] = adj[i].size();
    if (degree[i] == 1 && ptr == -1) ptr = i;
  }

  vector<int> code(n - 2);
  int leaf = ptr;
  for (int i = 0; i < n - 2; i++) {
    int next = parent[leaf];
    code[i] = next;
    if (--degree[next] == 1 && next < ptr) {
      leaf = next;
    } else {
      ptr++;
      while (degree[ptr] != 1) ptr++;
      leaf = ptr;
    }
  }
  return code;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 同樣以 0 為起點
adj = [[]]
parent = [0] * n

def dfs()v:
    for u in adj[v]:
        if u != parent[v]:
            parent[u] = v
            dfs(u)

def pruefer_code():
    n = len(adj)
    parent[n - 1] = -1
    dfs(n - 1)

    ptr = -1
    degree = [0] * n
    for i in range(0, n):
        degree[i] = len(adj[i])
        if degree[i] == 1 and ptr == -1:
            ptr = i

    code = [0] * (n - 2)
    leaf = ptr
    for i in range(0, n - 2):
        next = parent[leaf]
        code[i] = next
        if degree[next] == 1 and next < ptr:
            degree[next] = degree[next] - 1
            leaf = next
        else:
            ptr = ptr + 1
            while degree[ptr] != 1:
                ptr = ptr + 1
            leaf = ptr
    return code

Prüfer 序列的性質

  1. 在構造完 Prüfer 序列後原樹中會剩下兩個結點，其中一個一定是編號最大的點 \(n\)。
  2. 每個結點在序列中出現的次數是其度數減 \(1\)。（沒有出現的就是葉結點）

用 Prüfer 序列重建樹

重建樹的方法是類似的。根據 Prüfer 序列的性質，我們可以得到原樹上每個點的度數。然後你也可以得到編號最小的葉結點，而這個結點一定與 Prüfer 序列的第一個數連接。然後我們同時刪掉這兩個結點的度數。

講到這裏也許你已經知道該怎麼做了。每次我們選擇一個度數為 \(1\) 的最小的結點編號，與當前枚舉到的 Prüfer 序列的點連接，然後同時減掉兩個點的度。到最後我們剩下兩個度數為 \(1\) 的點，其中一個是結點 \(n\)。就把它們建立連接。使用堆維護這個過程，在減度數的過程中如果發現度數減到 \(1\) 就把這個結點添加到堆中，這樣做的複雜度是 \(O(n\log n)\) 的。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// 原文摘代碼
vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
  int n = code.size() + 2;
  vector<int> degree(n, 1);
  for (int i : code) degree[i]++;

  set<int> leaves;
  for (int i = 0; i < n; i++)
    if (degree[i] == 1) leaves.insert(i);

  vector<pair<int, int>> edges;
  for (int v : code) {
    int leaf = *leaves.begin();
    leaves.erase(leaves.begin());

    edges.emplace_back(leaf, v);
    if (--degree[v] == 1) leaves.insert(v);
  }
  edges.emplace_back(*leaves.begin(), n - 1);
  return edges;
}

線性時間重建樹

同線性構造 Prüfer 序列的方法。在刪度數的時侯會產生新的葉結點，於是判斷這個葉結點與指針 \(p\) 的大小關係，如果更小就優先考慮它。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 原文摘代碼
vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
  int n = code.size() + 2;
  vector<int> degree(n, 1);
  for (int i : code) degree[i]++;

  int ptr = 0;
  while (degree[ptr] != 1) ptr++;
  int leaf = ptr;

  vector<pair<int, int>> edges;
  for (int v : code) {
    edges.emplace_back(leaf, v);
    if (--degree[v] == 1 && v < ptr) {
      leaf = v;
    } else {
      ptr++;
      while (degree[ptr] != 1) ptr++;
      leaf = ptr;
    }
  }
  edges.emplace_back(leaf, n - 1);
  return edges;
}

通過這些過程其實可以理解，Prüfer 序列與帶標號無根樹建立了雙射關係。

Cayley 公式 (Cayley's formula)

完全圖 \(K_n\) 有 \(n^{n-2}\) 棵生成樹。

怎麼證明？方法很多，但是用 Prüfer 序列證是很簡單的。任意一個長度為 \(n-2\) 的值域 \([1,n]\) 的整數序列都可以通過 Prüfer 序列雙射對應一個生成樹，於是方案數就是 \(n^{n-2}\)。

圖連通方案數

Prüfer 序列可能比你想得還強大。它能創造比 凱萊公式 更通用的公式。比如以下問題：

一個 \(n\) 個點 \(m\) 條邊的帶標號無向圖有 \(k\) 個連通塊。我們希望添加 \(k-1\) 條邊使得整個圖連通。求方案數。

證明

設 \(s_i\) 表示每個連通塊的數量。我們對 \(k\) 個連通塊構造 Prüfer 序列，然後你發現這並不是普通的 Prüfer 序列。因為每個連通塊的連接方法很多。不能直接淦就設啊。於是設 \(d_i\) 為第 \(i\) 個連通塊的度數。由於度數之和是邊數的兩倍，於是 \(\sum_{i=1}^kd_i=2k-2\)。則對於給定的 \(d\) 序列構造 Prüfer 序列的方案數是

\[ \binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}=\frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdots(d_k-1)!} \]

對於第 \(i\) 個連通塊，它的連接方式有 \({s_i}^{d_i}\) 種，因此對於給定 \(d\) 序列使圖連通的方案數是

\[ \binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot \prod_{i=1}^k{s_i}^{d_i} \]

現在我們要枚舉 \(d\) 序列，式子變成

\[ \sum_{d_i\ge 1，\sum_{i=1}^kd_i=2k-2}\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot \prod_{i=1}^k{s_i}^{d_i} \]

好的這是一個非常不喜聞樂見的式子。但是別慌！我們有多元二項式定理：

\[ (x_1 + \dots + x_m)^p = \sum_{\substack{c_i \ge 0 ,\ \sum_{i=1}^m c_i = p}} \binom{p}{c_1, c_2, \cdots ,c_m}\cdot \prod_{i=1}^m{x_i}^{c_i} \]

那麼我們對原式做一下換元，設 \(e_i=d_i-1\)，顯然 \(\sum_{i=1}^ke_i=k-2\)，於是原式變成

\[ \sum_{e_i\ge 0，\sum_{i=1}^ke_i=k-2}\binom{k-2}{e_1,e_2,\cdots,e_k}\cdot \prod_{i=1}^k{s_i}^{e_i+1} \]

化簡得到

\[ (s_1+s_2+\cdots+s_k)^{k-2}\cdot \prod_{i=1}^ks_i \]

即

\[ n^{k-2}\cdot\prod_{i=1}^ks_i \]

這就是答案啦

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用