プリューファー列

プリューファー列とその生成アルゴリズム

組み合わせ数学におけるプリューファー列（Prüfer sequence）とは、ラベル付き木から一意に生成される数列です。この数列の長さは、木の頂点数が n のときに n - 2 となります。プリューファー列は、数学者ハインツ・プリューファーがケイリーの公式の証明に寄与するために初めて導入したとされています。

プリューファー列の生成方法

プリューファー列を生成するためのプロセスは、ラベル付き木から叶う2つの頂点が残るまで、繰り返し葉を削除していくというものです。ここで、「葉」とは、他の頂点との接続が1本しかない頂点を指します。

具体的な手順は次の通りです。
1. まず、木に含まれる頂点を1からnまでの番号で扱います。
2. 各ステップで、最も小さい番号の葉を選び、その隣接頂点をプリューファー列に追加します。選んだ葉はその後木から取り除かれます。
3. 上記の操作を繰り返し、残った頂点が2つになるまで続けます。

この方法に従った例を見てみましょう。まず、頂点1が最も小さいため、これを木から削除し、接続している頂点4をプリューファー列に追加します。続けて、頂点2と3を削除し、再度4が追加されます。ここで、4は葉となり、最も小さい番号のため削除され、次に5が列に追加され得ます。最終的に残った頂点は2つになり、その際のプリューファー列は {4, 4, 4, 5} となります。

プリューファー列から木を生成する

逆に、プリューファー列から木を再構成する手順も存在します。プリューファー列が {a1, a2, ..., an} で与えられた場合、生成される木は1からn+2までの n+2 個の頂点を持ちます。各頂点の次数は、列の中での出現回数に1を加えた値として記録します。

具体的には、次のようなアルゴリズムを使います。
1. 初めに n の長さを取得し、1から n+2 の孤立した頂点で構成されるグラフを生成します。
2. 各頂点の初期次数を1で設定し、その後プリューファー列に基づいて次数を更新します。
3. 次に、次数が1の中で最小のjを見つけ、該当する頂点にプリューファー列から選ばれた値との間に辺を追加していきます。
4. すべてのa_iに対する操作を終えた後、残った2つの頂点の間に辺を追加して、アルゴリズムを完了します。

ケイリーの公式

ケイリーの公式は、n 頂点の木に対するプリューファー列の性質を示す重要な結果です。特に、n 頂点の木に対するプリューファー列は一意であり、その長さは n - 2 です。さらに、指定された長さの列を用いて生成可能な木はただ一つ存在します。これにより、n 頂点の木は n^{n-2} 通り存在することが示され、組織的な数学的理解を深める手段となります。

結論

プリューファー列は、木構造の解析やより広範な組み合わせ論の研究において極めて重要な役割を果たしています。特に、この列を生成するアルゴリズムや逆に木を再構築するプロセスの理解は、データ構造の最適化やネットワーク設計など、様々な応用分野でも活用されています。

もう一度検索