行列木定理

無向グラフ $G$ とその向き付け $\mathfrak{o}$ に対して、接続行列 $M(G)$ を
\begin{eqnarray}
M_{i, j} =
\begin{cases}
1 & (辺 e_j は向き付け \mathfrak{o} の下、頂点 v_i を始点に持つ) \\
-1 & (辺 e_j は向き付け \mathfrak{o} の下、頂点 v_i を終点に持つ) \\
0 & (\text{otherwise})
\end{cases}
\end{eqnarray}
として定義する。このとき、$L(G) = MM^T$ は\begin{eqnarray}
L_{i, j} =
\begin{cases}
-m_{i,j} & (i \neq j で、頂点 i,j 間に m_{i,j} 本の辺がある) \\
d(i) & (i = j で頂点iに接続する辺の個数が d(i) である) \\
\end{cases}
\end{eqnarray}となる。$L$ をラプラシアン行列と呼ぶ。

行列木定理：$G$ を自己ループのない無向グラフ、$G$ の全域木の個数を $\kappa(G)$ とする。とする。$L_{v}$ を $L$ から $v$ で番号づけられた行と列を除いた小行列とすると、$$\det(L_{v}) = \kappa(G)$$ が成り立つ。この値は $v$ や $\mathfrak{o}$ の選び方に依らない。

証明：$M$ は任意の小行列の行列式が $0, \pm 1$ になる。この性質を完全ユニモジュラという。特に、頂点集合 $U$、辺集合 $F$ で添え字付けられた行・列からなる小行列 $A$ が $\det(A) = \pm 1$ となるための必要十分条件（あとで示す）は

$F$ からなる無向基礎グラフは $V(G) \setminus U$ の頂点を根とする森になる。
$U$ は $F$ の辺で被覆されている。

である。この事実を認めると、$L_v$ において $F$ は $v$ を根とする森、つまり、木になる。従って、コーシー・ビネの定理より、
\begin{align}
\det(L_v) &= \det(M_vM_v^T) \\
&= \sum_S \det({M_v}^S)^2 \\
&= \kappa(G) \\
\end{align}となる。ただし、$M_v$ は頂点 $v$ で番号づけられた行・列を $M$ から取り除いた小行列、$M_v^S$ は $M_v$ から辺集合 $S$ で番号づけられた列を取り出した小行列である。

証明することなく使った次の事実を示す。

無向基礎グラフを向きづけた接続行列 $M$ は任意の小行列の行列式が $0, \pm 1$ になる。特に、頂点集合 $U$、辺集合 $F$ で添え字付けられた行・列からなる小行列 $A$ が $\det(A) = \pm 1$ となるための必要十分条は

$F$ からなる無向基礎グラフが $V(G) \setminus U$ の頂点を根とする森になる。
$U$ は $F$ の辺で被覆されている。

である。

証明：行列式が非零になるには、各頂点に辺を一つずつ割り当てなければならない。閉路以外の頂点に割り当てる辺は、葉から貪欲に一意に定まる。頂点が順に $v_0, v_1, \ldots$ である閉路は、頂点 $v_i$ に辺 $\{v_i, v_{i+1}\}$ を割り当てる方法と、辺 $\{v_i, v_{i-1}\}$ を割り当てる方法の二通りがある。いくつかある閉路のうち、頂点ラベルが辞書順最小の閉路の辺の向きを反転する操作 $\phi$ を考える（閉路の辺を巡回置換する）。偶閉路の場合、置換の偶奇が反転し、辺の向き(±1)の積は不変。奇閉路の場合、置換の偶奇は不変だが、辺の向き(±1)の積は反転する。従って、$\phi$ は、閉路がある場合、行列式の符号を反転させる。$\phi$ は二回行うと元に戻るので、閉路のあるグラフはペアをなし、行列式が打ち消される。従って、森だけが残る。あるいは、$A$ の核はサイクル空間になっていて、その像の次元が $|E|-|V|+(連結成分の数) > 0$ になっていることから、行列式が 0 になることが分かる。

Comments

コメントを残すコメントをキャンセル