adjacency matrix

ウィキペディア

隣接行列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/25 07:00 UTC 版)

「接続行列 (incidence matrix)」とは異なります。

${\displaystyle {\begin{array}{r|c}&{\begin{matrix}1&2&3&4\end{matrix}}\\\hline {\begin{matrix}1\\2\\3\\4\end{matrix}}&{\begin{pmatrix}0&1&0&0\\1&0&1&1\\0&1&0&0\\0&1&0&0\\\end{pmatrix}}\end{array}}}$

${\displaystyle A={\begin{pmatrix}0&0&12&60&0\\10&0&0&0&0\\0&20&0&32&0\\0&0&0&0&0\\7&0&0&0&0\\\end{pmatrix}}}$

${\displaystyle A={\begin{pmatrix}0&3&0&0\\2&0&4&0\\0&0&0&1\\0&0&2&0\\\end{pmatrix}}}$

${\displaystyle {\begin{pmatrix}2&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix}}}$ ナウルグラフ（英語版）

座標は0–23。 白い場は0、色付けされた場は1である。

有向グラフ

有向グラフでは、頂点の入次数は対応する列の成分の和を取ることによって計算でき、出次数は対応する行の成分の和を取ることによって計算できる。

ラベル付きグラフ	隣接行列
S4の有向ケイリーグラフ	座標は0–23。 グラフが有向であるため、隣接行列は必ずしも対称ではない。

自明なグラフ

完全グラフの隣接行列は、成分が0の対角要素以外は全て1を含む。空グラフの隣接行列はゼロ行列である。

性質

スペクトル

無向単純グラフの隣接行列は対称であり、したがって実固有値および直交固有ベクトル基底の完全集合を持つ。グラフの固有値一式はグラフのスペクトルである^[5]。通常、固有値を${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$

• ドイツ