木からプリューファー列を生成するアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:32 UTC 版)
「プリューファー列」の記事における「木からプリューファー列を生成するアルゴリズム」の解説
ラベル付き木から、2つの頂点が残るまで繰り返し頂点を繰り返し除いていくことによりプリューファー列を生成できる。頂点 1 {\displaystyle 1} から n {\displaystyle n} からなる木からプリューファー列を生成することを考える。 i {\displaystyle i} 番目のステップでは、この木の葉のうち番号が最も小さいものを選び、隣接する頂点をプリューファー列に追加するとともに、選んだ葉を木から取り除く。 ラベル付き木についてプリューファー列は一意であり、長さは n − 2 {\displaystyle n-2} である。 プリューファー列の生成、プリューファー列からの木の復元の両方を、基数ソートのアルゴリズムを用いて並列化することができる。
※この「木からプリューファー列を生成するアルゴリズム」の解説は、「プリューファー列」の解説の一部です。
「木からプリューファー列を生成するアルゴリズム」を含む「プリューファー列」の記事については、「プリューファー列」の概要を参照ください。
ウィキペディア小見出し辞書の「木からプリューファー列を生成するアルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 木からプリューファー列を生成するアルゴリズムのページへのリンク
