blogoid

blogのようなもの

行列木定理の証明

0. はじめに

今回は行列木定理(Kirchhoff's theorem)の証明を紹介してみようと思います。

行列木定理とは、全域木の個数の数え上げに関する定理です。証明方法はいくつかありますが、今回は漸化式を用いた全域木の個数の数え上げとの対応を見ることで定理を証明してみたいと思います。

1. 定理の内容

頂点数$n$のループを含まない多重無向グラフ$G$が与えられたとします。対角成分に頂点の次数を並べた行列から、隣接行列*1を引いたものをラプラシアン行列といいます。つまり、$G$に対する$n$×$n$ラプラシアン行列$L=(l_{ij})$は$$\begin{aligned}l_{ij}=\begin{cases}\text{頂点iの次数}&(i=j)\\ \text{頂点iと頂点jの間の辺の数}\times (-1)&(\mathrm{otherwise}) \end{cases} \end{aligned} $$と定義されます。

ここで、実はラプラシアン行列とグラフの全域木の個数には以下のような関係があります。

定理:行列木定理(Kirchhoff's theorem)

グラフの全域木の個数は、ラプラシアン行列の任意の余因子(つまり任意の$i$行$j$列を除いた$(n-1)\times (n-1)$小行列式に$(-1)^{i+j}$をかけたもの)に等しい。

つまり、行列式を計算するだけで全域木の個数がわかるという定理です。便利ですね。ついでに全域木の個数の数え上げが多項式時間でできるということもわかるので(行列式の計算は多項式時間で可能)、そういう意味でも意義がありますね。

 

2. 漸化式を用いた全域木の個数の数え上げ

 ここで行列木定理を証明する準備として、グラフの全域木の個数を漸化式を用いて数える方法を考えていきたいと思います。

グラフ$G$のある辺$e$に着目します。$G$の全域木は、$e$を含むものと含まないものに分けられます。

ここで、$e$を含む全域木の個数は、$G$において$e$を縮約したグラフ$G/e$の全域木の個数に等しく、$e$を含まない全域木の個数は、$G$から$e$を削除したグラフ$G\setminus e$の全域木の個数に等しいです。なぜかというと、$G$の$e$を含む全域木は、それから$e$を除いた$G/e$における全域木と一対一対応していて、$G$の$e$を含まない全域木は、$G\setminus e$における同じ全域木と一対一対応しているからです(下図参照)。

 

f:id:mizuwater0:20181123235909p:plain

つまり、グラフ$G$の全域木の個数を$T(G)$と表すと、次のような関係式が成り立ちます。$$T(G)=T(G/e)+T(G\setminus e)$$

この漸化式*2を用いると、全域木の個数を数え上げることができます、すごい!!...という話ではなく(もちろん指数時間)、この漸化式は行列木定理の証明に役立ちます。その活躍は次節で見ていきましょう。

3. 定理の証明

 いよいよ行列木定理の証明です。

まずはラプラシアン行列の対角成分に対する余因子が全域木の個数と一致することを示していこうと思います。2.で紹介した漸化式を用いて帰納法的に示していきます。

まずグラフ$G$の頂点数が2個の場合を考えます。このとき、2頂点間の辺の数を$d$とすると、ラプラシアン行列$L$は$$L = \left( \begin{array}{cc} d & -d \\ -d & d \end{array} \right) $$となります。これの余因子は$d$であり、全域木の個数と一致するからOKです。

次にグラフの頂点数が2以上で辺がない場合を考えます。このとき、ラプラシアン行列$L$は零行列になるので、余因子も0となります。一方全域木の個数も0なので、余因子と全域木の個数が一致してOKです。

さて、今度は一般の$n$頂点グラフ$G$の場合について考えてみます。$G$のラプラシアン行列$L$は、$G$の頂点$i$の次数を$d_i$と表し、隣接行列を$A=(a_{ij})$と表すことで$$L = \left( \begin{array}{cccc} d_1 & -a_{12} & \ldots & -a_{1n} \\ -a_{21} & d_2 &\ldots & -a_{2n} \\ \vdots &\vdots & \ddots & \vdots \\ -a_{n1} & -a_{n2} & \ldots& d_n \end{array} \right)$$となります。

ここで$L$の$(1,1)$成分に対する余因子$L_{11}$は$$L_{11} = \left| \begin{array}{cccc} d_2 & -a_{23} & \ldots & -a_{2n} \\ -a_{32} & d_3 & \ldots & -a_{3n} \\ \vdots & \vdots & \ddots & \vdots \\ -a_{n2} & -a_{n3} & \ldots & d_n \end{array} \right| $$です。

ここでもし、頂点1からほかの頂点への辺が存在しないとすると、$L$の1行目が$0$となるので、$L_{11}$のすべての行の和が$0$になり、$L_{11}=0$です。このとき同時に全域木の個数も0個なので、$L_{11}$と全域木の個数が一致しOKです。

今度は頂点1からほかの頂点への辺が存在した場合を考えます。頂点1から頂点iへの辺が存在したとします。この辺を$e$とおきます。このとき、$$\begin{aligned} L_{11}&=\left| \begin{array}{cccccccc} d_2 & -a_{23} & \ldots &-a_{2{i-1}} & -a_{2i} & -a_{2{i+1}} & \ldots & -a_{2n} \\ -a_{32} & d_3 & \ldots & -a_{3{i-1}} & -a_{3i} & -a_{3{i+1}} & \ldots & -a_{3n}\\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ -a_{i2} & -a_{i3} & \ldots & -a_{i{i-1}} & d_i & -a_{i{i+1}} & \ldots & -a_{in} \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ -a_{n2} & -a_{n3} & \ldots & -a_{n{i-1}} & -a_{ni} & -a_{n{i+1}} & \ldots & d_n \end{array} \right|\\\\ &=\left| \begin{array}{cccccccc} d_2 & -a_{23} & \ldots &-a_{2{i-1}} & 0 & -a_{2{i+1}} & \ldots & -a_{2n} \\ -a_{32} & d_3 & \ldots & -a_{3{i-1}} & 0 & -a_{3{i+1}} & \ldots & -a_{3n}\\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ -a_{i2} & -a_{i3} & \ldots & -a_{i{i-1}} & 1 & -a_{i{i+1}} & \ldots & -a_{in} \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ -a_{n2} & -a_{n3} & \ldots & -a_{n{i-1}} & 0 & -a_{n{i+1}} & \ldots & d_n \end{array} \right| \\\\ &+\left| \begin{array}{cccccccc} d_2 & -a_{23} & \ldots &-a_{2{i-1}} & -a_{2i} & -a_{2{i+1}} & \ldots & -a_{2n} \\ -a_{32} & d_3 & \ldots & -a_{3{i-1}} & -a_{3i} & -a_{3{i+1}} & \ldots & -a_{3n}\\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ -a_{i2} & -a_{i3} & \ldots & -a_{i{i-1}} & d_i-1 & -a_{i{i+1}} & \ldots & -a_{in} \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ -a_{n2} & -a_{n3} & \ldots & -a_{n{i-1}} & -a_{ni} & -a_{n{i+1}} & \ldots & d_n \end{array} \right| \end{aligned} $$と第i列について分解します。つまり、$L_{11}$を、第i列の第i成分が1、それ以外が0のものと、その残りに分解します。すると、実はこれらは、それぞれ$G/e$から自己ループを除いたグラフ($\tilde{G/e}$とおく)のラプラシアン行列の余因子*3と、$G\setminus e$のラプラシアン行列の余因子になっています。実際に確認してみます。

まず前者について確認します。$\tilde{G/e}$のラプラシアン行列を$L'$とおくと、$${\scriptsize L'=\left( \begin{array}{cccccccc} d_1+d_i-2a_{1i} & -a_{12}-a_{i2} & -a_{13}-a_{i3} & \ldots & -a_{1{i-1}}-a_{i{i-1}} & -a_{1{i+1}}-a_{i{i+1}} & \ldots & -a_{1n}-a_{in}\\ -a_{21}-a_{2i} & d_2 & -a_{23} & \ldots &-a_{2{i-1}} & -a_{2{i+1}} & \ldots & -a_{2n} \\ -a_{31}-a_{3i} & -a_{32} & d_3 & \ldots & -a_{3{i-1}} & -a_{3{i+1}} & \ldots & -a_{3n}\\ \vdots & \vdots & \vdots & & \vdots & \vdots & & \vdots \\ -a_{{i-1}1}-a_{{i-1}i} & -a_{{i-1}2} & -a_{{i-1}3} & \ldots & d_{i-1} & -a_{{i-1}{i+1}} & \ldots & -a_{{i-1}n} \\ -a_{{i+1}1}-a_{{i+1}i} & -a_{{i+1}2} & -a_{{i+1}3} & \ldots & -a_{{i+1}{i-1}} & d_{i+1} & \ldots & -a_{{i+1}n} \\ \vdots & \vdots & \vdots & & \vdots & \vdots & & \vdots \\ -a_{n1}-a{ni} & -a_{n2} & -a_{n3} & \ldots & -a_{n{i-1}} & -a_{n{i+1}} & \ldots & d_n \end{array} \right)}$$です($\tilde{G/e}$の頂点1(第1行と第1列)が、$G$における頂点1と頂点iを一つの頂点にまとめたものに対応しています)。

一方、先ほど分解した2つの行列式のうちの1つ目は

$$\begin{aligned} & \left| \begin{array}{cccccccc} d_2 & -a_{23} & \ldots &-a_{2{i-1}} & 0 & -a_{2{i+1}} & \ldots & -a_{2n} \\ -a_{32} & d_3 & \ldots & -a_{3{i-1}} & 0 & -a_{3{i+1}} & \ldots & -a_{3n}\\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ -a_{i2} & -a_{i3} & \ldots & -a_{i{i-1}} & 1 & -a_{i{i+1}} & \ldots & -a_{in} \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ -a_{n2} & -a_{n3} & \ldots & -a_{n{i-1}} & 0 & -a_{n{i+1}} & \ldots & d_n \end{array} \right|= \\\\ & \left| \begin{array}{cccccccc} d_2 & -a_{23} & \ldots &-a_{2{i-1}} & -a_{2{i+1}} & \ldots & -a_{2n} \\ -a_{32} & d_3 & \ldots & -a_{3{i-1}} & -a_{3{i+1}} & \ldots & -a_{3n}\\ \vdots & \vdots & & \vdots & \vdots & & \vdots \\ -a_{{i-1}2} & -a_{{i-1}3} & \ldots & d_{i-1} & -a_{{i-1}{i+1}} & \ldots & -a_{{i-1}n} \\ -a_{{i+1}2} & -a_{{i+1}3} & \ldots & -a_{{i+1}{i-1}} & d_{i+1} & \ldots & -a_{{i+1}n} \\ \vdots & \vdots & & \vdots & \vdots & & \vdots \\ -a_{n2} & -a_{n3} & \ldots & -a_{n{i-1}} & -a_{n{i+1}} & \ldots & d_n \end{array} \right| \end{aligned} $$です。

これを見ると確かにこの行列式は$L'$の$(1,1)$成分に対する余因子になっています。

次に、分解した行列式のうちの2つ目が$G\setminus e$のラプラシアン行列の余因子になっていることを確認します。これは簡単に確認できます。$G\setminus e$のラプラシアン行列は、$G$のラプラシアン行列$L$の$(1,1)$成分と$(i,i)$成分をそれぞれ$d_1-1$、$d_i-1$とし、$(1,i)$成分、$(i,1)$成分をそれぞれ$-a_{1i}+1$、$-a_{i1}+1$としたものです。これを踏まえて分解した行列式のうちの2つ目を眺めてみると、確かにこれは$G\setminus e$のラプラシアン行列の成分$(1,1)$に対する余因子になっています。

ここで、$\tilde{G/e}$と$G\setminus e$に対して行列木定理が成り立っているとすると、先ほどの$L_{11}$を$\tilde{G/e}$のラプラシアン行列の余因子と$G\setminus e$のラプラシアン行列の余因子に分解した式から、$$L_{11}=T(\tilde{G/e})+T(G\setminus e)$$が成り立ちます。$\tilde{G/e}$が$G/e$から自己ループを除いたグラフであったことを思い出すと、全域木に自己ループは含まれないので、$\tilde{G/e}$と$G/e$の全域木の個数は等しいです。つまり、$$L_{11}=T(G/e)+T(G\setminus e)$$が成り立ちます。ここで、2.で紹介した漸化式を思い出すと、$$T(G)=T(G/e)+T(G\setminus e)$$なので、$$L_{11}=T(G)$$が成り立ちます。つまり、$L_{11}$が$G$の全域木の個数に等しいかどうかは、$\tilde{G/e}$と$G\setminus e$に対して行列木定理が(対角成分に対する余因子について)成り立つかどうかに帰着されます。ここで$\tilde{G/e}$と$G\setminus e$は、$G$よりも辺の数、もしくは辺と頂点両方の数が少ないです。成分$(2,2)$~$(n,n)$に対する余因子$L_{22}$~$L_{nn}$が$G$の全域木の個数に等しいかどうかも同様に、$G$よりも辺や頂点の数が少ないグラフに対して行列木定理が(対角成分に対する余因子について)成り立つかどうかに帰着されます。つまり、このようにどんどん辺の数や頂点の数が少ないグラフに対する行列木定理に帰着していけば、いつかは最初に示した辺がないグラフか頂点数が2個のグラフに帰着されるので、証明が完了したことになります。これで対角成分に対する余因子については行列木定理が示されました。

行列木定理を任意の余因子まで拡張するのはそんなに難しくないはずなので略します。概略だけ言うと、ラプラシアン行列の$(i,j)$成分に対する余因子は、$(i,i)$成分に対する余因子に等しいことが実は簡単に言えるので示せます(ラプラシアン行列のすべての列の和が$0$であることに着目すれば言えます)。

これで行列木定理の証明は終わりです。

 4. 参考文献

WikipediaのKirchhoff's theoremのページを参考にしました。

Kirchhoff's theorem - Wikipedia

行列木定理の証明としては一番有名(らしい)なCauchy Binetの定理を用いた証明も書いてあります。気になる方は参照されたし。

*1:ここでは多重グラフを考えているので、例えば頂点1と頂点2の間に2本辺があれば、隣接行列の(1,2)成分は2となります。

*2:これを一般化したものをtutte多項式と呼ぶらしいです。全然知らないのでそのうち勉強したい...

*3:本当は$G/e$のラプラシアン行列の余因子、と簡潔に言いたいところなのですが、自己ループのあるグラフに対してラプラシアン行列を定義すると、ラプラシアン行列の良い性質が崩れたりするので(自己ループをどう次数にカウントするかにもよりそうですが)、結局自己ループを除いたグラフを考えるのが楽ということでそうしました。