ケイリーの公式

ウィキペディア

ケイリーの公式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/09/21 00:25 UTC 版)

2個、3個、4個のラベル付き頂点を持つ木の一覧。2個のラベル付き頂点を持つ木は 2^2-2 = 1 個、3個のラベル付き頂点を持つ木は 3^3-2 = 3 個、4個のラベル付き頂点を持つ木は 4^4-2 = 16 個ある。

ケイリーの公式（ケイリーのこうしき、英: Cayley's formula）は、グラフ理論における公式のひとつ。正整数 n に対し、n 個のラベル付き頂点を持つ木の個数は n^n-2 であるというもの。ケイリーは19世紀のイギリスの数学者。

歴史

この公式にアーサー・ケイリーの名が冠されているのは、1889年の論文 (Cayley 1889) に由来する。ただし、この論文が引用しているカール・ヴィルヘルム・ボルチャルトの論文（1860年）において、すでに証明が与えられている。また、ジェームス・ジョセフ・シルベスターも1857年に同値な命題を与えている。

1918年にハインツ・プリューファーが行った証明が有名で、この過程でプリューファーコードの概念が生み出された。

証明

プリューファーコードを用いた証明

n=6の時の、n個の点で構成される木の例。この木のプリューファーコードは {4,4,4,5}である

n個の点で構成されるラベル付きの木の集合と、記号列「{a₁,a₂, ..., a_n-2}」の集合を、1対1で対応させる（全単射）ことを考える。ただし、「a_i」は整数であり、「1≦a_i≦n」とする。

「1≦a_i≦n」（つまり、記号「a_i」は1からnまでの値を取りうる）であるから、記号列「{a₁, a₂, ..., a_n-2}」の個数は、全部で「n^n-2」個あると言える。なので、もしn個の点で構成される木の集合と、記号列「{a₁,a₂, ..., a_n-2}」の集合を、1対1で対応させることができたなら、n 個のラベル付き頂点を持つ木の個数が「n^n-2」個であるということが直ちに言える。「n=1」または「n=2」の時は自明であるので、「n≧3」の時について考えよう。

端点のラベルで最小のものをb₁とし、b₁に隣接している点のラベルをa₁とする。この時、点b₁とその接続辺を除去すると、「n-1」個の点で構成されるラベル付きの木が得られる。次に、この新しい木の端点で最小のラベルをb₂とし、点b₂に隣接している点のラベルをa₂とし、点b₂とその接続辺を除去する。このように、端点と隣接辺のセットを次々に除去していき、2つの点になるまで続けていく。この結果、記号列{a₁,a₂, ..., a_n-2}が得られる。この記号列を「プリューファーコード」と呼ぶ。例えば上図のようなラベル付きの木の場合、「n=6」であり、プリューファーコードは 「{4,4,4,5}」である。

逆も見ていこう。まず、辺のないn個の点だけで構成されるグラフを考えよう。このグラフの中で、記号列「{a₁,a₂, ..., a_n-2}」の中にはない、最小の点のラベルをb₁として、点b₁と点a₁を辺で結ぶ。次に、記号列からa₁を除去し、点b₁に×印を付けよう。次に、記号列「{a₂, ..., a_n-2}」の中にはなく、×印もついていない最小の点のラベルをb₂として、点b₂と点a₂を辺で結ぶ。このように、次々と線を結んでいき、点a_n-2と点b_n-2まで結び、最後に×印の付いていない（点b₁からb_n-2までに含まれなかった）2点を線で結ぶ。こうしてできたグラフを見ると、最初の木と同じものである。

このように見ていくと、任意に設定したプリューファーコードから、必ず最初に出発した木に戻ることができることが分かる。つまり、記号列「{a₁,a₂, ..., a_n-2}」の集合と、n個の点で構成されるラベル付きの木の集合が、1対1で対応していることが言える。証明終。

double counting法を用いた証明

有向辺を付け加える。

n個のラベル付き頂点を持つ木の個数をT_nとおく。ラベルが付いた頂点とラベルが付いた辺を持つ根付き木の個数U_nを2通りの方法で数える（double countingを参照）。なお根付き木の各辺は、根から遠ざかる方向に向き付けるものとする。

各ラベル付き頂点を持つ木に対して、根の選び方はn通り、辺へのラベルの付け方は(n-1)!通りなので、

$U_{n}=T_{n}n(n-1)!=T_{n}n!.$

ウィキペディア小見出し辞書

ケイリーの公式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:32 UTC 版)

「プリューファー列」の記事における「ケイリーの公式」の解説

n 頂点の木に対するプリューファー列は n − 2 の長さの、 1 から n の整数からなる一意な列である。逆に、長さ n − 2 で 1 から n の整数からなるすべての列について、対応する木がただ一つ存在する。 この定理は、ただちに「 n 頂点の木と長さ n − 2 で 1 から n の整数からなる列に全単射が存在する」という系を導く。列としてありうるものは n n − 2 個存在するので、 n 頂点の木は n n − 2 通り存在するとするケイリーの公式が示される。