ケイリーの公式

出典: フリー百科事典『ウィキペディア(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年の論文 (Cayley 1889) に由来する。ただし、この論文が引用しているカール・ヴィルヘルム・ボルチャルト英語版の論文(1860年)において、すでに証明が与えられている。また、ジェームス・ジョセフ・シルベスターも1857年に同値な命題を与えている。

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

証明[編集]

プリューファーコードを用いた証明[編集]

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

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

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

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

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

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

double counting法を用いた証明[編集]

有向辺を付け加える。

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

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

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

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

参考文献[編集]