谱图论

数学上，谱图论（英语：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]