Prüfer コード（Prüfer 列）とは、ラベル付き木を全単射に変換した一種の数列である。ラベル付き木を数えやすい対象に変換でき、木の数え上げに威力を発揮する。

Prüfer コードの定義

頂点集合 \(V=\{1,2,\ldots,n\}\) からなり、頂点 \(n\) を根とするラベル付き木 \(T\) を考える。木 \(T\) に対する Prüfer code を以下のよう生成される頂点列 \(\mathcal{P}(T)=(y_1,y_2,\ldots,y_{n-2})\) として定義する。

1. \(T_1:=T\)
2. 以下の操作を \(k=1,2,\ldots,n-1\) について行う。
   1. \(T_k\) のラベル最小の葉を \(x_k\), その親を \(y_k\) とする。
   2. \(T_{k+1}:=T_k-x_k\)

※ \(y_{n-1}=n\) は Prüfer コードには含まない。

Prüfer コードを作る一例は下図。

Prüfer コードの全単射性

\(n\) 頂点ラベル付き木全体から \(V^{n-2}\) への写像 \(\mathcal{P}\) が全単射であることを示したい。異なる木は異なる Prüfer コードを生成するから \(\mathcal{P}\) は単射である。全射であるには、木をなすように \((y_i)\) から \((x_i)\) が一意に復元できればよい。\(x_1,x_2,\ldots,x_k\) まで復元できたとする。木 \(T_{k+1}\) について、\(x_1,x_2,\ldots,x_k\) はすでに削除された頂点、\(y_{k+1},y_{k+2},\dots,y_{n-1}\) は葉となりえない頂点、その他の頂点は葉である。従って、\(S=\{x_1,x_2,\ldots,x_k\}\cup\{y_{k+1},y_{k+2},\ldots,y_{n-1}\}\) に含まれないラベル最小の頂点が \(x_{k+1}\) として定まる。\(|S| < n\) であるからこのような頂点は必ず取れる。以上より \((y_i)\) から \((x_i)\) が一意に復元できたから、\(\mathcal{P}\) は全単射であることが示された。

Prüfer コードの応用例として最も有名なのは次の定理だろう。

\(\mathcal{P}\) は \(n\) 頂点ラベル付き木全体から \(V^{n-2}\) への全単射であるから、この定理が成り立つ。

次のような数え上げの問題も Prüfer コードによって処理できる。

次数 \(d\) の頂点はちょうど \(d-1\) 回 Prüfer コードに出現するから、\({n-2 \choose d_1-1,d_2-1, \ldots ,d_n-1}\) 通り存在する。

問題演習

解答：\(m\) 個の葉が Prüfer コードに出現しないから \({n-1 \choose m}\sum_{i=0}^{n-1-m}{n-1-m \choose i}(-1)^i(n-m-i)^{n-2}\) 個。

解答：根 \(n\) が \(m-1\) 回 Prüfer コードに出現するから \({n-2 \choose m-1}(n-1)^{n-m-1}\) 個。

解答：森の各連結成分 \(G_i\) を縮約して 1 頂点にしたグラフを \(G’\) とする。\(G’\) の各頂点にはラベル \(1,2,…,n-m\) を付ける。Prüfer コード \(P(T)=(y_1,…,y_{n-m-2})\) は \(V(G’)^{n-m-2}\) への全単射で、次数 \(d(v)\) の頂点 \(v\) は \(y_1,…,y_{n-m-2}\) に \(d(v)-1\) 回出現する。また、縮約を解いた際、\(G’\) の頂点 \(i\) に接続する辺は、 \(G\) において \(|G_i|\) 通りの端点の接続方法がある。したがって \((\prod|G_i|)(\sum|G_i|)^{n-m-2}=n^{n-m-2}\prod|G_i|\) が答え。

\(kn^{n-k-1}\)通り。

解答：問題１より、各頂点 \(i\) の次数が \(d_i\) であるラベル付き木の総数は \((\sum_{i=1}^n x_i)^{n-2}\) の \(\prod_{i=1}^n x_i^{d_i-1}\) の係数に等しい。従って、\(\left(\frac{d}{dx}x\right)^2(x+\sum_{i=2}^{n} 1)^{n-2}\) に \(x=1\) を代入してラベル付き木の総数 \(n^{n-2}\) で割った \((5-\frac{6}{n})(1-\frac{1}{n})\) が答え。

解答：\(W_i:=V \setminus V_i\) とする。Prüfer コードと同様に符号化しようとしても、\(n-1\) 番目に取り除く頂点 \(n\) でない端点の部集合が分からないので上手くいかないはずである。そこで全域木 \(T\) のコード \(\mathcal{P’}(T)=(\sigma_1,\sigma_2,\ldots,\sigma_k,\sigma_\infty) \in W_1^{n_1-1} \times W_2^{n_2-1}\times \ldots \times W_k^{n_k-1} \times V^{n-2} \) を次のように構成する。

1. \((\sigma_1,\sigma_2,\ldots,\sigma_k,\sigma_\infty):=(\emptyset,\emptyset,\ldots,\emptyset,\emptyset)\)
2. \(T_1:=T\)
3. 以下の操作を \(k=1,2,\ldots,n-1\) について行う。
   1. \(T_k\) のラベル最小の葉を \(v\) 、その親を \(p\) 、\(v\) の属する部集合を \(W_a\) とする。
   2. \(T_k\) において \(W_a\) に \(v\) 以外の頂点が含まれるならば \(\sigma_a\)、さもなくば \(\sigma_\infty\) の末尾に \(v\) を追加する。
   3. \(T_{k+1}:=T_k-v\)

Prüfer コードと同様に削除済みの頂点と葉でない頂点に着目すれば次に削除される葉が分かり、全ての全域木 \(T\) と \(W_1^{n_1-1} \times W_2^{n_2-1}\times \ldots \times W_k^{n_k-1} \times V^{n-2}\) は全単射の関係にあることが示せる。従って、\(n^{m-2}\prod(n-n_i)^{n_i-1}\) が答え。

解答：この問題は今までの問題と比べると難しい（当社比）が Prüfer コードと同じ考えで処理できる。頂点 \(v\) とその隣接頂点の集合 \(N(v)\) が誘導する部分グラフが \(K^k\) と同型であるとき、頂点 \(v\) を k-leaf と呼ぶことにする。 Prüfer コードに倣って \(k\) 木 \(G\) に関する頂点の列 \(a_i\) と頂点集合の列 \(B_i\) を次のように作ろう。

1. \(G_1:=G\)
2. 以下の操作を \(i=1,2,\ldots,n-k\) について行う。
   1. \(G_i\) のラベル最小の k-leaf を \(a_i\), その隣接頂点の集合を \(B_i\) とする。
   2. \(G_{i+1}:=G_i-a_i\)

\(G\) に対して \((a_i),(B_i)\) の組は単射である。全射を示したい。この構成方法は \(k\) 木の定義にある再帰的構築の全く逆再生である（初期状態が \(K^k\) か \(K^{k+1}\) かという違いを無視すれば）。定義に従って \(k\) 木を構築するとき、k-leaf になるのは (ii) で追加された頂点のみ、また k-leaf でなくなるのは、(ii) で追加された頂点の隣接頂点のみ。各 \(B_i\) (\(i < n-k\))は \(|B_i-B_j|\leq1\) となる \(j>i\) が存在する。従って、Prüfer コードと同様にすれば、\((B_i)\) から \((a_i)\) を一意に復元できるから全射である。

\(|B_i-B_j|\leq1\) からも分かる通りこの表現は冗長である。より詳しく見ると \(B_i=B_{n-k}\) であるか、\(a_j \in B_i \land B_i-\{a_j\} \subset B_j\) を満たす唯一の \(i < j\leq n-k\) が存在する。後者の場合、実は \(\{u\}=B_i-B_j, \{v\}=B_j-B_i\) の 2 つだけ持っておけば十分である。この事はこれらだけから、\((a_i)\) が復元でき、\((a_i)\) を合わせれば \((B_i)\) が復元できることから分かる。\(u \in V(G)\setminus{B_{n-k}}, v \in B_j\) の頂点を自由に取れる。

以上から \(B_{n-k}\) を選ぶ \(n \choose k\) 通りも併せて \({n \choose k}(1+k(n-k))^{n-k-1}\) 通りが答え。

参考文献

1. ヴァン・リント&ウィルソン 組合せ論 上
   • Prüfer コードの定義や全単射性の証明について参考にした。
2. Lewis, Richard P. “The number of spanning trees of a complete multipartite graph.” Discrete mathematics 197 (1999): 537-541.
   • 完全多部グラフの全域木の Prüfer コードについて参考にした。
3. Costa Pereira, P. R., Lilian Markenzon, and Oswaldo Vernet. “The Reduced Prufer Code for Rooted Labelled k-Trees.” ELECTRONIC NOTES IN DISCRETE MATHEMATICS 22.1 (2005): 135-139.
   • k 木の Prüfer コードについて参考にした。k 木にも Prüfer コードが応用できると知って驚いた。