數學上，譜圖論（）是圖論的分支，研究图的性質與其邻接矩阵、调和矩阵等的特徵多項式、特征值和特征向量有何關聯。n個頂點的圖，其鄰接矩陣是n\times n矩陣，各分量分別以0或1表示對應的兩頂點之間是否有連邊。簡單無向圖的鄰接矩陣是實對稱矩陣，從而可，其特徵值皆是實代數整數。
雖然鄰接矩陣取決於如何標記頂點以作排序，但是矩阵的谱是圖不變量，不取決於標記方式。（不過也不是完備不變量，不足以完全刻畫圖的全部性質。）
譜圖論亦關注藉圖的矩陣特徵值重數定義的參數，如。
共譜圖
兩幅圖稱為「共譜」（）或「等譜」（），意思是兩者的鄰接矩陣，特徵值不僅數值相等，連重數也一樣，即組成的多重集相等。
，最小的一對共譜多面体图 ]]
共譜圖不必同構，但同構圖必然共譜。
獨有的譜
圖G由譜決定（），意思是具有該譜的圖必與G同構。簡單例子包括：
- 完全圖
- 有限，即恰有一個頂點度數大於2的樹。
共譜配偶
若一對圖具有相同的譜，但是不同構，則稱為「共譜配偶」（）。最小一對共譜配偶是\{K_{1, 4}, C_4 \sqcup K_1\}，前者是五個頂點的星，而後者是四個頂點的環，與獨一個頂點的不交並，如考拉茲和西诺戈维茨於1957年所述。最小一對多面體共譜配偶是兩個八頂點的九面體。
尋找共譜圖
幾乎所有树皆會與另一樹共譜。換言之，隨頂點數增加，有共譜樹的樹所佔比率趨於1。一對正則圖共譜當且僅當其補圖亦共譜。一對共譜，當且僅當其相交陣列相等。
共譜圖亦可藉構造。尚有另一類共譜圖，來自各種點線幾何。此種幾何中，以各點為頂點，有直線過兩點則連邊，可得「點共線圖」（）。反之，以直線為頂點，兩直線相交則連邊，可得「線相交圖」（）。兩幅圖必共譜，但經常不同構。
奇格不等式
黎曼几何中，對於緊黎曼流形M，有等周定理的推廣，稱為。其斷言，n維區域A\subseteq M的體積一定時，邊界\partial A的面積不能太小，相比A的體積，比例常數有某個下界，與拉普拉斯－貝爾特拉米算子的特徵值有關。此不等式在圖論的離散情況下有類比，拉－貝二氏算子對應的概念是拉氏矩陣。譜圖論的奇格不等式在算法方面有應用，因為藉由拉氏算子的第二特徵值，可以估算圖的最小割之值。
奇格常數
图的奇格常數（），或作奇格數（）、等周數（），直觀理解是用作衡量該圖是否有「瓶頸」。多個學科需要衡量瓶頸程度，所以其用途包括：建造非常連通的计算机网络、洗牌、低維拓撲（尤其研究雙曲3流形時）。
對於一幅n個頂點的圖G，奇格常數h(G)的定義，可用符號寫成：
: h(G) = \min_{0
式中的最小值取遍一切大小不過半的非空頂點集合S，而\partial (S)表示S的邊邊界（），即恰有一端屬S的邊所組成的集。
不等式敍述
當G為d正則時，h(G)與度數及第二特徵值之差d - \lambda_2（又稱「譜隙」）有關。多久克及阿隆、二人分別獨立證出以下不等式：
: \frac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.
此不等式與马尔可夫链的密切相關，亦是黎曼几何中，的離散變式。
更一般情況，可考慮連通圖G，不必正則，此時金芳蓉的書中有另一條不等式：
: \frac{1}{2} {\lambda} \le {\boldsymbol h}(G) \le \sqrt{2 \Delta \lambda},
式中\lambda是（未歸一的）拉氏算子最小非平凡特徵值，\Delta是最大度，而{\boldsymbol h}(G)是經歸一化的奇格常數：
: {\boldsymbol h}(G) = \min_{\emptyset \not =S\subset V(G)}\frac{\min({\mathrm{vol}}(S), {\mathrm{vol}}(\bar{S}))},
其中{\mathrm{vol}}(Y)表示Y中各頂點的度數和。
霍夫曼-德爾薩特不等式
對正則圖的獨立集大小，可用特徵值計算出一個上界，最先由和菲利浦·德爾薩特（）證明。不等式的敍述如下：
設G是n個頂點的k正則圖，且最小一個特徵值為\lambda_{\mathrm{min}}，則G的獨立數
:\alpha(G) \leq \frac{n}{1 - \frac{k}{\lambda_{\mathrm{min}}}}.
此上界應用在合適的圖上，就能以代數方式證明，以及有關有限域上子空間相交族的類似定理。
對於一般不必正則的圖，考慮歸一化拉氏矩陣的最大特徵值 \lambda'_\mathrm {max}，也能推導出類似的結論：1980年茨維特科維奇、杜布、薩克斯的專著《圖之譜》概括了當時本領域的多數研究，其後由1988年《圖譜論之近期成果》和《圖之譜》1995年第三版再次更新。在等領域有應用。近來，譜圖論應用廣泛，用於分析一些現實（如信號處理時）可能會遇到的圖。
參見
- 強正則圖
- 代数连通度
- 代数图论
- 譜聚類
*
*
*
- 扩展图
參考文獻
*
评论 (0)