text: 代數圖論是用代數方法處理圖論問題的數學分支。這不同於幾何、組合或演算法的方法。代數圖論有三個主要分支，分別使用線性代數，使用群論，以及研究圖不變數。代數圖論的分支.使用線性代數.代數圖論的第一個分支用線性代數來研究圖，特別是研究圖的鄰接矩陣或拉普拉斯矩陣的譜。以佩特森圖為例，鄰接矩陣的譜為(-2, -2, -2, -2, 1, 1, 1, 1, 1, 3)。透過一些定理把譜的性質與圖的其他性質聯絡起來。舉一個簡單的例子，對於直徑為D的連通圖，它的譜至少有D+1個不同的值。圖的譜可用於分析網路的同步。使用群論.代數圖論的第二個分支用群論來研究圖，尤其是自同構群以及幾何群論。重點是根據對稱性對圖進行分類，以及不同類別之間的包含關係。某些特殊類別的圖足夠少，可以把它們列舉出來。根據Frucht定理，所以的群都可以表示成連通圖的自同構群。另外，給定一個群，可以作出相應的凱萊圖，凱萊圖有一些性質與群的結構相關。代數圖論的第二個分支與第一個分支有聯絡，因為圖的對稱性在圖的譜中也有反映。尤其是，對於高度對稱的圖，例如佩特森圖，不同的特徵值的數目很少。凱萊圖的譜與群的結構直接相關，尤其是與不可約特徵標相關。研究圖不變數.最後，代數圖論的第三個分支研究圖不變數的代數性質，尤其是色多項式、Tutte多項式與扭結不變數。例如，圖的色多項式計算了頂點著色的個數。佩特森圖的色多項式為formula_1。這意味著佩特森圖不能用1種或2種顏色著色，但可以用3種顏色著色，且著色方式有120種。代數圖論的這一領域的許多工作都是為了證明四色定理而啟發。可是仍然有許多未解決的問題，例如如何判定兩個圖的色多項式相同，以及如何判定一個多項式是不是某個圖的色多項式。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 代數圖論
metadata: https://zh.wikipedia.org/wiki?curid=6535125