KirchhoffMatrix

KirchhoffMatrix[g]
グラフ g のKirchhoff行列を返す.

詳細詳細

  • KirchhoffMatrixSparseArrayオブジェクトを返す.これはNormalを使って通常の行列に変換できる.
  • 対角項 の次数に等しい.
  • 頂点 と連結されている場合,項 である.
  • 頂点 VertexList[g]で返されるものと同じ順序であると想定される.
  • グラフのKirchhoff行列の次元は × である.ただし, は頂点の数である.

予備知識
予備知識

  • KirchhoffMatrixは,ラプラシアン(Laplacian)行列,アドミタンス行列,あるいは離散ラプラシアンとしても知られる,Kirchhoff行列を返す.これは,整数要素の正方行列である.効率のため,KirchhoffMatrixは行列を疎な配列として返す. (通常の)Kirchhoff行列 L は,次数行列 D (グラフの頂点次数 の対角行列)と隣接行列 A の差 として定義され,L の対角要素 は,したがって,頂点 の次数 に等しく,非対角要素 は,頂点 に隣接している場合は-1で,その他の場合は0である.
  • n 個の頂点があるグラフの場合,Kirchhoff行列の次元は n×n である.無向グラフの場合,Kirchhoff行列は対称である.
  • Kirchhoff行列は,スペクトルグラフ理論の中心的役割を果たす.この理論は,隣接行列あるいはKirchhoff行列の固有値に基づいてグラフを研究するものである.これを使って,グラフの頂点間の抵抗距離を計算することができる.これは,各辺が単位抵抗で置換された場合の(電池が頂点に付属している)頂点間の実効抵抗として定義することができる.これは,行列木定理にも見られる.この定理は,グラフの全域木の数を与えるものである.Kirchhoff行列の2番目に小さい固有値はグラフの代数連結性として知られており,グラフはこの固有値が0より大きいときかつそのときに限り連結されている.グラフの代数連結性に対応する固有値はFiddlerベクトルとして知られており,隣接行列あるいはKirchhoff行列の固有値に基づいて指定されたグラフを特定の特性を持つより小さい成分に分割するスペクトルグラフ分割において重要である
  • 物理学者は「Kirchhoff行列」の代りに「ラプラシアン行列」という語を好んで使うのに注意のこと.物理学者や数学者の中には, かつ のときは が隣接しているなら,その他の場合は0という,正規化が異なるバージョンも使う. さらに,「グラフスペクトル」という語は,一般に,数学者にとってはグラフの隣接行列の固有値を意味するのに対し,物理学者にとっては,これはしばしば正規化されたKirchhoff行列の固有値を意味する.であるから,これらの語が孤立して出てきた場合は注意が必要である.
  • KirchhoffGraphを使ってKirchhoff行列からグラフを構成することができる.類似した関数のAdjacencyGraphおよびIncidenceGraphは,与えられた隣接行列および結合行列からグラフを構築する.

例題例題すべて開くすべて閉じる

  (2)  (2)

無向グラフのKirchhoff行列:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]//MatrixForm=

有向グラフのKirchhoff行列:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]//MatrixForm=
2010年に導入
(8.0)