『線形代数とネットワーク』前半を読み、木の意義について理解してみる - 機械のように今を輝き、少女のようにここを定義せよ

記号を整理する
- 記号の意味
- 記号の直感的理解
すべては木だった
さいごに
参考文献

最近は「グラフ」、ようはネットワークのことですが、
の話題をいろいろな所で目にします。

何か数理科学的な問題を考える上で、
その表現の幅が豊かであるためでしょうか。

しかし一方で、
それぞれのグラフがどんなグラフなのか、
その「性質」をヒトコトで言うのはなかなか
難しいようです。

そんな中、ある本を読んでいて、
グラフでもやはり「行列式」が
一定の意味のある働きをしているようで、
これにそこはかとない快さを感じました。

この理解を改めて整理したく、
要点を簡潔にまとめてみたいと思います。

結論を先取りすると、
グラフについてある表現をしたとき、
グローバルな性質の１つである行列式が、
結局、木の数になるということ。

この木の数というのが、
電気回路などで重要視される、
（あるいは自分だったら因果とかでも
　気にする因子ですが、）
ある種の閉路の数にも一致するというのです。

その読んでいたのは
『線形代数とネットワーク』という本で、
改めて線形代数の価値を感じることになり、
なかなかの良さがあります。

さてこれらを理解するうえで、
見る勉を行うだけだけだとやっぱり記号の意味を
つどつど忘れてしまって面倒です。

さりとてノートに記載していても
少し時間が経つと、どっかいってしまう・・・。

このため、せっかくなので、
記事にまとめて残してみようと思います。

記号を整理する

記号の意味

まずは $B, L$ などの記号の意味を列挙します。

自分で理解しやすい表現にするため、
定義を厳密に記載しているものではありません。

$B$ は接続行列。
全ての頂点と枝の組み合わせです。

（隣接行列は頂点と頂点の組み合わせなので、
　そこが違いますね。）

頂点 $i$ から枝 $j$ が出ていっている場合、
$B_{ij}$ は 1 になります。
入ってきている場合は -1 になります。

『線形代数とネットワーク』38P にある
下図グラフの例を、以下で示します。
f:id:a16777216:20190627111233p:plain

接続行列は、
$B = \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & -1 \\ -1 & 1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 0 & -1 & 1 \\ \end{pmatrix}$
と表されます。

→行→　が１つの頂点に相当します。
ここでは丁度４行ありますね。

↓
列
↓
が１つの枝に相当します。
どの列も流出元 1、流入先 -1 が１つずつありますね。

被約接続行列 $B'$ というものもあります。
$B$ から適当な一行を削除します。
ここでは４行目を削除します。

$B' = \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & -1 \\ -1 & 1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & -1 & 1 & 0 \\ \end{pmatrix}$

$H$ は名前はついていませんが、
頂点の数 $n$ に対し $n -1$ の枝を選ぶ、
部分グラフになります。
$n -1$ というのが既に木の片鱗を見せていますね。

ここで $B$ から下図の黒い線だけ選び、
部分グラフ $H$ を作ると、
f:id:a16777216:20190627113402p:plain
$B_H$ は
$B_H = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & -1 \\ \end{pmatrix}$
となります。

元の $B$ のうち、
1 から数えて 3, 4, 5 番目の枝を取っています。

$T$ は、 $H$ の中の特別な場合で、
「全域木」に相当する場合です。

全域木とは何かというと、うまく
「全ての頂点を含む木」を取り出した
部分グラフですね。

連結なグラフであれば必然的に、
上手に枝を刈っていけば、
かならずすべての頂点を結ぶ木が得られる、
という寸法ですね。

グラフの中に全域木という大きな木が
必然的に含まれているわけです。

なお $\overline{T}$ は補木と呼ばれる、
$T$ の全ての枝の集合を表します。

全域木 $T$ に補木 $\overline{T}$ の枝 $\overline{t}$ を１つだけつけたときに
現れる単純閉路を $C( \overline{t} )$ と書きます。

少し寄り道になりますが、
以下のタイセット、カットセットというのも
のちに繋がってきます。

$C( \overline{t} )$ の集合を基本タイセットと言います。

対し、 $D(t)$ の集合は、
基本カットセットと呼ばれます。

全域木 $T$ から枝 $t$ だけを除くと、
木は２つの木に分裂していしまいます。

これらの２つの木の頂点の集合を、それぞれ
$X, \overline{X}$ と書きましょう。

このとき、 $X, \overline{X}$ を結ぶ完全二部グラフを作ると
（ただし全て $X$ から $\overline{X}$ への向き）、
これがカットセット $D(t)$ になります。

基本タイセットを行列表示したのが $P$ で、
何番目の閉路が（行）、何番目の枝を（列）
どっち向きに使うか、という行列です。

対して、
基本カットセットを行列表示したのが $Q$ です。
何番目の二部グラフが（行）、何番目の枝を（列）
どっち向きに使うか、という行列です。

他の頻出記号には $L$ があります。
これは $L=B ^{t}B$ とも書け、
グラフラプラシアンのようです。

$B$ は長方形の行列ですが、
転置して自分と書けることで相殺し、
少し疎に広く広がっていたのが
キュッと縮まるイメージですね。

同書には無向の例しかなかったのですが、
上図の有向な $B$ の例で $L$ を求めると、
$L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \\ \end{pmatrix}$
・・・何のことはない、
無向のときと同じものですね。
すなわちラプラシアンの -1 倍というわけです。

記号の直感的理解

ここまでで、以下の記号を書いてきました。
少し自分なりに意味を考えてみたいと思います。

まず $B$ は、最初だけ戸惑いますが、
文字通り頂点から枝への流出ですね。

隣接行列のあいだに枝が割って入っている、
そういう印象を受けます。

$B_H$ については実用的な要請から
少し振り返ってみます。

$B_H$ は $n \times (n-1)$ の行列で、
→１行→が１つの頂点、
↓１列↓が１つの枝になっています。

$n$ 行なので頂点のほうがちょっと多いですね。
そこで被約にして頂点を１個外してしまえば、
この $B'_H$ は $(n-1) \times (n-1)$ の正方行列です。

全域木 $T$ の場合は、（特に根を外す慣例のようですが、）
残された頂点と枝とで１対１対応を作れます。

この対応順で $B'_H$ の並びを構成してやれば、
対角成分は皆 $\pm 1$ になります。

$B'_H$ 全体のなかで $\pm 1$ になる要素の数が
$2(n-1)$ より少ないことを合わせると、
行列式が $\det B'_H = \pm 1$ となることが分かりますね。

すべては木だった

さて、閉路を含むような任意のグラフを考えるさいも、
その中に隠れている木（の数）こそが
グローバルな特徴量の１つである行列式と
なんと一致するのだと、
この本を読んでいて分かってきました。

木が世界を規定するという
北欧神話的なロマンを感じます。

ともあれ、明確に定量化できる量である
行列式が、このような定性的な意味を持つのは、
ひとまずは頼もしさを感じるところです。

ちょっと導き方を確認したうえで、
その上で少し触れたタイセット等とも
関係性をさらってみましょう。

ラプラシアンから１行目と１列目を削った
$n-1$ 行 $n-1$ 列の $L'$ は、
$B'$ を使って
$L'$ = $B' ~ ^{t} B'$
と書けます。

さてこのとき、 $\det L'$ はどうでしょうか。

一般に、こういう $m \times M ~ (M \geq m)$ という
「長方形の行列同士の積」の行列式を考えるとき、
コーシー - ビネの公式が役立つそうです。

本だけだとちょっと読み取れなかったですが、
Wikipedia 情報に頼るとするならば、
専用の項目があって結構詳しく書いてあります。

ja.wikipedia.org

つまり、 $M$ 個のうち大小関係を入れ替えない
$m$ 個を選んで正方形を作ろうというわけですね。

いわゆる $_M C _n$ 通りを考えるということでしょうか。
確かに、余因子展開を思い出してみれば
確かにそうなるという気がします。

$m$ 個の取り合わせを $S$ とするなら、
$\displaystyle \det (A ^{t} B) = \sum _S \det A _S \det ~ ^{t} B _S$
という具合です。
これを $L'$ の場合で書くと、
$\displaystyle \det L' = \sum _H (\det B' _H )^2$
となります。
木でないものも含む $H$ 全体というのが丁度、
$n-1$ 個の取り合わせ全体になっているためですね。