代數圖論
代數圖論（algebraic graph theory）是用代數方法處理圖論問題的數學分支。這不同於幾何、組合或算法的方法。代數圖論有三個主要分支，分別使用線性代數，使用群論，以及研究圖不變量。
代數圖論的分支[編輯]
使用線性代數[編輯]
代數圖論的第一個分支用線性代數來研究圖，特別是研究圖的鄰接矩陣或拉普拉斯矩陣的譜（這部分代數圖論也被稱為譜圖理論）。以佩特森圖為例，鄰接矩陣的譜為(-2, -2, -2, -2, 1, 1, 1, 1, 1, 3)。通過一些定理把譜的性質與圖的其他性質聯繫起來。舉一個簡單的例子，對於直徑為D的連通圖，它的譜至少有D+1個不同的值[1]。圖的譜可用於分析網絡的同步。
使用群論[編輯]
代數圖論的第二個分支用群論來研究圖，尤其是自同構群以及幾何群論。重點是根據對稱性對圖進行分類，以及不同類別之間的包含關係。某些特殊類別的圖足夠少，可以把它們列舉出來。根據Frucht定理，所以的群都可以表示成連通圖的自同構群[2]。另外，給定一個群，可以作出相應的凱萊圖，凱萊圖有一些性質與群的結構相關[1]。
代數圖論的第二個分支與第一個分支有聯繫，因為圖的對稱性在圖的譜中也有反映。尤其是，對於高度對稱的圖，例如佩特森圖，不同的特徵值的數目很少[1]（佩特森圖有3個不同的特徵值，在直徑相等的圖中是最少的）。凱萊圖的譜與群的結構直接相關，尤其是與不可約特徵標相關[1][3]。
研究圖不變量[編輯]
最後，代數圖論的第三個分支研究圖不變量的代數性質，尤其是色多項式、Tutte多項式與扭結不變量。例如，圖的色多項式計算了頂點着色的個數。佩特森圖的色多項式為[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.