譜圖論

數學上，譜圖論（英語：spectral graph theory）是圖論的分支，研究圖的性質與其鄰接矩陣、調和矩陣等的特徵多項式、特徵值和特徵向量有何關聯。 $n$ 個頂點的圖，其鄰接矩陣是 $n\times n$ 矩陣，各分量分別以 $0$ 或 $1$ 表示對應的兩頂點之間是否有連邊。簡單無向圖的鄰接矩陣是實對稱矩陣，從而可正交對角化（英語：Orthogonal diagonalization），其特徵值皆是實代數整數。

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

譜圖論亦關注藉圖的矩陣特徵值重數定義的參數，如科蘭·德韋迪耶爾數（英語：Colin de Verdière graph invariant）。

共譜圖

兩幅圖稱為「共譜」（cospectral）或「等譜」（isospectral），意思是兩者的鄰接矩陣等譜（英語：isospectral），特徵值不僅數值相等，連重數也一樣，即組成的多重集相等。

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

獨有的譜

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

完全圖
有限星狀樹（英語：starlike tree），即恰有一個頂點度數大於 $2$ 的樹。

共譜配偶

若一對圖具有相同的譜，但是不同構，則稱為「共譜配偶」（cospectral mates）。最小一對共譜配偶是 $\{K_{1,4},C_{4}\sqcup K_{1}\}$ ，前者是五個頂點的星，而後者是四個頂點的環，與獨一個頂點的不交並，如考拉茲和西諾戈維茨於1957年所述。^[1]^[2]最小一對多面體共譜配偶是兩個八頂點的九面體。^[3]

尋找共譜圖

幾乎所有樹皆會與另一樹共譜。換言之，隨頂點數增加，有共譜樹的樹所佔比率趨於 $1$ 。^[4]一對正則圖共譜當且僅當其補圖亦共譜。^[5]一對距離正則圖（英語：distance-regular graph）共譜，當且僅當其相交陣列相等。

共譜圖亦可藉砂田方法（英語：isospectral）構造。^[6]尚有另一類共譜圖，來自各種點線幾何。此種幾何中，以各點為頂點，有直線過兩點則連邊，可得「點共線圖」（point-collinearity graph）。反之，以直線為頂點，兩直線相交則連邊，可得「線相交圖」（line-intersection graph）。兩幅圖必共譜，但經常不同構。^[7]

奇格不等式

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

奇格常數

圖的奇格常數（Cheeger constant），或作奇格數（Cheeger number）、等周數（isoperimetric number），直觀理解是用作衡量該圖是否有「瓶頸」。多個學科需要衡量瓶頸程度，所以其用途包括：建造非常連通的計算機網絡、洗牌、低維拓撲（尤其研究雙曲3流形時）。

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

h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}}.

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

不等式敍述

當 $G$ 為 $d$ 正則時， $h(G)$ 與度數及第二特徵值之差 $d-\lambda _{2}$ （又稱「譜隙」）有關。多久克^[9]及阿隆、米爾曼（英語：Vitali Milman）二人^[10]分別獨立證出以下不等式：^[11]

{\frac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.

此不等式與馬爾可夫鏈的奇格界（英語：Cheeger bound）密切相關，亦是黎曼幾何中，奇格不等式（英語：Cheeger constant）的離散變式。

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

{\frac {1}{2}}{\lambda }\leq {\boldsymbol {h}}(G)\leq {\sqrt {2\Delta \lambda }},

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

{\boldsymbol {h}}(G)=\min _{\emptyset \not =S\subset V(G)}{\frac {|\partial (S)|}{\min({\mathrm {vol} }(S),{\mathrm {vol} }({\bar {S}}))}},

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

霍夫曼-德爾薩特不等式

對正則圖的獨立集大小，可用特徵值計算出一個上界，最先由艾倫·霍夫曼（英語：Alan J. Hoffman）和菲利浦·德爾薩特（Philippe Delsarte）證明。^[13]不等式的敍述如下：

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

$\alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}.$

此上界應用在合適的圖上，就能以代數方式證明艾狄胥-柯-雷多定理（英語：Erdős–Ko–Rado theorem），以及有關有限域上子空間相交族的類似定理。^[14]

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

\alpha (G)\leq n\left(1-{\frac {1}{\lambda '_{\mathrm {max} }}}\right){\frac {\Delta (G)}{\delta (G)}},

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

{\mathrm {vol} }(X)\leq \left(1-{\frac {1}{\lambda '_{\mathrm {max} }}}\right){\mathrm {vol} }(V(G)),

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

沿革

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

參見

參考文獻

^ Collatz, Lothar; Sinogowitz, Ulrich. Spektren endlicher Grafen [有限圖之譜]. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 1957, 21: 63–77. doi:10.1007/BF02941924 （德語）.
^ Weisstein, Eric W. (編). Cospectral Graphs. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
^ Hosoya, Haruo; Nagashima, Umpei; Hyugaji, Sachiko. Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices [拓撲孿生圖。最小一對八頂點等譜多面體圖]. Journal of Chemical Information and Modeling. 1994, 34 (2): 428–431. doi:10.1021/ci00018a033 （英語）.
^ Schwenk, A. J. Almost All Trees are Cospectral [幾乎全體樹皆共譜]. Harary, Frank (編). New Directions in the Theory of Graphs [圖論之新方向]. New York: Academic Press. 1973: 275–307. ISBN 012324255X. OCLC 890297242 （英語）.
^ Godsil, Chris. Are Almost All Graphs Cospectral? [幾乎所有圖皆共譜嗎？] (PDF). 2007-11-07 [2022-01-04]. （原始內容 (PDF)存檔於2022-01-04）（英語）.
^ Sunada, Toshikazu. Riemannian coverings and isospectral manifolds [黎曼覆疊和等譜流形]. Ann. of Math. 1985, 121 (1): 169–186. JSTOR 1971195. doi:10.2307/1971195 （英語）.
^ Brouwer, Andries; Haemers, Willem H. §14.2.2 Partial linear spaces [第14.2.2小節：半線性空間]. Spectra of Graphs [圖之譜] (PDF). Springer. 2011 [2022-02-18]. （原始內容 (PDF)存檔於2022-02-04）（英語）.
^ Hoory, Linial & Wigderson (2006)的Definition 2.1
^ Dodziuk, J. Difference Equations, Isoperimetric inequality and Transience of Certain Random Walks [差分方程、等周不等式、某隨機遊走之暫現]. Trans. Amer. Math. Soc. 1984, 284 (2): 787–794 （英語）.
^ Alon, N.; Milman, V. D. λ₁, isoperimetric inequalities for graphs, and superconcentrators [λ₁、圖之等周不等式、超集中器]. Journal of Combinatorial Theory, Series B. 1985, 38 (1): 73–88. MR 0782626. doi:10.1016/0095-8956(85)90092-9 （英語）.
^ Hoory, Linial & Wigderson (2006)的Theorem 2.4。
^ ^12.0 ^12.1 ^12.2 Chung, Fan. Spectral Graph Theory [譜圖論]. Providence, R. I.: American Mathematical Society. 1997 [2022-01-10]. ISBN 0821803158. MR 1421568. （原始內容存檔於2020-02-14）（英語）前四章可於網頁查閱
^ Godsil, Chris. Erdős-Ko-Rado Theorems [艾狄胥-柯-雷多諸定理] (PDF). 2009-05 [2022-01-05]. （原始內容 (PDF)存檔於2022-01-20）（英語）.
^ Godsil, Christopher; Meagher, Karen. Erdős–Ko–Rado theorems: algebraic approaches [艾狄胥-柯-雷多諸定理：代數進路]. Cambridge, United Kingdom. 2016. ISBN 9781107128446. OCLC 935456305. doi:10.1017/CBO9781316414958 （英語）.
^ ^15.0 ^15.1 Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan. Eigenspaces of Graphs [圖之本徵空間]. Cambridge University Press. 1997. ISBN 0-521-57352-1. doi:10.1017/CBO9781139086547 （英語）.
^ Cvetković, Dragoš M.; Doob, Michael; Sachs, Horst. Spectra of Graphs [圖之譜]. New York: Academic Press. 1980 （英語）.
^ Cvetković, Dragoš M.; Doob, Michael; Gutman, Ivan; Torgasev, A. Recent Results in the Theory of Graph Spectra [圖譜論之近期成果]. Annals of Discrete mathematics 36. 1988 [2022-01-05]. ISBN 0-444-70361-6. doi:10.1016/s0167-5060(08)x7010-4. （原始內容存檔於2017-11-05）（英語）.
^ Sunada, Toshikazu. Discrete geometric analysis [離散幾何分析]. Proceedings of Symposia in Pure Mathematics. 2008, 77: 51–86. ISBN 9780821844717. doi:10.1090/pspum/077/2459864 （英語）.
^ Shuman, David I; Ricaud, Benjamin; Vandergheynst, Pierre. Vertex-frequency analysis on graphs [圖上的頂點頻率分析]. Applied and Computational Harmonic Analysis. March 2016, 40 (2): 260–291. ISSN 1063-5203. arXiv:1307.5708 . doi:10.1016/j.acha.2015.02.005 （英語）.
^ Stankovic, Ljubisa; Dakovic, Milos; Sejdic, Ervin. Vertex-Frequency Analysis: A Way to Localize Graph Spectral Components [Lecture Notes] [頂點頻率分析：局部化圖譜分量的方法 [講義]]. IEEE Signal Processing Magazine. July 2017, 34 (4): 176–182. Bibcode:2017ISPM...34..176S. ISSN 1053-5888. doi:10.1109/msp.2017.2696572 （英語）.
^ Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi. Spectral Graph Wavelets and Filter Banks With Low Approximation Error [譜圖小波和低近似誤差的濾波器組]. IEEE Transactions on Signal and Information Processing over Networks. September 2016, 2 (3): 230–245. ISSN 2373-776X. doi:10.1109/tsipn.2016.2581303 （英語）.
^ Behjat, Hamid; Richter, Ulrike; Van De Ville, Dimitri; Sornmo, Leif. Signal-Adapted Tight Frames on Graphs [圖上適應訊號的緊標架]. IEEE Transactions on Signal Processing. 2016-11-15, 64 (22): 6017–6029 [2022-01-05]. Bibcode:2016ITSP...64.6017B. ISSN 1053-587X. doi:10.1109/tsp.2016.2591513. （原始內容存檔於2022-01-05）（英語）.

Hoory, Shlomo; Linial, Nathan; Wigderson, Avi. Expander graphs and their applications [擴展圖及其應用] (PDF). Bulletin (New Series) of the American Mathematical Society. 2006-10, 43 (4): 439–561 [2022-02-18]. doi:10.1090/S0273-0979-06-01126-8. （原始內容 (PDF)存檔於2022-01-13）（英語）.

[1] Collatz, Lothar; Sinogowitz, Ulrich. Spektren endlicher Grafen [有限圖之譜]. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 1957, 21: 63–77. doi:10.1007/BF02941924 （德語）.

[2] Weisstein, Eric W. (編). Cospectral Graphs. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.

[3] Hosoya, Haruo; Nagashima, Umpei; Hyugaji, Sachiko. Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices [拓撲孿生圖。最小一對八頂點等譜多面體圖]. Journal of Chemical Information and Modeling. 1994, 34 (2): 428–431. doi:10.1021/ci00018a033 （英語）.

[4] Schwenk, A. J. Almost All Trees are Cospectral [幾乎全體樹皆共譜]. Harary, Frank (編). New Directions in the Theory of Graphs [圖論之新方向]. New York: Academic Press. 1973: 275–307. ISBN 012324255X. OCLC 890297242 （英語）.

[5] Godsil, Chris. Are Almost All Graphs Cospectral? [幾乎所有圖皆共譜嗎？] (PDF). 2007-11-07 [2022-01-04]. （原始內容 (PDF)存檔於2022-01-04）（英語）.

[6] Sunada, Toshikazu. Riemannian coverings and isospectral manifolds [黎曼覆疊和等譜流形]. Ann. of Math. 1985, 121 (1): 169–186. JSTOR 1971195. doi:10.2307/1971195 （英語）.

[7] Brouwer, Andries; Haemers, Willem H. §14.2.2 Partial linear spaces [第14.2.2小節：半線性空間]. Spectra of Graphs [圖之譜] (PDF). Springer. 2011 [2022-02-18]. （原始內容 (PDF)存檔於2022-02-04）（英語）.

[8] Hoory, Linial & Wigderson (2006)的Definition 2.1

[9] Dodziuk, J. Difference Equations, Isoperimetric inequality and Transience of Certain Random Walks [差分方程、等周不等式、某隨機遊走之暫現]. Trans. Amer. Math. Soc. 1984, 284 (2): 787–794 （英語）.

[10] Alon, N.; Milman, V. D. λ₁, isoperimetric inequalities for graphs, and superconcentrators [λ₁、圖之等周不等式、超集中器]. Journal of Combinatorial Theory, Series B. 1985, 38 (1): 73–88. MR 0782626. doi:10.1016/0095-8956(85)90092-9 （英語）.

[11] Hoory, Linial & Wigderson (2006)的Theorem 2.4。

[chung-12] 12.0 ^12.1 ^12.2 Chung, Fan. Spectral Graph Theory [譜圖論]. Providence, R. I.: American Mathematical Society. 1997 [2022-01-10]. ISBN 0821803158. MR 1421568. （原始內容存檔於2020-02-14）（英語）前四章可於網頁查閱

[13] Godsil, Chris. Erdős-Ko-Rado Theorems [艾狄胥-柯-雷多諸定理] (PDF). 2009-05 [2022-01-05]. （原始內容 (PDF)存檔於2022-01-20）（英語）.

[14] Godsil, Christopher; Meagher, Karen. Erdős–Ko–Rado theorems: algebraic approaches [艾狄胥-柯-雷多諸定理：代數進路]. Cambridge, United Kingdom. 2016. ISBN 9781107128446. OCLC 935456305. doi:10.1017/CBO9781316414958 （英語）.

[cvet2-15] 15.0 ^15.1 Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan. Eigenspaces of Graphs [圖之本徵空間]. Cambridge University Press. 1997. ISBN 0-521-57352-1. doi:10.1017/CBO9781139086547 （英語）.

[16] Cvetković, Dragoš M.; Doob, Michael; Sachs, Horst. Spectra of Graphs [圖之譜]. New York: Academic Press. 1980 （英語）.

[17] Cvetković, Dragoš M.; Doob, Michael; Gutman, Ivan; Torgasev, A. Recent Results in the Theory of Graph Spectra [圖譜論之近期成果]. Annals of Discrete mathematics 36. 1988 [2022-01-05]. ISBN 0-444-70361-6. doi:10.1016/s0167-5060(08)x7010-4. （原始內容存檔於2017-11-05）（英語）.

[18] Sunada, Toshikazu. Discrete geometric analysis [離散幾何分析]. Proceedings of Symposia in Pure Mathematics. 2008, 77: 51–86. ISBN 9780821844717. doi:10.1090/pspum/077/2459864 （英語）.

[19] Shuman, David I; Ricaud, Benjamin; Vandergheynst, Pierre. Vertex-frequency analysis on graphs [圖上的頂點頻率分析]. Applied and Computational Harmonic Analysis. March 2016, 40 (2): 260–291. ISSN 1063-5203. arXiv:1307.5708 . doi:10.1016/j.acha.2015.02.005 （英語）.

[20] Stankovic, Ljubisa; Dakovic, Milos; Sejdic, Ervin. Vertex-Frequency Analysis: A Way to Localize Graph Spectral Components [Lecture Notes] [頂點頻率分析：局部化圖譜分量的方法 [講義]]. IEEE Signal Processing Magazine. July 2017, 34 (4): 176–182. Bibcode:2017ISPM...34..176S. ISSN 1053-5888. doi:10.1109/msp.2017.2696572 （英語）.

[21] Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi. Spectral Graph Wavelets and Filter Banks With Low Approximation Error [譜圖小波和低近似誤差的濾波器組]. IEEE Transactions on Signal and Information Processing over Networks. September 2016, 2 (3): 230–245. ISSN 2373-776X. doi:10.1109/tsipn.2016.2581303 （英語）.

[22] Behjat, Hamid; Richter, Ulrike; Van De Ville, Dimitri; Sornmo, Leif. Signal-Adapted Tight Frames on Graphs [圖上適應訊號的緊標架]. IEEE Transactions on Signal Processing. 2016-11-15, 64 (22): 6017–6029 [2022-01-05]. Bibcode:2016ITSP...64.6017B. ISSN 1053-587X. doi:10.1109/tsp.2016.2591513. （原始內容存檔於2022-01-05）（英語）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]