跳至內容

代數圖論

維基百科,自由的百科全書
佩特森圖,一種高度對稱的圖。它的直徑為2。其自同構群有120個元素,事實上就是對稱群

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

代數圖論的分支

使用線性代數

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

使用群論

交錯群凱萊圖,在三維空間中構成了截角四面體

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

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

研究圖不變量

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

最後,代數圖論的第三個分支研究圖不變量的代數性質,尤其是色多項式、Tutte多項式與扭結不變量。例如,圖的色多項式計算了頂點着色的個數。佩特森圖的色多項式為[1]。這意味着佩特森圖不能用1種或2種顏色着色,但可以用3種顏色着色,且着色方式有120種。代數圖論的這一領域的許多工作都是為了證明四色定理而啟發。可是仍然有許多未解決的問題,例如如何判定兩個圖的色多項式相同,以及如何判定一個多項式是不是某個圖的色多項式。

另見

參考資料

  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
  • Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, 207, New York: Springer-Verlag.