鄰接代數

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

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

性質

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

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

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

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