代數圖論

代數圖論（algebraic graph theory）是用代數方法處理圖論問題的數學分支。這不同於幾何、組合或算法的方法。代數圖論有三個主要分支，分別使用線性代數，使用群論，以及研究圖不變量。

佩特森圖，一種高度對稱的圖。它的直徑為2。其自同構群有120個元素，事實上就是對稱群${\displaystyle S_{5}}$。

代數圖論的分支

使用線性代數

代數圖論的第一個分支用線性代數來研究圖，特別是研究圖的鄰接矩陣或拉普拉斯矩陣的譜（這部分代數圖論也被稱為譜圖理論）。以佩特森圖為例，鄰接矩陣的譜為(-2, -2, -2, -2, 1, 1, 1, 1, 1, 3)。通過一些定理把譜的性質與圖的其他性質聯繫起來。舉一個簡單的例子，對於直徑為D的連通圖，它的譜至少有D+1個不同的值^[1]。圖的譜可用於分析網絡的同步。

使用群論

交錯群${\displaystyle A_{4}}$的凱萊圖，在三維空間中構成了截角四面體。

代數圖論的第二個分支用群論來研究圖，尤其是自同構群以及幾何群論。重點是根據對稱性對圖進行分類，以及不同類別之間的包含關係。某些特殊類別的圖足夠少，可以把它們列舉出來。根據Frucht定理，所以的群都可以表示成連通圖的自同構群^[2]。另外，給定一個群，可以作出相應的凱萊圖，凱萊圖有一些性質與群的結構相關^[1]。

代數圖論的第二個分支與第一個分支有聯繫，因為圖的對稱性在圖的譜中也有反映。尤其是，對於高度對稱的圖，例如佩特森圖，不同的特徵值的數目很少^[1]（佩特森圖有3個不同的特徵值，在直徑相等的圖中是最少的）。凱萊圖的譜與群的結構直接相關，尤其是與不可約特徵標相關^[1][3]。

研究圖不變量

用三種顏色對佩特森圖的頂點進行着色。根據色多項式，有120種3着色。

最後，代數圖論的第三個分支研究圖不變量的代數性質，尤其是色多項式、Tutte多項式與扭結不變量。例如，圖的色多項式計算了頂點着色的個數。佩特森圖的色多項式為${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$^[1]。這意味着佩特森圖不能用1種或2種顏色着色，但可以用3種顏色着色，且着色方式有120種。代數圖論的這一領域的許多工作都是為了證明四色定理而啟發。可是仍然有許多未解決的問題，例如如何判定兩個圖的色多項式相同，以及如何判定一個多項式是不是某個圖的色多項式。

另見

• 譜圖理論
• 代數組合學
• 代數連通度
• 鄰接矩陣

參考資料

1. Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
2. R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.
3. Babai, L (1996), "Automorphism groups, isomorphism, reconstruction", in Graham, R; Grötschel, M; Lovász, L, Handbook of Combinatorics, Elsevier

• Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, 207, New York: Springer-Verlag.