■ケイリーの定理とラベル付きの木

1889年、ケイリーはn個の頂点をもつラベル付きの木の数t(n)を決定する問題に取り組んだ。

この問題は非常に簡単な答えをもつ。

===================================

【1】ケイリーの定理

n個の頂点をもつラベル付きの木の数はt(n)=n^(n-2)である。

頂点数3のベル付きの木は3個ある。

頂点数4のベル付きの木は16個ある。

頂点数5のベル付きの木は125個ある。

この定理は完全グラフKnがn^(n-2)個のラベル付き全域木をもつことを主張している。

===================================

【2】非同型な全域木

ラベル付きは同型なグラフを同一視しないことを意味している。

頂点数3のベル付きの木は3個ある。→頂点数3の非同型な全域木は1個ある(V字型=3!/2!=3個)

頂点数4のベル付きの木は16個ある。→頂点数4の非同型な全域木は2個ある

(N字型=4!/2!=12個、T字型=4!/3!=4個)

頂点数5のベル付きの木は125ある。→頂点数5の非同型な全域木は3個ある

(X字型=5!/4!=5個、W字型=5!/2!=60個、Y字型=5!/2!=60個)

===================================