AdjacencyMatrix

AdjacencyMatrix[g]
グラフ g の頂点 - 頂点の隣接行列を与える.

詳細詳細

  • 隣接行列は,連結性行列としても知られている.
  • AdjacencyMatrixNormalを使って通常の行列に変換可能なSparseArrayオブジェクトを返す.
  • 隣接行列の項 は頂点 から頂点 への有向辺の数である.
  • 対角項 は頂点 のループの数を数える.
  • 無向辺は方向が逆の2つの有向辺と解釈される.
  • 頂点 VertexList[g]で与えられる順序であるとみなされる.
  • グラフの隣接行列の次元は × である.ただし, は頂点数である.

予備知識
予備知識

  • AdjacencyMatrixは,正方行列を返す.その行と列はグラフの頂点に対応し,要素 は,頂点 から頂点 までの(有向)辺の数を与える非負の整数である.隣接行列は,行列に対する簡単な操作を使って,数多くの特性を計算するのに使えるグラフの便利な表現を提供する.隣接行列を与えることによって効率的に行えるグラフの計算の例には,頂点次数,入次数と出次数,最高で ステップの頂点間の経路の数,グラフスペクトル等がある.
  • 個の頂点のグラフについては,隣接行列は の次元を持つ.無向グラフについては,隣接行列は対称である.有限の単純グラフ(例:自己ループや複数辺を持たない,無向で,重みなしのグラフ)については,隣接行列は対角に0を持たなければならず,その行列要素は, に隣接している場合には によって,その他の場合には によって与えられる.
  • 頂点の特定の順序に基づくグラフの明示的な隣接行列の表現は,一意的である.しかし,グラフの頂点は置換できるので,対応する同形クラスのグラフを表す隣接行列のクラスが存在する.ただし,同形クラスの隣接行列は行列の行と列の一意的なモジュロ置換である(グラフ頂点のラベルを付け直すことに正確に対応する).
  • AdjacencyGraphを使って,隣接行列からグラフを構築することができる.IncidenceMatrixは,頂点と頂点の関係の代りに,頂点と辺の関係を与えるグラフの別の行列表現を与える.AdjacencyMatrixはグラフの重みを考慮に入れないので,辺の重みを持つグラフの隣接行列を計算する場合には,WeightedAdjacencyMatrixを使わなければならない.
2010年に導入
(8.0)