プリューファー列

ウィキペディア

プリューファー列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/02 13:25 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}\}$ カテゴリ / コモンズ