譜圖論
數學上,譜圖論(英語:spectral graph theory)是圖論的分支,研究圖的性質與其鄰接矩陣、調和矩陣等的特徵多項式、特徵值和特徵向量有何關聯。個頂點的圖,其鄰接矩陣是矩陣,各分量分別以或表示對應的兩頂點之間是否有連邊。簡單無向圖的鄰接矩陣是實對稱矩陣,從而可正交對角化,其特徵值皆是實代數整數。
雖然鄰接矩陣取決於如何標記頂點以作排序,但是矩陣的譜是圖不變量,不取決於標記方式。(不過也不是完備不變量,不足以完全刻畫圖的全部性質。)
譜圖論亦關注藉圖的矩陣特徵值重數定義的參數,如科蘭·德韋迪耶爾數。
共譜圖
兩幅圖稱為「共譜」(cospectral)或「等譜」(isospectral),意思是兩者的鄰接矩陣等譜,特徵值不僅數值相等,連重數也一樣,即組成的多重集相等。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Isospectral_enneahedra.svg/300px-Isospectral_enneahedra.svg.png)
共譜圖不必同構,但同構圖必然共譜。
獨有的譜
圖由譜決定(determined by its spectrum),意思是具有該譜的圖必與同構。簡單例子包括:
共譜配偶
若一對圖具有相同的譜,但是不同構,則稱為「共譜配偶」(cospectral mates)。最小一對共譜配偶是,前者是五個頂點的星,而後者是四個頂點的環,與獨一個頂點的不交並,如考拉茲和西諾戈維茨於1957年所述。[1][2]最小一對多面體共譜配偶是兩個八頂點的九面體。[3]
尋找共譜圖
幾乎所有樹皆會與另一樹共譜。換言之,隨頂點數增加,有共譜樹的樹所佔比率趨於。[4]一對正則圖共譜當且僅當其補圖亦共譜。[5]一對距離正則圖共譜,當且僅當其相交陣列相等。
共譜圖亦可藉砂田方法構造。[6]尚有另一類共譜圖,來自各種點線幾何。此種幾何中,以各點為頂點,有直線過兩點則連邊,可得「點共線圖」(point-collinearity graph)。反之,以直線為頂點,兩直線相交則連邊,可得「線相交圖」(line-intersection graph)。兩幅圖必共譜,但經常不同構。[7]
奇格不等式
黎曼幾何中,對於緊黎曼流形,有等周定理的推廣,稱為奇格不等式。其斷言,維區域的體積一定時,邊界的面積不能太小,相比的體積,比例常數有某個下界,與拉普拉斯-貝爾特拉米算子的特徵值有關。此不等式在圖論的離散情況下有類比,拉-貝二氏算子對應的概念是拉氏矩陣。譜圖論的奇格不等式在算法方面有應用,因為藉由拉氏算子的第二特徵值,可以估算圖的最小割之值。
奇格常數
圖的奇格常數(Cheeger constant),或作奇格數(Cheeger number)、等周數(isoperimetric number),直觀理解是用作衡量該圖是否有「瓶頸」。多個學科需要衡量瓶頸程度,所以其用途包括:建造非常連通的計算機網絡、洗牌、低維拓撲(尤其研究雙曲3流形時)。
對於一幅個頂點的圖,奇格常數的定義,可用符號寫成:
式中的最小值取遍一切大小不過半的非空頂點集合,而表示的邊邊界(edge boundary),即恰有一端屬的邊所組成的集。[8]
不等式敍述
當為正則時,與度數及第二特徵值之差(又稱「譜隙」)有關。多久克[9]及阿隆、米爾曼二人[10]分別獨立證出以下不等式:[11]
此不等式與馬爾可夫鏈的奇格界密切相關,亦是黎曼幾何中,奇格不等式的離散變式。
更一般情況,可考慮連通圖,不必正則,此時金芳蓉的書[12]:35中有另一條不等式:
式中是(未歸一的)拉氏算子最小非平凡特徵值,是最大度,而是經歸一化的奇格常數:
其中表示中各頂點的度數和。
霍夫曼-德爾薩特不等式
對正則圖的獨立集大小,可用特徵值計算出一個上界,最先由艾倫·霍夫曼和菲利浦·德爾薩特(Philippe Delsarte)證明。[13]不等式的敍述如下:
設是個頂點的正則圖,且最小一個特徵值為,則的獨立數
此上界應用在合適的圖上,就能以代數方式證明艾狄胥-柯-雷多定理,以及有關有限域上子空間相交族的類似定理。[14]
對於一般不必正則的圖,考慮歸一化拉氏矩陣的最大特徵值,也能推導出類似的結論:[12]
式中和分別表示的最大度和最小度。此為另一不等式[12]:109的特例:對於任意獨立集,有
其中代表集合中所有頂點的度數之和。
沿革
譜圖論在1950年代至1960年代逐漸出現。圖論有研究圖的結構與譜性質之間有何聯繫,除此之外,量子化學研究亦是另一源頭,但兩個方向的研究互不流通,要到很後期才合而為一。[15]1980年茨維特科維奇、杜布、薩克斯的專著《圖之譜》[16]概括了當時本領域的多數研究,其後由1988年《圖譜論之近期成果》[17]和《圖之譜》1995年第三版再次更新。[15]2000年代,砂田利一開創離散幾何分析,並加以發展。此領域處理譜圖論的方式,是利用加權圖的離散拉氏算子,[18]在形狀分析等領域有應用。近來,譜圖論應用廣泛,用於分析一些現實(如信號處理時)可能會遇到的圖。[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. λ1, isoperimetric inequalities for graphs, and superconcentrators [λ1、圖之等周不等式、超集中器]. 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) (英語).