プリューファー列

ウィキペディア

プリューファー列

出典: フリー百科事典『ウィキペディア（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} となる。

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

${\displaystyle \{a_{1},a_{2},\cdots a_{n}\}}$ を与えられたプリューファー列とする。 生成される木は ${\displaystyle 1}$ から ${\displaystyle n+2}$ まで ${\displaystyle 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

次に、次数 ${\displaystyle degree_{j}}$ が ${\displaystyle 1}$ であり、かつ最小となるような ${\displaystyle j}$ を見つけて、木に辺 ${\displaystyle (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

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

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

ケイリーの公式

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

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

注釈・出典

1. ^ Prüfer, H. (1918). “Neuer Beweis eines Satzes über Permutationen”. Arch. Math. Phys. 27: 742–744. 
2. ^ Caminiti, S., Finocchi, I., Petreschi, R. (2007). “On coding labeled trees”. Theoretical Computer Science 382(2): 97–108. doi:10.1016/j.tcs.2007.03.009. 
3. ^ Jens Gottlieb; Bryant A. Julstrom; Günther R. Raidl; Franz Rothlauf. (2001). “Prüfer numbers: A poor representation of spanning trees for evolutionary search”. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001): 343–350. オリジナルの2006-09-26時点におけるアーカイブ。. https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf. 

外部リンク

• Prüfer code – from MathWorld