グラフ理論において、連結した無向完全グラフ `G=(V,E)` が与えられたとき、 この部分グラフで木であるものを、無向グラフの全域木またはスパニングツリーという。
頂点数が `n` である無向完全グラフ `K_n` の異なる全域木の総数は `n^(n-2)` である。 これをケーリーの定理という。 ケーリーとは、線形代数でお目にかかる、ケーリー・ハミルトンの定理のケーリーのことである。 `n = 4` の場合は `n^(n-2) = 16` である。この全 16 通りの例を示す。
このケーリーの定理の証明で、`{a_1, a_2, cdots, a_n} (a_i = 1, cdots, n; 1 le i le n - 2) ` となる数列と、異なる全域木すべての間に全単射が存在することを示す方法がある。 この証明で使われる数列 `{a_1, a_2, cdots, a_n}` をプリューファー列と呼ぶ。 プリューファー列から全域木を作る手順や、逆に全域木からプリューファー列を作る手順は Wikipedia や下記の文献を参照されたい。 下の表の左側は `K_10` のプリューファー列の例、右側はプリューファー列から再構成した全域木の辺である。
次の図はプリューファー列 A から構成した全域木である。
参考文献では、`K_5` の全域木すべて 125 通りをすべて図に示せという練習問題があった。 さすがに図に示すのは大変なので、全域木の構成を示すことで代わりとする。
まりんきょ学問所 ＞ JavaScript 手習い ＞ 全域木とプリューファー列
