1. 高校数学の美しい物語
  2. 隣接行列,接続行列,ラプラシアン行列

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

更新日時 2021/03/07

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

目次
  • 準備

  • 隣接行列

  • 点枝接続行列

  • ラプラシアン行列

  • Tutte行列

準備

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

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

隣接行列

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

隣接行列の例

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

隣接行列 AA の性質

  • AA は対称行列
  • AnA^nijij 成分は,GG における ii から jj への長さ nn の道(同じところを複数回通ってもよい)の本数

点枝接続行列

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

点枝接続行列の例

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

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

接続行列 QQ の性質

  • (無向グラフにおいて)二部グラフの接続行列は完全単模(任意の正方部分行列の行列式が 00 または ±1\pm 1

  • (有向グラフにおいて※のように接続行列を定めた場合)任意のグラフの接続行列は完全単模

ラプラシアン行列

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

さきほどの図のグラフに対応するラプラシアン行列は,

L=(0000021101210112)L=\begin{pmatrix}0&0&0&0\\0&2&-1&-1\\0&-1&2&-1\\0&-1&-1&2\end{pmatrix}

ラプラシアン行列 LL の性質

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

Tutte行列

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

さきほどの図のグラフに対応するTutte行列は,

T=(000000x23x240x230x340x24x340)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行列 TT の性質

  • TT は歪対称行列
  • TT が正則     \iff GG に完全マッチングが存在
  • 12rankT=G\dfrac{1}{2}\mathrm{rank}\:T=G の最大マッチングのサイズ

グラフ理論と行列の関係についてはBapatのGraphs and Matricesという本がオススメです。

人気記事
  1. 高校数学の美しい物語
  2. 隣接行列,接続行列,ラプラシアン行列