行列木定理とCayleyの定理

行列木定理(Matrix-Tree Theorem)

無向グラフ GG に対して,GG の全域木の個数は,GG のラプラシアン行列の任意の余因子と等しい。

行列木定理の意味と証明,そして応用例として Cayley の定理の証明を紹介します。

行列木定理の意味

全域木の例

GG の全域木とは,GG のすべての頂点を含む木(閉路を含まない部分グラフ)です。→グラフ理論の基礎

GG のラプラシアンとは,各行,列がそれぞれ GG の頂点に対応しており,対角成分にはその頂点の次数,非対角成分については枝がある部分に 1-1,無い部分に 00 を格納した正方行列です。→隣接行列,接続行列,ラプラシアン行列

例えば,上図の GG のラプラシアンは (3111120110101102)\begin{pmatrix}3&-1&-1&-1\\-1&2&0&-1\\-1&0&1&0\\-1&-1&0&2\end{pmatrix} です。この 1111 余因子は, Δ11=det(201010102)=3\Delta_{11}=\det\begin{pmatrix}2&0&-1\\0&1&0\\-1&0&2\end{pmatrix}=3 です,実は GG の全域木の個数も 33 です。1212 余因子や 2323 余因子など,他の余因子もすべて 33 になります!

行列木定理の証明

以下の2つにわけて,証明します。

  1. ラプラシアン行列の ijij 余因子 Δij\Delta_{ij}i,ji,j によらず一定
  2. Δ11\Delta_{11}GG の全域木の個数と同じ
1の証明

Δ11=Δ12\Delta_{11}=\Delta_{12} を示す。他の余因子が等しいことも同様に示せる。

わかりやすさのために n=5n=5 の場合で示す。一般の nn でも同様。

Δ11=det(d2a23a24a25a23d3a34a35a24a34d4a45a25a35a45d5)\Delta_{11}=\det\begin{pmatrix}d_2&a_{23}&a_{24}&a_{25}\\a_{23}&d_3&a_{34}&a_{35}\\a_{24}&a_{34}&d_4&a_{45}\\a_{25}&a_{35}&a_{45}&d_5\end{pmatrix} である。ただし,did_i は頂点 ii の次数である。1列目に1列目以外の各列を加えることで, Δ11=det(a12a23a24a25a13d3a34a35a14a34d4a45a15a35a45d5)\Delta_{11}=\det\begin{pmatrix}-a_{12}&a_{23}&a_{24}&a_{25}\\-a_{13}&d_3&a_{34}&a_{35}\\-a_{14}&a_{34}&d_4&a_{45}\\-a_{15}&a_{35}&a_{45}&d_5\end{pmatrix} となる(もとのラプラシアン行列で各行の和が 00 であることを使った) これはまさに符号まで含めて Δ12\Delta_{12} である。

次に2です。行列式に関するビネ・コーシーの定理を使います。少し難しいですがとてもおもしろいです。

2の証明

GG の点枝接続行列を EE とする。ただし,i<ji<j なる頂点 i,ji,j 間に枝があるとき,ii 側の要素は 11jj 側の要素は 1-1 とする。 行列木定理の証明 例えば,図の例だと E=(1110100101000011)E=\begin{pmatrix}1&1&1&0\\-1&0&0&1\\0&-1&0&0\\0&0&-1&-1\end{pmatrix} である。行数=GG の頂点数,列数=GG の枝数となる行列である。例えば EE の3行目より,頂点1と4を結ぶ枝(e3e_3)があることがわかる。EE とラプラシアン LL の定義より,L=EEL=EE^{\top} となる。よって,EE の1行目を除いた行列を EE' とすると, Δ11=detEE\Delta_{11}=\det E'E'^{\top} となる。右辺にビネ・コーシーの定理を使うと, Δ11=Sdet(E[S])det(E[S])=Sdet(E[S])2\Delta_{11}=\displaystyle\sum_{S}\det(E'[S])\det(E'^{\top}[S])=\displaystyle\sum_{S}\det(E'[S])^2 となる。ただし,SS は枝のラベル {1,2,3,...,n}\{1,2,3,...,n\} から V1|V|-1 個(V|V|GG の頂点数)選んだ集合全体を動く。

つまり,SS により GG の枝が V1|V|-1 個決まるが,

  • これらが全域木をなさない,つまり閉路を含むとき det(E(S))=0\det(E'(S))=0 である。 実際,頂点1を含まない閉路があるときは,E(S)=(110101011)E'(S)=\begin{pmatrix}1&1&0\\-1&0&1\\0&-1&-1\end{pmatrix} のように,行和が 00 ベクトルになるので行列式が 00。頂点1を含む閉路があるときは,頂点1以外に孤立点があり,E(S)E'(S) のその行はすべて 00 なので行列式は 00
  • これらが全域木をなすとき,det(E(S))=±1\det(E'(S))=\pm 1 である。 実際,E(S)=(101001010)E'(S)=\begin{pmatrix}-1&0&1\\0&0&-1\\0&-1&0\end{pmatrix} などとなるが,置換による行列式の定義を考えたとき,00 を選ばない置換がただ1つになる。もう少し詳しく言うと「木は次数1の頂点を2つ以上含む(頂点1以外で次数1のものが存在する)」ことと「木から次数1の頂点を1つ除いても木のまま」であることから,00 を選ばない置換を構成しようとするとただ1つになる。

よって,Δ11\Delta_{11}GG の全域木の個数と等しい。

Cayley の定理

Cayley の定理

nn 個の(ラベル付き)頂点を持つ木の個数は T(n)=nn2T(n)=n^{n-2}

Cayleyの定理の例 例えば n=4n=4 のときは図のように 1616 通りです。たしかに 424^2 になっています。

行列木定理を使って証明できます。

証明

わかりやすさのために n=5n=5 で計算する。一般の nn でも同様。

頂点数 55 の完全グラフに行列木定理を使うと

T(5)=det(4111141111411114)T(5)=\det\begin{pmatrix}4&-1&-1&-1\\-1&4&-1&-1\\-1&-1&4&-1\\-1&-1&-1&4\end{pmatrix}

1行目以外の各行から1行目を引くことで, T(5)=det(4111550050505005)T(5)=\det\begin{pmatrix}4&-1&-1&-1\\-5&5&0&0\\-5&0&5&0\\-5&0&0&5\end{pmatrix}

1列目以外の各列を1列目に加えることで, T(5)=det(1111050000500005)T(5)=\det\begin{pmatrix}1&-1&-1&-1\\0&5&0&0\\0&0&5&0\\0&0&0&5\end{pmatrix}

上三角行列の行列式は対角成分の積なので T(5)=53T(5)=5^3 と等しい。

行列木定理を使わず直接 Cayley の定理を証明する方法もたくさんあります。

参考文献:Kirchhoff’s theorem

大学院の授業の演習問題で Cayley の定理の証明が出題されて,全く歯が立たなかった記憶があります。