鄰接代數

在代數圖論中，圖$G$的鄰接代數（adjacency algebra）是這個圖的鄰接矩陣$A(G)$的多項式所組成的代數。它是一種矩陣代數，是$A$的各次冪的線性組合所組成的集合。

其他一些類似的數學對象也被稱為「鄰接代數」。

性質

$G$的鄰接代數的性質與$G$的圖論性質相關，例如各種譜、鄰接性、連通性。

命題：頂點$i,j$之間長度為$d$路徑的數目等於$A^{d}$的$(i,j)$元。

命題：對於直徑為$d$的連通圖，其鄰接代數的維數至少是$d+1$。

推論：直徑為$d$的連通圖至少有$d+1$個不同的特徵值。

參考文獻

• Algebraic graph theory, by Norman L. Biggs, 1993, ISBN 0521458978, p. 9