隣接行列

ウィキペディア

隣接行列

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

${\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}}$

$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}}$

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

${\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を含む。空グラフの隣接行列はゼロ行列である。

性質

スペクトル

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

• ドイツ

ウィキペディア小見出し辞書

隣接行列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/14 07:02 UTC 版)

「強正則グラフ」の記事における「隣接行列」の解説

I を単位行列、J を matrix of ones（英語版）（全成分が1の行列）で、いずれも v 次（行列）であるとする。強正則グラフの隣接行列 A は2つの方程式を満たさねばならない。まず、 A J = J A = k J これはグラフの正則性を述べなおした自明な関係である。これより、k は隣接行列の固有値で、全成分が1のベクトルがそれに対する固有ベクトルであることがわかる。 次は2次式の関係式で、グラフの強正則性を表す。 A 2 = k I + λ A + μ ( J − I − A ) 左辺の ij-成分は、頂点 i から頂点 j への長さ2の道の本数を表す。右辺の最初の項は頂点 i を自分自身と結ぶ、つまり k 本の「出」と「入り」の辺の数である。第2項は頂点 i と頂点 j が隣接しているときに、2辺でこれらを結ぶ道の本数を表す。第3項は頂点 i と頂点 j が隣接していないときの本数である。これら3つの場合は排他的で、かつ全てを尽くしているから、単純に和をとって等式が得られる。 逆に、グラフの隣接行列がこれら2条件を満たし、完全グラフでも空グラフでもないとき、強正則グラフである。