接続行列と隣接行列の違い

  • このエントリーをはてなブックマークに追加
  • Pocket
  • LINEで送る

接続行列も隣接行列も,ともにグラフを行列で表現したものです。

本記事ではそれらの定義と,複式簿記との関係を簡単にまとめます。

頂点集合の要素数は\( n\)とし,そのインデックスを\( i=1,2,\cdots,n\)とします。辺集合の要素数は\( m\)とし,そのインデックスを\( j=1,2,\cdots,m\)とします。

接続行列

\( n\times m\)行列として定義されます。辺\( j\)が頂点\(i_1 \)から頂点\( i_2\)に向かっているとき,接続行列\( M\)の第\( j\)列について,第\( i_1\)行目に\( -1\)が,第\( i_2\)行目に\( 1\)が入力されます。

複式簿記との関係

グラフが複式簿記の有向グラフを表しているとき,接続行列における各列はバランスベクトルになります。

【君の知らない複式簿記6】矢印簿記で仕訳をビジュアライズ

隣接行列

\( n\times n\)行列として定義されます。頂点\(i_1 \)と頂点\( i_2\)の間に辺が存在するとき,隣接行列\( A\)の\((i_1,i_2)\)成分と\((i_2,i_1)\)成分に\( 1\)が入力されます。この定義から,隣接行列は対称行列です。

複式簿記との関係

行列簿記は隣接行列です。

【君の知らない複式簿記 補遺】隣接行列とマテシッチの行列簿記

ラプラシアン行列

隣接行列を\(A \),その次数行列を\( D\)とします。次数行列とは\( n\times n\)対角行列であって,対角成分には各頂点から伸びる辺の数を入力したものです。

このとき,\( L=D-A\)で定義される行列を,ラプラシアン行列といいます。

接続行列\( M\)をとると,ラプラシアン行列を\( L=M^{\textsf{T}}M\)と表せます。

参考文献

ラプラシアン行列 – Wikipedia 


  • このエントリーをはてなブックマークに追加
  • Pocket
  • LINEで送る

SNSでもご購読できます。

コメントを残す

*