Skip to content →

行列木定理

無向グラフ \(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\) の辺で被覆されている。

である。この事実を認めると、コーシー・ビネの定理より、
\begin{align}
\det(L_v) &= \det(M_vM_v^T) \\
&= \sum_S \det({M_v}^S)^2 \\
&= \kappa(G, v) \\
\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\) は二回行うと元に戻るので、閉路のあるグラフはペアをなし、行列式が打ち消される。従って、閉路のない場合だけが残る。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA