邻接代数

在代数图论中，图 $G$ 的邻接代数（adjacency algebra）是这个图的邻接矩阵 $A(G)$ 的多项式所组成的代数。它是一种矩阵代数，是 $A$ 的各次幂的线性组合所组成的集合。

其他一些类似的数学对象也被称为“邻接代数”。

性质

$G$ 的邻接代数的性质与 $G$ 的图论性质相关，例如各种谱、邻接性、连通性。

命题：顶点 $i,j$ 之间长度为 $d$ 路径的数目等于 $A^{d}$ 的 $(i,j)$ 元。

命题：对于直径为 $d$ 的连通图，其邻接代数的维数至少是 $d+1$ 。

推论：直径为 $d$ 的连通图至少有 $d+1$ 个不同的特征值。