プリュファーシーケンス

組合せ数学において、ラベル付き木のプリューファー列（プリューファーコード、プリューファー数とも呼ばれる）は、その木に関連付けられた一意の列である。n頂点の木のプリューファー列の長さはn − 2であり $、$ 単純 $な$ $反復$ アルゴリズムによって生成できる。プリューファー列は、 1918年にハインツ・プリューファーによってケーリーの公式を証明するために初めて使用された。^[¹^]

木をプリュファーシーケンスに変換するアルゴリズム

ラベル付き木のプリューファー列は、頂点が2つだけになるまで繰り返し頂点を削除することで生成できます。具体的には、頂点 ${1, 2, ...,$ $n$ $}を持つラベル付き木$ $T$ を考えます。ステップ $i$ では、ラベルが最小の葉を削除し、プリューファー列の $i$ 番目の要素をこの葉の隣接要素のラベルに設定します。

ラベル付きツリーのPrüferシーケンスは一意であり、長さは $n - 2$ です。

符号化と復号化はどちらも整数基数ソートに簡約され、並列化される。^{[ 2 ]}

例

上記のアルゴリズムを右に示す木に対して実行するとどうなるでしょうか。最初は頂点1が最も小さいラベルを持つ葉なので、まず頂点1を削除し、プリューファーシーケンスに4を追加します。次に頂点2と3を削除するので、頂点4がさらに2回追加されます。頂点4は葉になり、ラベルが最も小さいので削除し、シーケンスに5を追加します。残る頂点は2つだけなので、ここで処理を終了します。木のシーケンスは[4,4,4,5]です。

Prüferシーケンスをツリーに変換するアルゴリズム

[a[1], a[2], ..., a[n]]をプリューファー列とします。

木にはからまでn+2の番号が付けられたノードがあります。各ノードの次数を、シーケンス内での出現回数に1を加えた値に設定します。例えば、擬似コードでは次のようになります。 1n+2

Convert-Prüfer-to-Tree (  $a$  ) 1  $n$  ←長さ[  $a$  ] 2  $T \leftarrow 1$ から $n$  + 2までの番号が付けられた $n$  + 2個の孤立したノードを持つグラフ 3度← 整数の配列 4  $T$ 内の各ノード $i$ に対して 5 度[  $i$  ]←1を実行する 6それぞれの値 $i$ について、 $7$  度 [  $i$ ] ←度[  $i$  ] + 1

次に、シーケンスの各番号についてa[i]、次数が1である最初の（最も番号が小さい）ノードを見つけ、ツリーにjエッジを追加し、との次数をデクリメントします。擬似コードでは、次のようになります。(j, a[i])ja[i]

8 a の各値 $i$ に対して、次の $処理を$ 実行する9 T  $の$ 各ノード $j$ に対して、次の処理を実行する 10 次数[  $j$  ] = 1の場合、次 の処理を実行する 11エッジ[  $i$  ,  $j$  ] $を T$ に挿入する 12 次数[  $i$  ] ←次数[  $i$  ] - 1 13 度[  $j$  ] ←度[  $j$  ] - 1 14 休憩

このループの最後には、次数1のノードが2つ残ります（これらをu、と呼びます）。最後に、木にv辺を追加します。 ^[³^](u,v)

15  $u$  ←  $v$  ← 0 16  $T$ 内の各ノード $i$ について 17 次数[  $i$  ] = 1 の 場合 18 u  $=$  0の場合 19  $u$  ←  $i$  20 それ以外の場合 21  $v$  ←  $i$  22 break 23辺[  $u$  ,  $v$  ] を $T$ に挿入 24次数[  $u$  ] ←次数[  $u$  ] - 1 25度[  $v$  ] ←度[  $v$  ] - 1 26リターン $T$

ケーリーの公式

$n$ 頂点のラベル付き木のプリューファー列は、ラベル 1 から $nまでの長さ$ $n - 2$ の一意の列である。ラベル 1 から $n$ までの長さ $n$ $- 2$ の列 $S$ が与えられたとき、プリューファー列が $Sである$ 一意のラベル付き木が存在する。

直接的な帰結として、プリューファー列は、 $n$ 頂点上のラベル付き木の集合と、ラベル 1 から $nまでの長さ$ $n$ $- 2$ の列の集合との間の一対一関係を与える。後者の集合のサイズは $n$ $n$ $-2$ であるため、この一対一関係の存在はケイリーの公式、すなわち $n頂点上に$ $n$ $n$ $-2$ 本のラベル付き木が存在することを証明する。

その他のアプリケーション

出典: ^{[ 4 ]}

ケイリーの公式を強化すると、次の主張が証明されます。

各頂点に次数が指定された完全グラフにおける全域木の数は多項式係数に等しい。

K_{n}

d_{i}

i

{\binom {n-2}{d_{1}-1,\,d_{2}-1,\,\dots ,\,d_{n}-1}}={\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots (d_{n}-1)!}}.

証明は、Prüfer シーケンスで番号が正確に何回も現れることを観察することによって行われます。

i

{\textstyle d_{i}-1}

ケイリーの公式は一般化できる：ラベル付き木は、実際にはラベル付き完全グラフの全域木である。列挙されたプリューファー列に制約を課すことで、同様の方法で完全二部グラフの全域木の数を計算できる。G $が$ 、一方の区画に頂点1から $n$ $1 、もう一方の区画に頂点$ $n$ $1$ $+ 1$ から $nを持つ$ 完全二部グラフである場合、 $G$ のラベル付き全域木の数はであり、ここで $n$ $2$ $=$ $n$ $-$ $n$ $1$ である。 $n_{1}^{n_{2}-1}n_{2}^{n_{1}-1}$
均一に分布したランダムな Prüfer シーケンスを生成し、それを対応するツリーに変換することは、均一に分布したランダムなラベル付きツリーを生成する簡単な方法です。

参考文献

^プリューファー、H. (1918)。「Neuer Beweis eines Satzes über Permutationen」。アーチ。数学。物理学。27 : 742–744 .
^ Caminiti, S., Finocchi, I., Petreschi, R. (2007). 「ラベル付き木の符号化について」 .理論計算機科学. 382 (2): 97– 108. doi : 10.1016/j.tcs.2007.03.009 .{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
^ Jens Gottlieb、Bryant A. Julstrom、Günther R. Raidl、Franz Rothlauf (2001). 「Prüfer数：進化的探索におけるスパニングツリーの不適切な表現」（PDF） . Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) : 343– 350. 2006年9月26日時点のオリジナル（PDF）からアーカイブ。
^梶本秀次 (2003). 「プリューファーコードの拡張とブロックからの連結グラフの組み立て」.グラフと組合せ論. 19 (2): 231– 239. doi : 10.1007/s00373-002-0499-3 . S2CID 22970936 .

外部リンク

Prüfer コード– MathWorldより

[1] プリューファー、H. (1918)。「Neuer Beweis eines Satzes über Permutationen」。アーチ。数学。物理学。27 : 742–744 .

[2] Caminiti, S., Finocchi, I., Petreschi, R. (2007). 「ラベル付き木の符号化について」 .理論計算機科学. 382 (2): 97– 108. doi : 10.1016/j.tcs.2007.03.009 .{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[3] Jens Gottlieb、Bryant A. Julstrom、Günther R. Raidl、Franz Rothlauf (2001). 「Prüfer数：進化的探索におけるスパニングツリーの不適切な表現」（PDF） . Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) : 343– 350. 2006年9月26日時点のオリジナル（PDF）からアーカイブ。

[4] 梶本秀次 (2003). 「プリューファーコードの拡張とブロックからの連結グラフの組み立て」.グラフと組合せ論. 19 (2): 231– 239. doi : 10.1007/s00373-002-0499-3 . S2CID 22970936 .

[

[ 2 ]

[

[ 4 ]