譜圖論

數學分支,研究圖的性質如何反映在相關矩陣的譜上

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

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

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

共譜圖

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

 
兩個共譜九面體,最小的一對共譜多面體圖

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

獨有的譜

 由譜決定(determined by its spectrum),意思是具有該譜的圖必與 同構。簡單例子包括:

共譜配偶

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

尋找共譜圖

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

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

奇格不等式

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

奇格常數

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

對於一幅 個頂點的圖 ,奇格常數 的定義,可用符號寫成:

 

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

不等式敍述

  正則時, 與度數及第二特徵值之差 (又稱「譜隙」)有關。多久克[9]阿隆米爾曼英語Vitali Milman二人[10]分別獨立證出以下不等式:[11]

 

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

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

 

式中 是(未歸一的)拉氏算子最小非平凡特徵值, 是最大度,而 是經歸一化的奇格常數:

 

其中 表示 中各頂點的度數和。

霍夫曼-德爾薩特不等式

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

  個頂點的 正則圖,且最小一個特徵值為 ,則 獨立數

 

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

對於一般不必正則的圖,考慮歸一化拉氏矩陣的最大特徵值 ,也能推導出類似的結論:[12]

 

式中  分別表示 的最大度和最小度。此為另一不等式[12]:109的特例:對於任意獨立集 ,有

 

其中 代表集合 中所有頂點的度數之和。

沿革

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

參見

參考文獻

  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. λ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 (英語). 
  11. ^ Hoory, Linial & Wigderson (2006)的Theorem 2.4。
  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 (英語). 
  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) (英語).