谱图论

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

数学上,谱图论(英语: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) (英语).