数学上，谱图论（英语：spectral graph theory）是图论的分支，研究图的性质与其邻接矩阵、调和矩阵等的特征多项式、特征值和特征向量有何关联。个顶点的图，其邻接矩阵是矩阵，各分量分别以或表示对应的两顶点之间是否有连边。简单无向图的邻接矩阵是实对称矩阵，从而可正交对角化，其特征值皆是实代数整数。
虽然邻接矩阵取决于如何标记顶点以作排序，但是矩阵的谱是图不变量，不取决于标记方式。（不过也不是完备不变量，不足以完全刻画图的全部性质。）
谱图论亦关注藉图的矩阵特征值重数定义的参数，如科兰·德韦迪耶尔数。
共谱图
两幅图称为“共谱”（cospectral）或“等谱”（isospectral），意思是两者的邻接矩阵等谱，特征值不仅数值相等，连重数也一样，即组成的多重集相等。
共谱图不必同构，但同构图必然共谱。
图由谱决定（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]
参见
参考文献
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
