最大流最小カット定理のLP双対を用いた証明

今回は、グラフ理論分野における超有名定理、最大流最小カット定理の証明について書いてみようと思います。

最大流最小カット定理は証明方法がいくつかありますが、今回は線形計画法の双対を用いた証明を紹介します。この証明方法はFord-Fulkersonのアルゴリズムを用いた証明に比べるとやや煩雑ですが、線形計画問題と整数計画問題の間を行き来する例として勉強になる（？）証明方法です。

1. 線形計画法の復習

まずは線形計画問題の双対について復習です。次の線形計画問題が与えられたとします。

$\mathrm{(P)}$

$$\begin{aligned} \mathrm{max}\ \ &c^{\mathrm{T}}x\\ \mathrm{subject\ to}\ \ &Ax\leq b \end{aligned}$$

これの双対問題は以下のようになります。

$\mathrm{(D)}$

$$\begin{aligned} \mathrm{min}\ \ &b^{\mathrm{T}}y\\ \mathrm{subject\ to}\ \ &A^{\mathrm{T}}y=c\\ &y\geq 0\end{aligned}$$

実は、最大流問題と最小カット問題の双対も、これらの線形計画問題の双対に対応しています。つまり、最大流問題を線形計画問題として表すと、その双対をとった問題は最小カット問題となっているのです！このことを示せば、線形計画問題では主問題と双対問題の最適値が等しい*1ことから、最大流最小カット定理を示すことができます。

2. 最大流最小カット定理の証明

では、最大流最小カット定理を証明していきましょう。任意の有向グラフ$G=(V, A)$と、始点$s$、終点$t$が与えられたとします。各辺$(i, j)\in A$の容量を$c_{ij}$とします。この$G$に十分大きな容量$c_{ts}$を持つ有向辺$(t, s)$を付け加えたグラフを$\tilde{G}$とします。すると、最大流問題は、$\tilde{G}$のすべての頂点で流れ込む流量と出ていく流量が等しくなるようなフローを考えたときに、そのようなフローがとりうる辺$(t, s)$の流量の最大値を求める問題に言い換えることができます。

さて、$\tilde{G}$の接続行列*2を$N$、$\tilde{G}$の各辺$(i, j)$の容量$c_{ij}$を並べたベクトルを$c=(c_{ij})\in R^{|A|+1}$とします。また、各辺$(i, j)$の流量を$x_{ij}$とし、$x_{ij}$を並べたベクトルを$x=(x_{ij})\in R^{|A|+1}$とします。このとき、最大流問題（を先ほど言い換えた問題）は以下のように表現できます。

 $\mathrm{(P)}$

$$\begin{aligned} \mathrm{max}\ \ &x_{ts}\\ \mathrm{subject\ to}\ \ &Nx=0\\ &0\leq x\leq c\end{aligned}$$

 これを少し変形すると以下のようになります。

$\mathrm{(P)}$

$$\begin{aligned} \mathrm{max}\ \ &x_{ts}\\ \\ \mathrm{subject\ to}\ \ &\left( \begin{array}{ccccc} N \\ -N \\ -I \\ I \end{array} \right) x\leq \left(\begin{array}{c} 0 \\ 0 \\ 0 \\ c \end{array} \right) \end{aligned}$$

これの双対問題は次のようになります。

$\mathrm{(D)}$

$$\begin{aligned} \mathrm{min}\ \ &\left( \begin{array}{ccccc} 0 \\ 0 \\ 0 \\ c \end{array} \right)^{\mathrm{T}} \! \! \! y \\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} \ -N^{\mathrm{T}} \ -I \ \ \ I \end{array} \right)y=e \\ \\ &y\geq 0 \end{aligned}$$

ただし、$e$は各成分が$\tilde{G}$の各辺に対応している$|A|+1$次元ベクトルであり、辺$(t, s)$に対応する成分は1で、それ以外の成分は0となっています。

 ここで、$y$を$-N^{\mathrm{T}}$、$N^{\mathrm{T}}$、$-I$、$I$のそれぞれに対応する部分ごとに分ける、つまり

$$y=\begin{aligned} \left( \begin{array}{ccccc} y_1 \\ y_2 \\ y_3 \\ y_4 \end{array} \right) \end{aligned}$$

と分けます（$y_1, y_2\in R^{\mathrm{|V|}}$、$y_3, y_4\in R^{\mathrm{|A|+1}}$）。

すると、$\mathrm{(D)}$は

 $\mathrm{(D)}$

$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4\\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} \ -N^{\mathrm{T}} \ -I \ \ \ I \end{array} \right)\ \left( \begin{array}{ccccc} y_1 \\ y_2 \\ y_3 \\ y_4 \end{array} \right)=e \\ \\ &\left( \begin{array}{ccccc} y_1 \\ y_2 \\ y_3 \\ y_4 \end{array} \right)\geq 0 \end{aligned}$$

となります。

さらに、$z=y_1-y_2$とおくと、$\mathrm{(D)}$は以下のようになります。

 $\mathrm{(D)}$

$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4\\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} \ -I \ \ \ I \end{array} \right)\ \left( \begin{array}{ccccc} z \\ y_3 \\ y_4 \end{array} \right)=e \\ \\ &\left( \begin{array}{ccccc} y_3 \\ y_4 \end{array} \right)\geq 0 \end{aligned}$$

つまりこれは

 $\mathrm{(D)}$

$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4\\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} \ \ I \end{array} \right)\ \left( \begin{array}{ccccc} z \\ y_4 \end{array} \right)\geq e \\ &y_4\geq 0 \end{aligned}$$

と変形できて、さらに

 $\mathrm{(D)}$

$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4\\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} &I \\ 0 &I \end{array} \right)\ \left( \begin{array}{ccccc} z \\ y_4 \end{array} \right)\geq \left( \begin{array}{ccccc} e \\ 0 \end{array} \right)  \end{aligned}$$

と変形できます。

さて、この問題$\mathrm{(D)}$が最小カット問題となっていることを説明しましょう。

まず、$\mathrm{(D)}$の制約条件の式は$2(|A|+1)$本ありますが、そのすべてを満たす部分は多面体の内部となります。この多面体の任意の頂点は、$\begin{aligned} &\left( \begin{array}{ccccc} N^{\mathrm{T}} &I \\ 0 &I \end{array} \right) \end{aligned}$が完全単模行列*3*4であることから、座標がすべて整数となります（いくつかの平面の式をまとめて$Ax=b$と表したとき、これらが交わってできる頂点は$x=A^{-1}b$によって求められることを思い出せばわかります）。そして、$\mathrm{(D)}$で最小値を達成するのは、制約条件が表す多面体の頂点のいずれかにおいてなので、$\mathrm{(D)}$の最適解は整数ベクトルとなります。

さて、$\mathrm{(D)}$を整数計画問題に言い換えられたところで、以下のように書き換えます。

$\mathrm{(D')}$

$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4 \\ \\ \mathrm{subject\ to}\ \ &N^{\mathrm{T}}z+y_4 \geq e \\ &y_4 \geq 0 \\ &y_4\in Z^{\mathrm{|A|+1}},\ z\in Z^{\mathrm{|V|}} \end{aligned}$$

 ここで、頂点$i$に対応する$z$の成分を$z_i$と表し、辺$(i, j)$に対応する$y_4$の成分を$y_{4(i, j)}$と表すことにします。すると、$c_{ts}$が十分大きいことから、$y_{4(t, s)}$は0になる、つまり$$z_t-z_s \geq 1$$が成り立ちます（$e$の辺$(t, s)$に対応する成分は1であることに注意）。これを踏まえて、以下のように頂点集合$U$、$W$を定義します:$$\begin{aligned} \ &U=\{ u\in V\ |\ z_u \leq z_s\} \\ &W=\{ w\in V\ |\ z_s+1 \leq z_w\} \end{aligned}$$

 このとき、$U, W$は$V$の分割であり、また$s\in U$、$t\in W$なので、$U, W$は$s, t$を分けるカットとなっています。ここで、$u\in U, w\in W$を満たす辺$(u, w)$について、$$z_u-z_w \leq -1$$なので、$$y_{4(u, w)} \geq -z_u+z_w \geq 1$$が成り立ちます。よって、$$c^{\mathrm{T}}y_4 \geq \sum_{u\in U, w\in W} c_{uw}$$が成り立ちます。ここで、$\sum_{u\in U, w\in W} c_{uw}$は$\tilde{G}$の$U, W$によるカットの容量です。つまり、$c^{\mathrm{T}}y_4$は$\tilde{G}$の最小カットの容量によって下から抑えられることがわかります。一方で、$\tilde{G}$のある最小カット$U, W(s\in U, t\in W)$に対して、$z, y_4$を$$\begin{aligned}z_i &= \begin{cases} 0 &(i\in U) \\ 1&(i\in W) \end{cases} \\ \\ y_{4(i, j)}&=\begin{cases}1&(i\in U, j\in W) \\ 0&(\mathrm{otherwise}) \end{cases} \end{aligned}$$と定めれば、$c^{\mathrm{T}}y_4$は最小カット$U, W$の容量となります。ゆえに、$\mathrm{(D')}$は$\tilde{G}$についての最小カット問題（＝$G$についての最小カット問題）と等価であり、つまり最大流問題を線形計画問題として表したものの双対をとると、最小カット問題となることが示されました。

*1:ただし主問題か双対問題に実行可能解がない場合は除きます。

*2:ここでは有向グラフ$\tilde{G}$を考えているので、接続行列の成分$(i, j)$は、頂点$i$が第$j$列に対応する有向辺の始点であれば1、終点であれば-1、どちらでもなければ0となります。

*3:完全単模行列とは、任意の部分正方行列の行列式が0、-1、1のいずれかであるような行列のことです。

*4:$\begin{aligned} &\left( \begin{array}{ccccc} N^{\mathrm{T}} &I \\ 0 &I \end{array} \right) \end{aligned}$が完全単模行列であることは、接続行列$N$が完全単模行列であることからわかります。接続行列が完全単模行列であることの証明は、例えばhttp://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-surikeikakuhou/integerprogunimod101222.pdfに載っています。

4-リスト彩色不可能な平面グラフ

 どんな平面グラフも4彩色*1可能という事実は、四色定理という名で広く知られています。では、4彩色を少し拡張した概念である、4リスト彩色については任意の平面グラフに対して可能なのか？というのが今回の話です。

まず、リスト彩色とは以下のように定義されます。

定義（リスト彩色）

グラフ$G=(V,E)$の各頂点$v\in V$に対して色の集合（リスト）$S_v$が与えられたとする。このとき、各頂点$v\in V$の色をリスト$S_v$から選んで塗り、隣り合う頂点が異なる色で塗られているとき、これをリスト$S_v$を用いた彩色とよぶ。各頂点$v\in V$に対して大きさ$k$であるどんなリスト$S_v(\forall v\in V\ |S_v|=k)$が与えられても、$G$が$S_v$を用いて彩色できるとき、$G$は$k-$リスト彩色可能、または$k-$選択可能*2という。

 

通常の彩色では、すべての頂点について同じ色の集合から色を選んで塗りますが、リスト彩色では頂点ごとに選ぶ色の集合を変えることを考えます。$k-$リスト彩色可能なグラフはすべての頂点に同じ$k$色の集合を与えられてもその集合から色を選んで彩色できる（つまり通常の彩色ができる）ので、彩色よりもリスト彩色のほうが強い概念です。

しかし、直感的には頂点ごとに選ぶ色の集合を変えたほうが彩色しやすくなるのではないか、$k-$彩色が可能なグラフは$k-$リスト彩色も可能なのではないか、と思ったりもするかもしれません。

 実際、任意の平面グラフは5彩色可能ですが、5-リスト彩色も可能です。

しかし、四色定理のリスト彩色版は実は成り立ちません。つまり、4-リスト彩色不可能な平面グラフが存在するのです！

4-リスト彩色不可能な平面グラフの例は色々ありますが、その中でも比較的頂点数が少ないシンプルなもの（といっても63頂点ありますが）を以下で紹介します。Mirzakhani graph*3 と呼ばれるグラフです。

上のほうに1つだけポツンとある頂点からは、各正方形の真ん中の頂点（次数4の頂点）を除いたすべての頂点に辺がのびています。このグラフが平面グラフであることはすぐに確認できます。では、Mirzakhani graphが4-リスト彩色可能でないことを実際に確認していきましょう。

Mirzakhani graphの各頂点に下図のような色（色は数字で表すことにします）のリストを与えます。ただし、$L_i=\{1,2,3,4,5\}\setminus \{i\}$とします。

 このリストを用いた彩色が不可能なことを示します。

上のほうに1つだけポツンとある頂点（最大次数頂点）の色が1であったとします。このとき、正方形の中心にある頂点のリストが$L_1$であるような5つの正方形（とその中心）からなる部分グラフをとってきます（左下図）。

 この部分グラフの頂点に、右上図のように名前をつけます。

まず、正方形の中心の頂点のリストはすべて$L_1$なので、正方形の4つの角にある頂点が2,3,4,5すべてを網羅すると中心の頂点が塗れなくなります。また、正方形の4つの角にある頂点は最大次数頂点に隣接しているので、1で塗ることはできません（この事実は以降暗黙のうちに使っていきます）。ゆえに、正方形の4つの角にある頂点のうち同じ色で塗られている2頂点が少なくとも1組あります。

ここで、ある1直線にならんだ5頂点のうちの正方形の中心を除いた3頂点（例えばb,d,hなど）をすべて同じ色で塗ると矛盾することを示します。例えばb,d,hが同じ色で塗られたとします。b,d,hの色のリストはそれぞれ$L_2,L_3,L_5$なので、b,d,hを同じ色で塗るには4で塗るしかありません。このとき真ん中の正方形に着目すると、kのリストは$L_4$なのでd,kを同じ色で塗ることはできません。よってe,iが同じ色で塗られることになります。e,iのリストは$L_5,L_2$で、4で塗られたdに隣接しているので、e,iの色は3となります（下図）。

ここで右と下の正方形に着目すると、n,qのリストは$L_3$なのでn,qは3で塗ることができません。よってlとk、kとpが同じ色で塗られることになり、つまりl,k,pが同じ色で塗られることになります。l,k,pのリストは$L_2,L_4,L_5$なので、l,k,pを同じ色で塗るには3で塗るしかありません。しかしこれでは同じ色の頂点が隣接するので矛盾します。

ほかの1直線上にならんだ5頂点のうち正方形の中心を除いた3頂点をすべて同じ色で塗っても、同様に矛盾が示せます。

よって、以下では上で考えたような3頂点がすべて同じ色で塗られる場合は除いて考えます。まず、左の正方形に着目して、aとeが同じ色で塗られているとします。このとき、下の正方形に着目します。eとnが同じ色で塗られるとすると、上で考えたような組み合わせの3頂点がすべて同じ色で塗られることになるのでダメで、ゆえにlとkが同じ色で塗られていることになります。同様に右の正方形と上の正方形にも着目すると、iとq、dとhが同じ色で塗られていることになります（下図）。

ここで、真ん中の正方形に着目すると、dとk、eとiのうち少なくともどちらかが同じ色で塗られている必要があります。dとkが同じ色で塗られていたとすると、l,k,d,hがすべて同じ色で塗られていることになります。しかしl,k,d,hのリストは$L_2,L_4,L_3,L_5$なので、l,k,d,hを同じ色で塗るには1で塗る必要があり、これは1で塗られている最大次数頂点と隣接していることと矛盾します。

左の正方形でbとdが同じ色で塗られている場合も同様に矛盾を示すことができます。よって、最大次数の頂点の色が1である場合は彩色できないことが示されました。

最大次数の頂点の色が2,3,4の場合も、中心の頂点のリストが$L_2,L_3,L_4$であるような正方形からなる部分グラフをとってきて、同じような議論をすれば矛盾を示せます。

よって、上で与えたようなリストを用いてMirzakhani graphは彩色できないので、Mirzakhani graphは4-リスト彩色不可能であることが示されました。

ちなみに、Mirzakhani graphは3彩色も可能な平面グラフです（各正方形の真ん中の頂点と、上に一つだけある頂点をすべて同じ色で塗って、残りは偶数長閉路なので2色で塗れる）。3彩色可能なのに4-リスト彩色はできないというのは直感に反して面白いですね。

*1:辺で結ばれた任意の2頂点が異なる色で塗られているような頂点の色の塗り方を彩色といいます。

*2:英語のchoosable（リスト彩色可能）の訳語です。リストから色を「選ぶ」というイメージなんですかね。

*3:女性初のフィールズ賞受賞者、Maryam Mirzakhaniの名を冠したグラフです。

木幅と線形時間アルゴリズム

今回は木幅（tree-width）の話を書いてみようと思います。

木幅とは、大雑把に言うとグラフがどれだけ木に近いかを表す値です（木に近いほど小さな値になります）。NP困難な問題でもグラフを木に限定すると多項式時間で解けたりする話は有名ですが、実は一部のNP困難な問題は、グラフの木幅が定数で上から抑えられるなら、なんと線形時間で解くことができます！

今回はそのようなNP困難問題の一つである最大独立集合問題を取り上げて、木幅が定数で抑えられるときの線形時間アルゴリズムを紹介することを目標に記事を書いていこうと思います。

1. 木分解と木幅

 木幅を定義する前に、まずは木分解（tree-decomposition）を定義します。木分解とは、グラフを木構造として表現したものです。ちなみにグラフは無向グラフのみを考えます。

定義（木分解）

 グラフ$G=(V,E)$に対して、頂点集合$V$の部分集合族$X=\{X_1, X_2, ..., X_k\}$と$X_1, X_2, ..., X_k$を節点として持つ木$T$の組$(X,T)$であって、以下を満たすものを$G$の木分解という。

1. $X_i(i=1, 2, ..., k)$の和集合は$V$
2. $G$において辺で結ばれている任意の2点$(u,v)$に対して、$u$、$v$を両方とも含む$X_i$が存在する
3. $G$の任意の頂点$v\in V$に対して、$v$を含む$X_i$全体は$T$上で連結

 イメージとしては、$G$の各頂点$v$に、$v$を含む$X_i$全体がなす$T$の部分木が対応しています。$G$で頂点$u$と$v$の間に辺があるなら、$u$に対応する$T$の部分木と$v$に対応する$T$の部分木が交わりを持つ（つまり$u$、$v$を両方含む$T$の節点$X_i$が存在する）という構造になっています。

例を見てみます。

左が元のグラフ、右が左のグラフの木分解です。先ほどの木分解の定義の1~3を満たしていることが確認できます。

木分解が定義できたので、今度は木分解の幅と、グラフの木幅を定義します。

定義（幅、木幅）

 グラフ$G$のある木分解$(X,T)$の幅とは、$\max_{X_i\in X}|X_i|-1$のことである*1。また、グラフ$G$の木幅tw$(G)$とは、$G$の全ての木分解の幅のうちの最小値である。

例えば、上の例における木分解の幅は2です。また、上の例におけるグラフは実は木幅も2です（つまり上に描いた木分解は幅が最小の木分解です）。

一般のグラフの木幅をすぐに求めるのは難しいですが、グラフクラスを限定すると木幅がすぐにわかったりします。例えば木の木幅は1であり（逆に連結なグラフで木幅が1なら木です）、また外平面的グラフ*2の木幅は2以下です。これを聞くと、確かに木幅が小さいほど木に近いグラフであるような気分になりますね*3。

さて、実は与えられたグラフの幅最小の木分解を求めるのはNP困難問題です。ですが、木幅が定数で上から抑えられるなら、以下のBodlaenderの定理を用いて（$|V|$に関する）線形時間で幅最小の木分解を求めることができます。

定理（Bodlaender 1996）

各定数$t$に対して、以下を（$t$を定数と見たときに）$O(|V|)$時間で行える。

入力として与えられたグラフ$G=(V,E)$に対して、その木幅が$t$以下であるか否かを判定し、もし$t$以下なら幅$t$以下の木分解を構成する。

 与えられたグラフ$G$の木幅が定数$l$で上から抑えられるとします。このとき、Bodlaenderの定理を$t=1,2,...,l$について順番に$G$に適用するか二部探索すれば、幅最小の木分解を（$l$を定数とみると）合計$O(|V|)$時間で得ることができます。これで幅最小の木分解を求める線形時間アルゴリズムが得られました。

（木幅が定数で抑えられるグラフに対する）最大独立集合問題の線形時間アルゴリズムも、この幅最小の木分解を求める線形時間アルゴリズムを使っています。このことは次の章以降で紹介していきます。

 2. Nice Tree-decomposition

 さて、グラフの幅最小の木分解が得られたとします。この木分解上でDPをまわすことで最大独立集合が求められるのですが、そのままDPをすると割と面倒です。そこでnice tree-decomposition と呼ばれるDPがしやすい木分解にあらかじめ変形しておいて、その木分解上でDPをまわす、ということがよく行われます*4。というわけで、この章では木分解上のDPを紹介する前にnice tree-decompositionを紹介しようと思います。

nice tree-decompositionとは、DPがしやすいように単純な構造しか持たないようにした木分解です。

定義（Nice Tree-decomposition）

nice tree-decompositionとは、木分解$(X,T)$で、$T$をある節点を根とした根付き木とみたときに以下を満たすもの*5。

1. 全ての$X_i\in X$は高々2つの子しか持たない
2. $X_i$が2つの子$X_j$、$X_k$を持つなら、$X_i=X_j=X_k$が成り立つ
3. $X_i$が1つの子$X_j$を持つなら、$G$のある頂点$v\in V$が存在して$X_i=X_j\cup \{v\}$または$X_i=X_j\setminus \{v\}$が成り立つ

2.を満たす$X_i$のことをjoin、3.を満たす$X_i$のうち$X_i=X_j\cup \{v\}$を満たすものをintroduce、$X_i=X_j\setminus \{v\}$を満たすものをforgetと呼びます。 

例えば、木分解の定義の後で例に挙げたグラフのnice tree-decompositionは以下のようになります（一意ではありません）。

 さて、（木幅が定数で抑えられるグラフに対して）幅最小の木分解が$O(|V|)$時間で得られることは前の章で説明しましたが、実はある木分解$(X,T)$から同じ幅のnice tree-decompositionを得ることも（幅を定数として）$O(|X|)$時間で可能です。

補題

グラフ$G$の木分解$(X,T)$に対して、同じ幅のnice tree-decompositionを（幅を定数として）$O(|X|)$時間で得ることができる。

証明)

与えられた木分解を$(X,T)$とする。まず、$T$の適当な節点$X_r\in X$を根と定めて、$T$を根付き木として見る。次に、以下の3ステップの操作により$T$を変形することで、同じ幅のnice tree-decompositionを構成する。

1.  3つ以上子を持つ節点の子を2つに減らす
2. 節点$X_i$が2つの子$X_j$、$X_k$を持ち、$X_i=X_j=X_k$が成り立たない場合、$X_i$の子を変える
3. 節点$X_i$が1つの子$X_j$を持ち、「$G$のある頂点$v\in V$が存在して$X_i=X_j\cup \{v\}$または$X_i=X_j\setminus \{v\}$が成り立つ」という関係が成り立たないとき、$X_i$と$X_j$の間に節点を追加する

 各ステップの操作を詳しく見ていく。

まず、ステップ1.について、ある節点$X_i$が3つ以上子を持っていたとする。$X_i$の親を$X_j$とする。このとき、$X_i$のコピーを新たにつくり、$X_j$と$X_i$の間に挿入する。また、$X_i$の子のうち、適当に1つ選んで親を$X_i$のコピーに変更する（下図参照）。

 

この変形は木分解の条件を保ち、また木分解の幅も変化しない。また、コピーのほうの$X_i$の子は2つであり、コピーでないほうの$X_i$の子はもともとの個数よりも1つ少なくなっている。つまり、$X_i$に対してこれと同じ変形をまた施し、これを（子が3つ以上の）すべての節点について帰納的に繰り返せば、有限回の変形によってすべての節点の子を2つ以下にすることができる。これによって増える節点の個数は$T$の辺の数以下なので、ステップ1.が終わった後の節点数は$O(|X|)$のままである。またステップ1.全体にかかる時間計算量は、幅を定数とみれば$O(|X|)$時間である。ステップ1.が完了すると、nice tree-decompositionの定義の1つ目の条件が満たされていることになる。

次にステップ2.について、節点$X_i$が2つの子$X_j$、$X_k$を持ち、$X_i=X_j=X_k$が成り立たないとする。このとき、新たに$X_i$のコピーを2つ作り、$X_i$と$X_j$、$X_i$と$X_k$の間にそれぞれ挿入する（下図参照）。

 この変形は木分解の条件を保ち、また木分解の幅も変化しない。この変形をステップ2.の条件に当てはまるすべての節点に対して行えば、nice tree-decompositionの定義の2つ目の条件が満たされることになる。ステップ2.全体で増える節点数、かかる時間計算量は幅を定数とみればともに$O(|X|)$である。

次にステップ3.について、節点$X_i$が1つの子$X_j$を持ち、「$G$のある頂点$v\in V$が存在して$X_i=X_j\cup \{v\}$または$X_i=X_j\setminus \{v\}$が成り立つ」という関係が成り立たないとする。$X_i\setminus X_j=\{u_1,u_2,...,u_p\}$とする。このとき、まず$X_i$と$X_j$の間に$X_i\setminus \{u_1\}$を挿入する。次に$X_i\setminus \{u_1\}$と$X_j$の間に$X_i\setminus \{u_1,u_2\}$を挿入する。次に$X_i\setminus \{u_1,u_2\}$と$X_j$の間に$X_i\setminus \{u_1,u_2,u_3\}$を挿入する...と繰り返し、最終的に$X_i\setminus\{u_1,u_2,...,u_{p-1}\}$と$X_j$の間に$X_i \setminus \{u_1,u_2,...,u_p\}$を挿入する。ちなみに$X_i \setminus \{u_1,u_2,...,u_p\}=X_i\cap X_j$である。

$X_j\setminus X_i=\{v_1,v_2,...,v_q\}$についても同様の操作を行う。つまり、まず$X_i\cap X_j$と$X_j$の間に$X_j\setminus \{v_1\}$を挿入する。次に$X_i\cap X_j$と$X_j\setminus \{v_1\}$の間に$X_j\setminus \{v_1,v_2\}$を挿入する...と繰り返し、最終的に$X_i\cap X_j$と$X_j\setminus \{v_1,v_2,...,v_{q-2}\}$の間に$X_j\setminus \{v_1,v_2,...,v_{q-1}\}$を挿入する（$X_j\setminus \{v_1,v_2,...,v_q\}=X_i\cap X_j$に注意）。

例えば$X_i=\{1,2,3,4\}$、$X_j=\{2,4,5,6,7\}$の場合は下図のように節点が挿入される。

この変形をステップ3.の条件に当てはまるすべての節点に対して行えば、nice tree-decompositionの3つ目の条件が満たされる。またこの変形は木分解の条件を保ち、幅も変化しない。また、集合$X_i$、$X_j$の要素数は木分解の幅+1以下なので、1つの親と子の組$(X_i,X_j)$に対してステップ3.の変形を行うことで増える節点数は、高々木分解の幅×2+1である。よって幅を定数とみれば、ステップ3.終了後の節点数は$O(|X|)$である。また、幅を定数とみればステップ3.全体でかかる時間計算量も$O(|X|)$である。

以上より、ステップ1、2、3によって、与えられた木分解$(X,T)$から同じ幅で節点数$O(|X|)$のnice tree-decompositionが$O(|X|)$時間で得られることがわかる。$\Box $

3. Nice Tree-decomposition上のDP

 木幅が定数で抑えられるグラフ$G=(V,E)$が与えられたとします。すると、1章で述べた通り、幅最小の木分解$(X,T)$を$O(|V|)$時間で得ることができます。また、2章の補題より$(X,T)$と同じ幅のnice tree-decompositionを$O(|X|)$時間で得ることができます。ここで、$|X|=O(|V|)$なので、これらを合わせることで合計$O(|V|)$時間で節点数$O(|V|)$で幅最小のnice tree-decompositionを得ることができます。

さて、幅最小のnice tree-decompositionが線形時間で得られることがわかったので、以下ではいよいよnice tree-decomposition上のDPによって最大独立集合問題が解けることを紹介していきます。

まず、最大独立集合問題に限らず木分解上でのDPは、次のように行われます。

•  木分解$(X,T)$に対して、適当な節点$X_r\in X$を選んで$T$の根と定める*6
• $T$の各節点$X_i\in X$に対して、グラフ$G_i$を、$X_i$とその子孫全体の和集合を頂点集合としてもつ$G$の誘導部分グラフ*7と定める
• $G$について解きたい問題を、各$G_i$について解くことで最終的に（$G_r=G$なので）$G$についても解く
• $X_i$が子$X_{i_1}, X_{i_2}, ..., X_{i_p}$を持っていたとき、$G_i$について解きたい問題を$G_{i_1}, G_{i_2}, ..., G_{i_p}$について解いた結果を用いて解く

上のDPについて、少し疑問を抱く方もいるかもしれません。つまり、$G_i$について解きたい問題を、$G_{i_1}, G_{i_2}, ..., G_{i_p}$について解いた結果を用いて簡単に解けるのでしょうか？

 $G_i$のある2つの子$G_{i_k}$と$G_{i_l}$の両方に含まれる頂点$u$が存在したとします。このとき、$u$は$X_i$にも必ず含まれます。なぜかというと、$u$を含む$T$の節点全体は連結なので、$X_{i_k}$またはその子孫と、$X_{i_l}$またはその子孫を結ぶ道上にある$X_i$にも$u$が含まれるからです。

また、$G_i$に含まれる辺は、$G_{i_1}, G_{i_2}, ..., G_{i_p}$に含まれる辺か、両端点が$X_i$に含まれる辺のどちらかです。なぜかというと、$G_i$のある辺の2端点を$u,v$とすると、$X_i$またはその子孫で$u$を含むもの、$v$を含むものが少なくとも1つずつあります。また、$u$と$v$の間には辺があるので、$T$は$u,v$を同時に含む節点を持ちます。ここで、$T$上で$u$を含む節点全体、$v$を含む節点全体はそれぞれ連結なので、$X_i$またはその子孫で$u,v$を両方とも含むものが必ず存在します。つまり、辺$(u,v)$は$G_{i_1}, G_{i_2}, ..., G_{i_p}$のいずれかに含まれるか、端点$u,v$が$X_i$に含まれるかのどちらかが成り立ちます。

よって、$G_i$についての問題を$G_{i_1}, G_{i_2}, ..., G_{i_p}$についての結果を用いて解く際に、頂点の重複や新しく追加される辺という意味で考慮しなくてはいけないのは$X_i$まわりだけなので、$X_i$のサイズが小さい（つまり木分解の幅が小さい）なら高速にDPをまわして解くことができます。これが木分解上のDPの強みです。

では、実際に最大独立集合問題に対するnice tree-decomposition上でのDPを見ていきましょう。

 最大独立集合問題に対するDP

 nice tree-decomposition$(X,T)$が与えられたとする。$T$の節点$X_i$とその部分集合$S\subseteq X_i$に対して、$A[i,S]$を$G_i$の独立集合$I$のうち$I\cap X_i=S$を満たすものの最大サイズと定める。$A[i,S]$を次のように更新していく。なお$X_i$の子は1つの場合$X_j$、2つの場合$X_j$、$X_k$と表すことにする。また、$X_i$がintrodece、forgetのときの$X_i$と$X_j$の差となる頂点を$v$とする。

・$X_i$が葉の場合：　$\begin{aligned}A[i,S]=\begin{cases}|S|&(\text{Sは独立集合})\\ -\infty&(\mathrm{otherwise}) \end{cases} \end{aligned}$

 

・$X_i$がjoinの場合：　$A[i,S]=A[j,S]+A[k,S]-|S|$

 

・$X_i$がintroduceの場合：　$\begin{aligned}A[i,S]=\begin{cases}A[j,S]&(v\notin S)\\ A[j,S\setminus\{v\}]+1&(v\in S, v\text{と}S\setminus\{v\}\text{の頂点を結ぶ辺がない})\\ -\infty&(\mathrm{otherwise}) \end{cases} \end{aligned}$

 

・$X_i$がforgetの場合：　$A[i,S]=\mathrm{max}\{A[j,S],A[j,S\cup \{v\}]\}$

$X_i$が葉、forgetの場合の式については少し考えれば成り立つことがわかると思います。$X_i$がjoinの場合の式は、$G_j$のうち$X_i$に含まれない頂点と、$G_k$のうち$X_i$に含まれない頂点との間に辺がないことから成り立ちます。また、$X_i$がintroduceで、$v\in S$の場合については、$G_i$のうち$X_i$に含まれない頂点と$v$の間には辺がないことに注意すると、$v$と$S\setminus \{v\}(\subseteq X_i)$との間に辺がなければ、$v$と$I\cap X_j=S\setminus\{v\}$を満たす$G_j$の独立集合$I$との間にも辺がないので、$A[i,S]=A[j,S\setminus\{v\}]+1$が成り立ちます。

与えられたnice tree-decomposition$(X,T)$の幅が定数$t$、$T$の節点数が$O(|V|)$だとします。すると、このDPの時間計算量は、定数時間で終わる更新を$O(2^{t+1}|V|)$回行うので、合計$O(|V|)$時間かかります。よって、（木幅が定数で抑えられるグラフに対して）幅最小のnice tree-decompositionが線形時間で得られることもあわせて、最大独立集合問題が線形時間で解けることが示されました。

4. おまけ

前の章で、木幅が定数で抑えられるグラフに対して最大独立集合問題が線形時間で解けることを示しました。実は、もっと一般的に次のような事実が成り立ちます。

定理（Courcelle 1990）

 木幅が定数で抑えられるグラフと単項二階論理式で表現できるグラフについての命題が与えられたとき、グラフが命題を満たすかどうかを線形時間で判定できる

 （グラフについての）単項二階論理式とは次の表現を組み合わせて記述できる論理式のことです。

• 論理結合子$\land, \lor, \to, \lnot, =, \neq$
• 頂点、辺に関する量化子$\forall, \exists$
• 述語adj($u,v$)（$u$と$v$の間に辺があるなら1を、ないなら0を返す）
• 述語inc($e,v$)（$v$が$e$の端点なら1を、そうでないなら0を返す）
• 頂点集合、辺集合に関する量化子$\forall, \exists$
• 頂点集合、辺集合に関する$\in, \subseteq$

例えば、グラフが二部グラフである、独立集合である、閉路がある、3彩色可能、などの命題は単項二階論理式で表現可能です。

Coucelleの定理については証明とかも追ってなくてあまりよく知らないので、そのうちちゃんと勉強したいなと思います。

*1:なぜ1を引いているのかというと、木の木幅を1にするためです。

*2:外平面的グラフとは、すべての頂点が外面に面していて、かつ辺は交差しないような平面埋め込みをもつグラフです。例えば木分解の例のところで登場したグラフは外平面的グラフです。

*3:ならない人もいるかもしれません。

*4:nice tree-decompositionに変形せずにそのままDPをする場合の解法はWikipediaに漸化式などが載っています。この漸化式も本質的にはnice tree-decompositionに変形してからDPする場合の漸化式と同じです。

*5:葉と根は必ず空集合という条件を定義に含む流儀などもありますが、今回はそれは採用しませんでした。

*6:nice tree-decompositionに変形した場合はすでに根が定まっています。

*7:$G'$が$G$の誘導部分グラフであるとは、$G'$が$G$の部分グラフであり、かつ両端点がどちらも$G'$に含まれるような$G$の辺はすべて$G'$にも含まれるグラフのことをいいます

行列木定理の証明

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$における同じ全域木と一対一対応しているからです（下図参照）。

つまり、グラフ$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$のラプラシアン行列の余因子、と簡潔に言いたいところなのですが、自己ループのあるグラフに対してラプラシアン行列を定義すると、ラプラシアン行列の良い性質が崩れたりするので（自己ループをどう次数にカウントするかにもよりそうですが）、結局自己ループを除いたグラフを考えるのが楽ということでそうしました。