Cayleyの定理 (全域木の総数)1. (次数列による方法)

この記事の所要時間: 648

Cayley の定理

この記事では,グラフの全域木の個数に関する Cayley の定理を紹介します.

定理 (Cayley)

任意の自然数 \(n\geq 2\) に対して,頂点数が \(n\) である完全グラフ \(K_n\) の全域木の総数は

\begin{align*}
T(K_n) = n^{n-2}
\end{align*}

一般のグラフ \(G\) の全域木の総数を \(T(G)\) の記号で表すこととします.

ここでは,4 通りの証明を紹介していきます(長くなるので別々の記事に分けます).4 つ目のラプラシアン行列を用いる方法では完全グラフ \(K_n\) に限らず一般のグラフの全域木の総数を求めることができます.

言葉の説明

頂点数が \(n\) の完全グラフ \(K_n\) とは,

\(n\) 個の頂点のうち任意の 2 点の間に枝が存在するようなグラフのこと.

3頂点の完全グラフ \(K_3\)

グラフ \(G=(V, E)\) の全域木とは,

グラフ \(G\) のすべての頂点と \(E\) の部分集合 \(T\) からなるグラフで木 (閉路をもたないグラフ) であるようなもののこと.

K3 の全域木.全部で 3 種類ある.

証明

1. 次数列による方法

命題1. 

\(n\geq 2\) とする.\(d_1, d_2, \ldots, d_n\) を和が \(2n-2\) である正の整数の列とする.このとき,頂点 \(i\) \((i=1, 2, \ldots, n)\) の次数が \(\deg{i}=d_i\) であるような \(K_n\) の全域木の総数は

\begin{align*}
\dfrac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}.
\end{align*}

頂点の次数とは,その頂点から出ている枝の数のことです.

\(n\) 頂点の木では,枝の総数は \(n-1\) 本なので,すべての頂点の次数の和はその 2 倍である \(2n-2\) になります.

命題1. の証明

この命題は \(n\) に関する帰納法で証明します.

まず \(n=2\) の場合は \(d_1=d_2=1\) であり,全域木は 1 つしかない (\(K_2\)自身のみ) ので,成り立ちます.

そこで,\(n>2\) の場合を考えます.

\[d_1+d_2+\cdots+d_n=2n-2<2n\]

なので,少なくとも 1 つの頂点においてその次数が 1 です.

そこで,\(d_n=1\) とします.

(頂点の番号付け \(1, 2, \ldots, n\) は自由に決めてよいので,次数が 1 の頂点と頂点 \(n\) を入れ替えると考える.)

各頂点 \(i\) の次数が \(d_i\) であるような \(K_n\) の全域木の全体の集合を \(\mathcal{T}\) とします.

また,頂点 \(n\) はほかの 1 つの頂点とのみ隣接するので,\(\mathcal{T}\) のうち頂点 \(n\) が頂点 \(j\) と隣接しているような全域木を \(\mathcal{T}_j\) とすると,

\begin{align}
\mathcal{T} = \mathcal{T}_1\sqcup\mathcal{T}_2\sqcup\cdots\sqcup\mathcal{T}_{n-1} \tag{1}
\end{align}

と書けます.

(記号 \(\sqcup\) は,\(\mathcal{T}_1, \ldots, \mathcal{T}_{n-1}\) に重複がないような和集合であるという意味です).

さて,\(\mathcal{T}_j\) に含まれる木から頂点 \(n\) と,頂点 \(n\) に接続する枝を取り除いたものは \(K_{n-1}\) の全域木になっており,その次数列は

\[d_1, d_2, \ldots, d_{j-1}, d_j-1, d_{j+1}, \ldots, d_{n-1}\]

となります.

この次数列をもつ \(K_{n-1}\) の全域木全体を \(\mathcal{T}^\prime_j\) とすると,\(\mathcal{T}_j\) の木と \(\mathcal{T}^\prime_j\) の木には 1 対 1 対応が得られたことになるので,帰納法の仮定から,

\begin{align*}
|\mathcal{T}_j| &= |\mathcal{T}^\prime_j|\\
&= \dfrac{(n-3)!}{(d_1-1)!(d_2-1)!\cdots(d_{j-1}-1)!(d_j-2)!(d_{j+1}-1)!\cdots(d_{n-1}-1)!}\\
&= \dfrac{(n-3)!(d_j-1)}{(d_1-1)!(d_2-1)!\cdots(d_{n-1}-1)!}
\end{align*}

よって,(1)式から,次数列が \(d_1, d_2, \ldots, d_n(=1)\) である全域木の総数は,

\begin{align*}
|\mathcal{T}| &= \sum_{j=1}^{n-1}|\mathcal{T}_j|\\
&= \sum_{j=1}^{n-1} \dfrac{(n-3)!(d_j-1)}{(d_1-1)!(d_2-1)!\cdots(d_{n-1}-1)!}\\
&= \dfrac{(n-3)!}{(d_1-1)!(d_2-1)!\cdots(d_{n-1}-1)!}\sum_{j=1}^{n-1} (d_j-1)\\
&= \dfrac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_{n-1}-1)!}
\end{align*}

ここで,\(d_1+d_2+\cdots+d_{n-1}=2n-2-d_n=2n-3\) であることを用いています.

分母に \((d_n-1)! = 1\) を掛ければ命題 1. の式が得られます.

Cayley の定理の証明

あとは命題1. の右辺をすべての次数列について和を取ればよく,

\begin{align*}
T(K_n) &= \sum_{\substack{d_1, d_2, \ldots, d_n\geqq 1\\
d_1+d_2+\cdots+d_n=2n-2}} \dfrac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}\\
&= \sum_{\substack{k_1, k_2, \ldots, k_n\geqq 0\\k_1+k_2+\cdots+k_n=n-2}} \dfrac{(n-2)!}{k_1!k_2!\cdots k_n!}\\
&= n^{n-2}
\end{align*}

となります.

参考:J.マトウシェク/J.ネシェトリル 『離散数学への招待』

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加