主題
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)。


另請參閱

代數連通性, 由譜確定, 特徵多項式, 同譜圖, 圖特徵值, 圖能量, 積分圖, 拉普拉斯矩陣, 譜半徑

使用 探索

參考文獻

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.

在 上被引用

圖譜

引用為

韋斯坦, 埃裡克·W. "圖譜。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/GraphSpectrum.html

主題分類