プリューファー列

ウィキペディア

プリューファー列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:32 UTC 版)

組み合わせ数学において、ラベル付きの木に対するプリューファー列（英: Prüfer sequence) あるいはプリューファーコード とは、その木から生成できる一意な数列である。 $n$

プリューファー列 {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