隣接代数

代数的グラフ理論において、グラフGの隣接代数は、グラフの隣接行列A ( G )内の多項式の代数である。これは行列代数の一例であり、 Aの べき乗の線形結合の集合である。^[1]

他の同様の数学的対象も「隣接代数」と呼ばれます。

Gの隣接代数の特性は、Gのさまざまなスペクトル、隣接、接続特性 と関連しています。

ステートメント。頂点iとjの間の長さdの歩行の数は、 A ^dの( i ,  j )番目の要素に等しい。^[1]

声明。直径dの連結グラフの隣接代数の次元は少なくともd  + 1である^。[1]

系。直径dの連結グラフには少なくともd  + 1個の異なる固有値がある。^[1]