プリューファー列

組み合わせ数学において、ラベル付きの木に対するプリューファー列（英: Prüfer sequence) あるいはプリューファーコード とは、その木から生成できる一意な数列である。 $n$ 頂点の木のプリューファー列の長さは $n-2$ であり、単純なアルゴリズムで生成できる。プリューファー列は、ハインツ・プリューファーがケイリーの公式を証明するためにはじめて使ったといわれる。

木からプリューファー列を生成するアルゴリズム

ラベル付き木から、2つの頂点が残るまで繰り返し頂点を繰り返し除いていくことによりプリューファー列を生成できる。 頂点 $1$ から $n$ からなる木からプリューファー列を生成することを考える。 $i$ 番目のステップでは、この木の葉のうち番号が最も小さいものを選び、隣接する頂点をプリューファー列に追加するとともに、選んだ葉を木から取り除く。

ラベル付き木についてプリューファー列は一意であり、長さは $n-2$ である。

プリューファー列の生成、プリューファー列からの木の復元の両方を、基数ソートのアルゴリズムを用いて並列化することができる。

例

プリューファー列 {4,4,4,5}　を生成する木

右の図で上に示したアルゴリズムを実行することを考える。最初、頂点1は最も小さい番号の頂点なので、これは木から削除され、隣接する頂点である4が列に追加される。 次に、同じように2と3が木から削除され、4がまた2回列に追加される。 ここで、4は木において葉となり、かつ最も番号が小さいので削除され、5が列に追加される。 これで残った頂点は2つになったのでアルゴリズムは停止し、プリューファー列は {4,4,4,5} となる。

プリューファー列から木を生成するアルゴリズム

$\{a_{1},a_{2},\cdots a_{n}\}$ を与えられたプリューファー列とする。 生成される木は $1$ から $n+2$ まで $n+2$ 個の頂点を持つ。すべての頂点について、列の中に出てくる回数に1を加えた値を次数として記録する。

 Convert-Prüfer-to-Tree(a)
 1 n ← length[a]
 2 T ← a graph with n + 2 isolated nodes, numbered 1 to n + 2
 3 degree ← an array of integers
 4 for each node i in T do
 5     degree[i] ← 1
 6 for each value i in a do
 7     degree[i] ← degree[i] + 1

次に、次数 $degree_{j}$ が $1$ であり、かつ最小となるような $j$ を見つけて、木に辺 $(j,a_{i})$ を追加する操作を繰り返す。

 8 for each value i in a do
 9     for each node j in T do
10         if degree[j] = 1 then
11             Insert edge[i, j] into T
12             degree[i] ← degree[i] - 1
13             degree[j] ← degree[j] - 1
14             break

すべての $a_{i}$ について操作を終えた後、次数が1となる残った2つの頂点 $u,v$ について辺 $(u,v)$ を追加し、アルゴリズムは終了する。

15 u ← v ← 0
16 for each node i in T
17     if degree[i] = 1 then
18         if u = 0 then
19             u ← i
20         else
21             v ← i
22             break
23 Insert edge[u, v] into T
24 degree[u] ← degree[u] - 1
25 degree[v] ← degree[v] - 1
26 return T

ケイリーの公式

$n$ 頂点の木に対するプリューファー列は $n-2$ の長さの、$1$ から $n$ の整数からなる一意な列である。 逆に、長さ $n-2$ で $1$ から $n$ の整数からなるすべての列について、対応する木がただ一つ存在する。

この定理は、ただちに「$n$ 頂点の木と長さ $n-2$ で $1$ から $n$ の整数からなる列に全単射が存在する」という系を導く。 列としてありうるものは $n^{n-2}$ 個存在するので、$n$ 頂点の木は $n^{n-2}$ 通り存在するとするケイリーの公式が示される。

外部リンク

• Prüfer code – from MathWorld