2015/09/12

隣接行列,接続行列,ラプラシアン行列

分野: グラフ理論  レベル: 大学数学

グラフに対応するいろいろな行列を紹介します。線形代数の議論でグラフの性質が分かるという素敵な理論のための道具です。

準備

グラフについてはグラフ理論の基礎をどうぞ。

以下では単純無向グラフ $G=(V,E)$ について考えます。ただし,$V$ は $G$ の頂点集合,$E$ は枝集合を表します。

隣接行列

各行,列がそれぞれ頂点に対応しており,枝がある部分に $1$,ない部分に $0$ を格納した $|V|\times |V|$ の正方行列を隣接行列と言います。

隣接行列の例

図のグラフ $G$ に対応する隣接行列は,$A=\begin{pmatrix}0&0&0&0\\0&0&1&1\\0&1&0&1\\0&1&1&0\end{pmatrix}$

〜隣接行列 $A$ の性質〜

  • $A$ は対称行列
  • $A^n$ の $ij$ 成分は,$G$ における $i$ から $j$ への長さ $n$ の道(同じところを複数回通ってもよい)の本数

点枝接続行列

各行が頂点,各列が枝(辺)に対応しており,頂点が枝に接続しているときは $1$,そうでない部分に $0$ を格納した $|V|\times |E|$ の行列を(点枝)接続行列と言います。

点枝接続行列の例

図のグラフに対応する接続行列は,$Q=\begin{pmatrix}0&0&0\\1&1&0\\1&0&1\\0&1&1\end{pmatrix}$

なお,有向グラフの場合,枝が頂点から出て行く部分は $1$,入ってくる部分は$-1$ とする場合が多いです。

〜接続行列 $Q$ の性質〜
・二部グラフの接続行列は完全単模(任意の正方部分行列の行列式が $0$ または $\pm 1$)

ラプラシアン行列

各行,列がそれぞれ頂点に対応しており,対角成分にはその頂点の次数,非対角成分については枝がある部分に$-1$,ない部分に $0$ を格納した $|V|\times |V|$ の正方行列をラプラシアン行列(グラフラプラシアン)と言います。

先ほどの図のグラフに対応するラプラシアン行列は,
$L=\begin{pmatrix}0&0&0&0\\0&2&-1&-1\\0&-1&2&-1\\0&-1&-1&2\end{pmatrix}$

〜ラプラシアン行列 $L$ の性質〜

  • $L$ は対称行列
  • $L$ の各行,各列の和は $0$
  • $\mathrm{rank}\:L=|V|-1$ $\iff G$ が連結
  • $L$ の任意の余因子は $G$ の全域木の個数と等しい(行列木定理)

Tutte行列

各行,列がそれぞれ頂点に対応しており,頂点 $i$ と $j$ を結ぶ枝があるとき,$ij$ 成分に変数 $x_{ij}$ を,$ji$ 成分に$-x_{ij}$ を格納した行列(他の成分は $0$)をTutte行列と言います。

先ほどの図のグラフに対応するTutte行列は,
$T=\begin{pmatrix}0&0&0&0\\0&0&x_{23}&x_{24}\\0&-x_{23}&0&x_{34}\\0&-x_{24}&-x_{34}&0\end{pmatrix}$

〜Tutte行列 $T$ の性質〜

  • $T$ は歪対称行列
  • $T$ が正則 $\iff$ $G$ に完全マッチングが存在
  • $\dfrac{1}{2}\mathrm{rank}\:T=G$ の最大マッチングのサイズ
グラフ理論と行列の関係についてはBapatのGraphs and Matricesという本がオススメです。
分野: グラフ理論  レベル: 大学数学