ケイリーの公式

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
2個、3個、4個のラベル付き頂点を持つ木の一覧。2個のラベル付き頂点を持つ木は 22-2 = 1 個、3個のラベル付き頂点を持つ木は 33-2 = 3 個、4個のラベル付き頂点を持つ木は 44-2 = 16 個ある。

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


歴史[編集]

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

証明[編集]

Graph.tree. Cayley's formula.png

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

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

次に、別の方法でUnを求める。ラベルが付いたn頂点からなる空グラフに順次向きを持った辺を付け加えることにより根付き木を構成する。k番目に付け加えられる辺のラベルはkとする。 空グラフにn-k本の辺が付け加えられてk本の根付き木(孤立点も根付き木と見なす)からなる森が出来たとする。この森にn-k+1番目の有向辺を付け加える方法は何通りか考える。付け加える有向辺の始点の選び方はn通りあり、終点は、先ほど選んだ始点が属さないk-1個の木の根のなかから選べるので、終点の選び方はk-1通りある。ゆえに辺の付け加え方はn(k-1)通りである。したがって、

U_n=\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.

Tn n! = nn − 2 n!から、Tn = nn − 2を得る。

参考文献[編集]