Skip to content →

Prüfer コード

この記事ではラベル付き木を全単射な方法で数列に変換する、Prüfer コード(Prüfer 列)と呼ばれるテクニックを解説する。Prüfer コードを使えば、ラベル付き木を数えやすい対象に変換することができるので、木の数え上げに威力を発揮する。

Prüfer コードの定義

頂点集合 \(V=\{1,2,\ldots,n\}\) からなり、頂点 \(n\) を根とするラベル付き木 \(T\) を考える。木 \(T\) に対する Prüfer code を以下のよう生成される頂点列 \(\mathcal{P}(T)=(y_1,y_2,..,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 コードの応用例として最も有名なのは次の定理だろう。

Cayley の定理:\(n\) 頂点ラベル付き木は \(n^{n-2}\) 個ある。

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

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

問題1:\(n\) 頂点ラベル付き木であって、各頂点 \(i\) の次数が \(d_i\) \((1\leq i \leq n)\) である木はいくつあるか。

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

問題演習

問題2:葉が \(m\) 個ある \(n\) 頂点ラベル付き根付き木はいくつあるか(根は頂点 \(n\) とする)。

解答:\(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}\) 個。

問題3:根の次数が \(m\) であるラベル付き木はいくつあるか(根は頂点 \(n\) とする)。

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

問題4: 頂点にラベルが付いた \(n\) 頂点 \(m\) 辺の森が与えられる。\(n-1-m\) 辺追加してできる木は何通りあるか。(出典:碧@KOKTOSbot

解答:森の各連結成分 \(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|\) が答え。

問題5:ラベル付き木をランダムに生成したとき、各頂点の次数の 2 乗の期待値はいくつか。

解答:問題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})\) が答え。

問題6:ラベル付き完全 \(m\) 部グラフ \(K_{n_1,\ldots,n_m}\) の全域木 \(T\) はいくつあるか。ただし、頂点 \(\sum_{i=1}^{k-1} n_i\) から 頂点 \(n_k+\sum_{i=1}^{k-1} n_i\) の \(n_k\) 個の頂点は \(k\) 番目の部集合 \(V_k\) に属するとする。(出典:[2])

解答:\(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}\) が答え。

問題7: \(k\) 木を次のように再帰的に定義されるグラフとする。

  1. \(k+1\) 頂点完全グラフ \(K^{k+1}\) は \(k\) 木である。
  2. \(k\) 木 \(G\) の部分グラフ \(H \cong K^k\) の各頂点と隣接する新たな頂点を \(G\) に加えたグラフは \(k\) 木である。

\(n\) 頂点ラベル付き \(k\) 木は何通りあるか。(出典:[3])

解答:この問題は今までの問題と比べると難しい(当社比)が 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 コードが応用できると知って驚いた。

Published in アルゴリズム

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA