谱图论

两幅图称为“共谱”（cospectral）或“等谱”（isospectral），意思是两者的邻接矩阵等谱（英语：isospectral），特征值不仅数值相等，连重数也一样，即组成的多重集相等。

共谱图不必同构，但同构图必然共谱。

独有的谱

图${\displaystyle G}$ 由谱决定（determined by its spectrum），意思是具有该谱的图必与${\displaystyle G}$ 同构。简单例子包括：

• 完全图
• 有限星状树（英语：starlike tree），即恰有一个顶点度数大于${\displaystyle 2}$ 的树。

共谱配偶

若一对图具有相同的谱，但是不同构，则称为“共谱配偶”（cospectral mates）。最小一对共谱配偶是${\displaystyle \{K_{1,4},C_{4}\sqcup K_{1}\}}$ ，前者是五个顶点的星，而后者是四个顶点的环，与独一个顶点的不交并，如科拉茨（英语：Lothar Collatz）和西诺戈维茨于1957年所述。^[1][2]最小一对多面体共谱配偶是两个八顶点的九面体。^[3]

寻找共谱图

几乎所有树皆会与另一树共谱。换言之，随顶点数增加，有共谱树的树所占比率趋于${\displaystyle 1}$ 。^[4]一对正则图共谱当且仅当其补图亦共谱。^[5]一对距离正则图（英语：distance-regular graph）共谱，当且仅当其相交阵列相等。

共谱图亦可藉砂田方法（英语：isospectral）构造。^[6]尚有另一类共谱图，来自各种点线几何。此种几何中，以各点为顶点，有直线过两点则连边，可得“点共线图”（point-collinearity graph）。反之，以直线为顶点，两直线相交则连边，可得“线相交图”（line-intersection graph）。两幅图必共谱，但经常不同构。^[7]

黎曼几何中，对于紧黎曼流形${\displaystyle M}$ ，有等周定理的推广，称为奇格不等式（英语：Cheeger constant）。其断言，${\displaystyle n}$ 维区域${\displaystyle A\subseteq M}$ 的体积一定时，边界${\displaystyle \partial A}$ 的面积不能太小，相比${\displaystyle A}$ 的体积，比例常数有某个下界，与拉普拉斯－贝尔特拉米算子的特征值有关。此不等式在图论的离散情况下有类比，拉－贝二氏算子对应的概念是拉氏矩阵。谱图论的奇格不等式在算法方面有应用，因为借由拉氏算子的第二特征值，可以估算图的最小割之值。

奇格常数

图的奇格常数（Cheeger constant），或作奇格数（Cheeger number）、等周数（isoperimetric number），直观理解是用作衡量该图是否有“瓶颈”。多个学科需要衡量瓶颈程度，所以其用途包括：建造非常连通的计算机网络、洗牌、低维拓扑（尤其研究双曲3流形时）。

对于一幅${\displaystyle n}$ 个顶点的图${\displaystyle G}$ ，奇格常数${\displaystyle h(G)}$ 的定义，可用符号写成：

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

式中的最小值取遍一切大小不过半的非空顶点集合${\displaystyle S}$ ，而${\displaystyle \partial (S)}$ 表示${\displaystyle S}$ 的边边界（edge boundary），即恰有一端属${\displaystyle S}$ 的边所组成的集。^[8]

不等式叙述

当${\displaystyle G}$ 为${\displaystyle d}$ 正则时，${\displaystyle h(G)}$ 与度数及第二特征值之差${\displaystyle d-\lambda _{2}}$ （又称“谱隙”）有关。多久克^[9]及阿隆、米尔曼（英语：Vitali Milman）二人^[10]分别独立证出以下不等式：^[11]

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

此不等式与马尔可夫链的奇格界（英语：Cheeger bound）密切相关，亦是黎曼几何中，奇格不等式（英语：Cheeger constant）的离散变式。

更一般情况，可考虑连通图${\displaystyle G}$ ，不必正则，此时金芳蓉的书^[12]:35中有另一条不等式：

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

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

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

其中${\displaystyle {\mathrm {vol} }(Y)}$ 表示${\displaystyle Y}$ 中各顶点的度数和。

对正则图的独立集大小，可用特征值计算出一个上界，最先由艾伦·霍夫曼（英语：Alan J. Hoffman）和菲利浦·德尔萨特（Philippe Delsarte）证明。^[13]不等式的叙述如下：

设${\displaystyle G}$ 是${\displaystyle n}$ 个顶点的${\displaystyle k}$ 正则图，且最小一个特征值为${\displaystyle \lambda _{\mathrm {min} }}$ ，则${\displaystyle G}$ 的独立数

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

此上界应用在合适的图上，就能以代数方式证明艾狄胥-柯-雷多定理（英语：Erdős–Ko–Rado theorem），以及有关有限域上子空间相交族的类似定理。^[14]

对于一般不必正则的图，考虑归一化拉氏矩阵的最大特征值${\displaystyle \lambda '_{\mathrm {max} }}$ ，也能推导出类似的结论：^[12]

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

式中${\displaystyle \Delta (G)}$ 和${\displaystyle \delta (G)}$ 分别表示${\displaystyle G}$ 的最大度和最小度。此为另一不等式^[12]:109的特例：对于任意独立集${\displaystyle X}$ ，有

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

其中${\displaystyle {\mathrm {vol} }(Y)}$ 代表集合${\displaystyle Y}$ 中所有顶点的度数之和。

谱图论在1950年代至1960年代逐渐出现。图论有研究图的结构与谱性质之间有何联系，除此之外，量子化学研究亦是另一源头，但两个方向的研究互不流通，要到很后期才合而为一。^[15]1980年茨维特科维奇、杜布、萨克斯的专著《图之谱》^[16]概括了当时本领域的多数研究，其后由1988年《图谱论之近期成果》^[17]和《图之谱》1995年第三版再次更新。^[15]2000年代，砂田利一（英语：Toshikazu Sunada）开创离散几何分析，并加以发展。此领域处理谱图论的方式，是利用加权图的离散拉氏算子，^[18]在形状分析（英语：Spectral shape analysis）等领域有应用。近来，谱图论应用广泛，用于分析一些现实（如信号处理时）可能会遇到的图。^{[19][20][21][22]}

• 强正则图（英语：Strongly regular graph）
• 代数连通度
• 代数图论
• 谱聚类（粤语：譜聚類）
• 谱形分析（英语：Spectral shape analysis）
• 埃斯特拉达指标（英语：Estrada index）
• 洛瓦兹数ϑ（英语：Lovász number）
• 扩展图

• 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） （英语）.