主题
Search

图谱


邻接矩阵的图特征值的集合称为图的谱。(但请注意,在物理学中,图的拉普拉斯矩阵的特征值有时也被称为图的谱。)具有 n_i 重退化特征值 lambda_i 的图 G 的谱通常表示为 Spec(G)=(lambda_1)^(n_1)(lambda_2)^(n_2)... (van Dam 和 Haemers 2003) 或 (lambda_1 lambda_2 ...; n_1 n_2 ...) (Biggs 1993, p. 8; Buekenhout 和 Parker 1998)。

G 的谱元素上的乘积 product_(k)(x-s_k) 被称为 G特征多项式,它由 G邻接矩阵关于变量 x特征多项式给出。

图的谱的最大绝对值称为其谱半径

可以使用 Wolfram 语言计算图的谱,使用Eigenvalues[AdjacencyMatrix[g]]. 可以使用以下方法获取许多命名图的预计算谱GraphData[graph,"Spectrum"].

谱完全由整数组成的图称为积分图

如果 G正则图,则连通图 G最大顶点度G 的特征值 当且仅当

两个非同构图可以共享相同的谱。这样的图称为同谱图。对于已知由其谱唯一确定的图,似乎没有标准的名称。虽然它们可以被认为是谱唯一的,但在实践中使用了术语“由谱确定”(van Dam 和 Haemers 2003)。

由 Siemion Fajtlowicz 在 20 世纪 80 年代中期编写的名为 Graffiti 的软件包已被用于生成谱图理论中的一千个猜想(DeLaVina 2005,Roucairol 和 Cazenave 2024)。


另请参阅

代数连通性, 由谱确定, 特征多项式, 同谱图, 图特征值, 图能量, 积分图, 拉普拉斯矩阵, 谱半径

使用 Wolfram|Alpha 探索

参考文献

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Buekenhout, F. and Parker, M. "The Number of Nets of the Regular Convex Polytopes in Dimension <=4." Disc. Math. 186, 69-94, 1998.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.DeLaVina, E. "On Some History of the Development of Graffiti." It Graphs and Discovery DIMACS: Series in Discrete Mathematics and Theoretical Computer Science 69, 81-118.2005.Haemers, W. H. "Spectral Characterization of Graphs." In IPM Combinatorics II: Design Theory, Graph Theory, and Computational Methods. April 22-27, 2006, IPM, Tehran. http://www.ipm.ac.ir/combinatoricsII/abstracts/Haemers1.pdf.Roucairol, M. and Cazenave, T. "Refutation of Spectral Graph Theory Conjectures with Search Algorithms." 27 Sep 2024. https://arxiv.org/abs/2409.18626.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 85, 1990.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.Wilf, H. "Graphs and Their Spectra: Old and New Results." Congr. Numer. 50, 37-43, 1985.

在 Wolfram|Alpha 上被引用

图谱

引用为

韦斯坦, 埃里克·W. "图谱。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/GraphSpectrum.html

主题分类