![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/Ungerichteter_Graph_mit_4_Knoten_und_3_Kanten.svg/langja-640px-Ungerichteter_Graph_mit_4_Knoten_und_3_Kanten.svg.png&w=640&q=50)
隣接行列
ウィキペディア フリーな encyclopedia
![]() |
「接続行列 (incidence matrix)」とは異なります。 |
グラフ理論および計算機科学において、隣接行列(りんせつぎょうれつ、英: adjacency matrix)は、有限グラフを表わすために使われる正方行列である。この行列の要素は、頂点の対がグラフ中で隣接(英語版)しているか否かを示す。
さらに見る
,
...
辺の重みと多重辺を 持たない無向グラフ |
左のグラフに対する 4x4-隣接行列 |
---|---|
![]() |
|
辺の重みを持ち、多重辺を 持たない有向グラフ |
左のグラフに対する 隣接行列 |
![]() |
|
辺の重みを持ち、多重辺を 持つ有向グラフ |
ループを持たない左のグラフの 可約隣接行列 |
閉じる
有限単純グラフの特別な例では、隣接行列はその対角上に0を持つ (0,1)-行列(英語版)である。もしグラフが無向ならば、隣接行列は対称である。グラフとその隣接行列の固有値および固有ベクトルとの間の関係はスペクトラルグラフ理論において研究される。
隣接行列はグラフに関する接続行列および次数行列と区別されなければならない。接続行列は、その要素が頂点-辺の対が接続しているか否かを示す行列表現であり、次数行列は個々の頂点の次数に関する情報を含む行列表現である。