プリューファー列

組み合わせ数学において、ラベル付きの木に対するプリューファー列（) あるいはプリューファーコード とは、その木から生成できる一意な数列である。
formula_1 頂点の木のプリューファー列の長さは formula_2 であり、単純なアルゴリズムで生成できる。プリューファー列は、がケイリーの公式を証明するためにはじめて使ったといわれる。
木からプリューファー列を生成するアルゴリズム.
ラベル付き木から、2つの頂点が残るまで繰り返し頂点を繰り返し除いていくことによりプリューファー列を生成できる。
頂点 formula_3 から formula_1 からなる木からプリューファー列を生成することを考える。
formula_5 番目のステップでは、この木の葉のうち番号が最も小さいものを選び、隣接する頂点をプリューファー列に追加するとともに、選んだ葉を木から取り除く。
ラベル付き木についてプリューファー列は一意であり、長さは formula_2 である。
プリューファー列の生成、プリューファー列からの木の復元の両方を、基数ソートのアルゴリズムを用いて並列化することができる。
例.
右の図で上に示したアルゴリズムを実行することを考える。最初、頂点1は最も小さい番号の頂点なので、これは木から削除され、隣接する頂点である4が列に追加される。
次に、同じように2と3が木から削除され、4がまた2回列に追加される。
ここで、4は木において葉となり、かつ最も番号が小さいので削除され、5が列に追加される。
これで残った頂点は2つになったのでアルゴリズムは停止し、プリューファー列は {4,4,4,5} となる。
プリューファー列から木を生成するアルゴリズム.
formula_7 を与えられたプリューファー列とする。
生成される木は formula_3 から formula_9 まで formula_9 個の頂点を持つ。すべての頂点について、列の中に出てくる回数に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
次に、次数 formula_11 が formula_3 であり、かつ最小となるような formula_13 を見つけて、木に辺 formula_14 を追加する操作を繰り返す。
 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
すべての formula_15 について操作を終えた後、次数が1となる残った2つの頂点 formula_16 について辺 formula_17 を追加し、アルゴリズムは終了する。
 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"
ケイリーの公式.
formula_1 頂点の木に対するプリューファー列は formula_2 の長さの、formula_3 から formula_1 の整数からなる一意な列である。
逆に、長さ formula_2 で formula_3 から formula_1 の整数からなるすべての列について、対応する木がただ一つ存在する。
この定理は、ただちに「formula_1 頂点の木と長さ formula_2 で formula_3 から formula_1 の整数からなる列に全単射が存在する」という系を導く。
列としてありうるものは formula_29 個存在するので、formula_1 頂点の木は formula_29 通り存在するとするケイリーの公式が示される。