譜圖論

數學上，譜圖論（Template:Lang-en）是圖論的分支，研究图的性質與其邻接矩阵、调和矩阵等的特徵多項式、特征值和特征向量有何關聯。$n$個頂點的圖，其鄰接矩陣是$n\times n$矩陣，各分量分別以$0$或$1$表示對應的兩頂點之間是否有連邊。簡單無向圖的鄰接矩陣是實對稱矩陣，從而可Template:Link-en，其特徵值皆是實代數整數。

雖然鄰接矩陣取決於如何標記頂點以作排序，但是矩阵的谱是圖不變量，不取決於標記方式。（不過也不是完備不變量，不足以完全刻畫圖的全部性質。）

譜圖論亦關注藉圖的矩陣特徵值重數定義的參數，如Template:Link-en。

共譜圖

兩幅圖稱為「共譜」（Template:Lang）或「等譜」（Template:Lang），意思是兩者的鄰接矩陣Template:Link-en，特徵值不僅數值相等，連重數也一樣，即組成的多重集相等。

兩個共譜九面體，最小的一對共譜多面体图

共譜圖不必同構，但同構圖必然共譜。

獨有的譜

圖$G$由譜決定（Template:Lang），意思是具有該譜的圖必與$G$同構。簡單例子包括：

• 完全圖
• 有限Template:Link-en，即恰有一個頂點度數大於$2$的樹。

共譜配偶

若一對圖具有相同的譜，但是不同構，則稱為「共譜配偶」（Template:Lang）。最小一對共譜配偶是$\{K_{1,4},C_4\bigsqcup K_1\}$，前者是五個頂點的星，而後者是四個頂點的環，與獨一個頂點的不交並，如考拉茲和西诺戈维茨於1957年所述。最小一對多面體共譜配偶是兩個八頂點的九面體。

尋找共譜圖

幾乎所有树皆會與另一樹共譜。換言之，隨頂點數增加，有共譜樹的樹所佔比率趨於$1$。一對正則圖共譜當且僅當其補圖亦共譜。一對Template:Link-en共譜，當且僅當其相交陣列相等。

共譜圖亦可藉Template:Link-en構造。尚有另一類共譜圖，來自各種點線幾何。此種幾何中，以各點為頂點，有直線過兩點則連邊，可得「點共線圖」（Template:Lang）。反之，以直線為頂點，兩直線相交則連邊，可得「線相交圖」（Template:Lang）。兩幅圖必共譜，但經常不同構。

奇格不等式

黎曼几何中，對於緊黎曼流形$M$，有等周定理的推廣，稱為Template:Link-en。其斷言，$n$維區域$A\subseteq M$的體積一定時，邊界$\partial A$的面積不能太小，相比$A$的體積，比例常數有某個下界，與拉普拉斯－貝爾特拉米算子的特徵值有關。此不等式在圖論的離散情況下有類比，拉－貝二氏算子對應的概念是拉氏矩陣。譜圖論的奇格不等式在算法方面有應用，因為藉由拉氏算子的第二特徵值，可以估算圖的最小割之值。

奇格常數

Template:Main 图的奇格常數（Template:Lang），或作奇格數（Template:Lang）、等周數（Template:Lang），直觀理解是用作衡量該圖是否有「瓶頸」。多個學科需要衡量瓶頸程度，所以其用途包括：建造非常連通的计算机网络、洗牌、低維拓撲（尤其研究雙曲3流形時）。

對於一幅$n$個頂點的圖$G$，奇格常數$h(G)$的定義，可用符號寫成：

$h(G)=\underset{0<|S|\le \frac{n}{2}}{\min }\frac{|\partial (S)|}{|S|}.$

式中的最小值取遍一切大小不過半的非空頂點集合$S$，而$\partial (S)$表示$S$的邊邊界（Template:Lang），即恰有一端屬$S$的邊所組成的集。

不等式敍述

當$G$為$d$正則時，$h(G)$與度數及第二特徵值之差$d-{\lambda }_2$（又稱「譜隙」）有關。多久克及阿隆、Template:Link-en二人分別獨立證出以下不等式：

$\frac{1}{2}(d-{\lambda }_2)\le h(G)\le \sqrt{2d(d-{\lambda }_2)}.$

此不等式與马尔可夫链的Template:Link-en密切相關，亦是黎曼几何中，Template:Link-en的離散變式。

更一般情況，可考慮連通圖$G$，不必正則，此時金芳蓉的書Template:Rp中有另一條不等式：

$\frac{1}{2}\lambda \le 𝒉(G)\le \sqrt{2\mathrm{\Delta }\lambda },$

式中$\lambda$是（未歸一的）拉氏算子最小非平凡特徵值，$\mathrm{\Delta }$是最大度，而$𝒉(G)$是經歸一化的奇格常數：

$𝒉(G)=\underset{\mathrm{\varnothing }=S\subset V(G)}{\min }\frac{|\partial (S)|}{\min (\mathrm{v}\mathrm{o}\mathrm{l}(S),\mathrm{v}\mathrm{o}\mathrm{l}(\overline{S}))},$

其中$\mathrm{v}\mathrm{o}\mathrm{l}(Y)$表示$Y$中各頂點的度數和。

霍夫曼-德爾薩特不等式

對正則圖的獨立集大小，可用特徵值計算出一個上界，最先由Template:Link-en和菲利浦·德爾薩特（Template:Lang）證明。不等式的敍述如下：

設$G$是$n$個頂點的$k$正則圖，且最小一個特徵值為${\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}$，則$G$的獨立數

$\alpha (G)\le \frac{n}{1-\frac{k}{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}}}.$

此上界應用在合適的圖上，就能以代數方式證明Template:Link-en，以及有關有限域上子空間相交族的類似定理。

對於一般不必正則的圖，考慮歸一化拉氏矩陣的最大特徵值$\lambda {\text{'}}_{\mathrm{m}\mathrm{a}\mathrm{x}}$，也能推導出類似的結論：

$\alpha (G)\le n(1-\frac{1}{\lambda {\text{'}}_{\mathrm{m}\mathrm{a}\mathrm{x}}})\frac{\mathrm{\Delta }(G)}{\delta (G)},$

式中$\mathrm{\Delta }(G)$和$\delta (G)$分別表示$G$的最大度和最小度。此為另一不等式Template:Rp的特例：對於任意獨立集$X$，有

$\mathrm{v}\mathrm{o}\mathrm{l}(X)\le (1-\frac{1}{\lambda {\text{'}}_{\mathrm{m}\mathrm{a}\mathrm{x}}})\mathrm{v}\mathrm{o}\mathrm{l}(V(G)),$

其中$\mathrm{v}\mathrm{o}\mathrm{l}(Y)$代表集合$Y$中所有頂點的度數之和。

沿革

譜圖論在1950年代至1960年代逐漸出現。图论有研究圖的結構與譜性質之間有何聯繫，除此之外，量子化学研究亦是另一源頭，但兩個方向的研究互不流通，要到很後期才合而為一。1980年茨維特科維奇、杜布、薩克斯的專著《圖之譜》概括了當時本領域的多數研究，其後由1988年《圖譜論之近期成果》和《圖之譜》1995年第三版再次更新。2000年代，Template:Link-en開創離散幾何分析，並加以發展。此領域處理譜圖論的方式，是利用加權圖的離散拉氏算子，在Template:Link-en等領域有應用。近來，譜圖論應用廣泛，用於分析一些現實（如信號處理時）可能會遇到的圖。

參見

• Template:Link-en
• 代数连通度
• 代数图论
• 譜聚類
• Template:Link-en
• Template:Link-en
• Template:Link-en
• 扩展图

參考文獻

• Template:Cite journal