代數圖論

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

代數圖論的分支

使用線性代數

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

使用群論

交錯群

A_{4}

的凱萊圖，在三維空間中構成了截角四面體。

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

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

研究圖不變量

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

最後，代數圖論的第三個分支研究圖不變量的代數性質，尤其是色多項式、Tutte多項式與扭結不變量。例如，圖的色多項式計算了頂點着色的個數。佩特森圖的色多項式為 $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.0 ^1.1 ^1.2 ^1.3 ^1.4 Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
^ R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.
^ 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.

[Biggs,_Norman-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 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

[1]

[2]

[3]