プリューファー列のソースを表示

[[組み合わせ数学]]において、ラベル付きの[[木 (数学)|木]]に対する'''プリューファー列'''（{{lang-en-short|Prüfer sequence}}) あるいは'''プリューファーコード''' とは、その木から生成できる一意な数列である。
<math>n</math> 頂点の木のプリューファー列の長さは <math>n-2</math> であり、単純なアルゴリズムで生成できる。プリューファー列は、{{仮リンク|ハインツ・プリューファー|en|Heinz Prüfer}}が[[ケイリーの公式]]を証明するためにはじめて使ったといわれる<ref>{{cite journal | author=Prüfer, H. | title=Neuer Beweis eines Satzes über Permutationen | journal=Arch. Math. Phys. | year=1918 | volume=27 | pages=742–744}}</ref>。

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

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

プリューファー列の生成、プリューファー列からの木の復元の両方を、基数ソートのアルゴリズムを用いて並列化することができる。
<ref>{{cite journal | author=Caminiti, S., Finocchi, I., Petreschi, R. | title= On coding labeled trees | journal=Theoretical Computer Science | year=2007 | volume=382(2) | pages=97–108|doi=10.1016/j.tcs.2007.03.009}}</ref>

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

==プリューファー列から木を生成するアルゴリズム==
<math>\{a_1,a_2,\cdots a_n\}</math> を与えられたプリューファー列とする。
生成される木は <math>1</math> から <math>n+2</math> まで <math>n+2</math> 個の頂点を持つ。すべての頂点について、列の中に出てくる回数に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

次に、次数 <math>degree_j</math> が <math>1</math> であり、かつ最小となるような <math>j</math> を見つけて、木に辺 <math>(j,a_i)</math> を追加する操作を繰り返す。

  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'''

すべての <math>a_i</math> について操作を終えた後、次数が1となる残った2つの頂点 <math>u,v</math> について辺 <math>(u,v)</math> を追加し、アルゴリズムは終了する。
<ref>{{cite journal |author1=Jens Gottlieb |author2=Bryant A. Julstrom |author3=Günther R. Raidl |author4=Franz Rothlauf. |title=Prüfer numbers:   A poor representation of spanning trees for evolutionary search |journal=Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) |year=2001 |pages=343–350 |url=http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf |url-status=dead |archiveurl=https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf |archivedate=2006-09-26 }}
</ref>

 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''

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

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

==注釈・出典==
{{reflist}}

==外部リンク==
* [http://mathworld.wolfram.com/PrueferCode.html Prüfer code] – from [[MathWorld]]

{{DEFAULTSORT:ふりゆうふああれつ}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]