【導讀】是一個頂點集為},,,{21nvvvV??GE的n階簡單圖。示G中iv與jv之間的邊數(shù)，稱??GA的特征值就稱為。G的鄰接譜，度矩陣??GD為G的頂點度數(shù)構成的對角矩陣。Laplace矩陣的研究是代數(shù)圖論的重要組成部分。p個完全圖的重組圖的情形。去掉兩個完全圖的重組圖中kK與knKK?從歷史觀點上來說，圖的譜和結(jié)構。之間的第一個關系是在1876年基爾霍夫證明了他著名的矩陣-樹定理時發(fā)現(xiàn)的[2]。的主要原理是把圖的重要不變量和圖譜聯(lián)系起來。通常，像色數(shù)和獨立數(shù)這樣難以計算的不。變量，用含特征值的表達式比較它們是很有效的。系以及這些關系在圖劃分、排名、網(wǎng)絡病毒傳播和聚集等領域的一些實際應用。征值的其他應用，可參見[1，3，4，5]。著[6，7]，Mohar的綜述[8]，Godsil和Royle. 都包含一個子圖與圖0G同構，把pGGG,,,21?，G的鄰接矩陣為nnijaGA??

　　

【正文】 knknknk?????????????????????00110100011110010111111211 =kknkknknknn????????????????????001101001100001002001121 =0101100010201121nkknknknn????????????????? =011102)(1121nkknkknnn????????????????? 所以 011102)()()()(112112211 21nkknkknnnnnHL knknkn??????????????? ?????????????? 令011102)(1121nkknkknng???????????????? 并進行如下計算： 0)1)(1()1)(()1( 1112 ??????????? nkknknknkg 0)( 2 ??? nkkg 0)1)(()2( 121 ??????? knknng 0)1)(()( 121 ????? knknng 南通大學畢業(yè)論文 18 01)1( 1 ????? knng 0)1)(()( 2 ?????? knknng 根據(jù)根的存在性定理可知： 1?k 和 k 之間至少存在一個根， k 和 1n 之間至少存在一個根 綜上：重組圖 nH 的 Laplace 譜為： 1 個 0， )1( ?k 個 n ， )2( 1 ??kn 個 1n ， )1( 2 ??kn 個 2n ，kk ??? 11 ? ， 121 2 nn ??? ? ， nn ??? 31 ? 。 p 個完全圖的重組圖的情形 由兩個完全圖的重組圖 Laplace 譜的變化情況，我們可以推廣得到 p 個完全圖的重組圖的情形。 定理 ，設重組圖 )。,(321 knnnn KKKKKG p??的 Laplace 譜為 n??? ?, 21 ,則譜為： 1 個 0，1 個 k ， k 個 n ， )1( 1 ??kn 個 1n ， )1( 2 ??kn 個 2n ， )1( 3 ??kn 個 ?,3n )1( ??knp 個 pn 。 定理 ，設重組圖 nH 為 )。,(321 knnnn KKKKKG p??去掉 Kk 內(nèi) 一條邊的所得到的圖， 則 其Laplace 譜 n??? ?, 21 為：其中包括 1 個 0， 1 個 k ， 1 個 2?n ， )2( ?k 個 n ， )1( 1 ??kn 個 1n ，)1( 2 ??kn 個 2n ， )1( 3 ??kn 個 ?,3n )1( ??knp 個 pn 。 定理 ，設重組圖 nH 為 )。,(321 knnnn KKKKKG p??去掉 kn KK ?1中一條邊所得到的圖，則其 Laplace 譜 n??? ?, 21 為： 1 個 0， 1 個 k ， 1 個 21?n ， k 個 n ， )1( 1 ??kn 個 1n ， )1( 2 ??kn個 2n ， )1( 3 ??kn 個 ?,3n )1( ??knp 個 pn 。 定理 ， 設重組圖 nH 為 )。,(321 knnnn KKKKKG p??去掉 kK 與 knK?1之間 一條邊所 得到的圖，其 Laplace 譜 為 n??? ?, 21 ， 則 重組圖 nH 的 Laplace 譜為： 1 個 0， )1( ?k 個 n ， )2( 1 ??kn 個 1n ， )1( 2 ??kn 個 2n ， )1( 3 ??kn 個 ?,3n )1( ??knp 個 pn kk ??? 11 ? ， 121 2 nn ??? ? ， nn ??? 31 ? 。 南通大學畢業(yè)論文 19 第三章 歸 納 下表 是 各種情況下重組圖的拉普拉斯譜個數(shù)分布的情況： 0 k 1n 2n n 2?n 21?n ),1( kk? ),2( 11 nn ? ).1( nn? 不去邊 1 1 11 ??kn 12 ??kn k 0 0 無 無 無 kK 內(nèi) 去邊 1 1 11 ??kn 12 ??kn 2?k 1 0 無 無 無 kn KK ?1內(nèi)去邊 1 1 11 ??kn 12 ??kn k 0 1 無 無 無 kn KK ?1與 kK 間去邊 1 無 21 ??kn 12 ??kn 1?k 無 無 1 1 1 通過上表 ，我們可以發(fā)現(xiàn)： 和定理 ，去掉重組圖中 kK 內(nèi)一條邊， 重組圖的譜半徑和代數(shù)連通度均未發(fā)生改變，只是定理 比定理 增加了 2?n 這個特征值，及特征值 n 的重數(shù)發(fā)生了改變。 和定理 ，去掉重組圖中 kn KK ?1內(nèi)一條邊， 重組圖的代數(shù)連通度未發(fā)生改變，譜半徑發(fā)生了變化，需要根據(jù) 1n 和 2n 的大小來確定。 和定理 ，去掉重組圖中 kK 與 kn KK ?1之間的一條邊， 重組圖的譜半徑不變，代數(shù)連通度發(fā)生改變，有三個特征值的大小較難確定，只能給出大概的范圍。特征值 個數(shù) 不同情況 南通大學畢業(yè)論文 20 參考文獻 [1] M. Dehmer . Structural Analysis of Complex Networks[M]. Springer Science+Business Media. [2] Kirchhoff G. U168。 ber die Auflo168。sung der Gleichungen auf welche man bei der Untersuchung der Linearen Vertheilung galvanischer Str168。ome gef168。uhrt wird[J]. Ann Phys Chem, 1847,72:497–508. [3] Krivelevich M, Sudakov B. Pseudorandom graphs[J]. More sets, graphs and numbers. Bolyai Society Mathematical Studies, 20xx,vol 15: 199–262. [4] van Dam E, Haemers W. Which graphs are determined by their spectrum?[J]. Lin Algebra Appl, 20xx,373:241–272. [5] van Dam E, Haemers W. Developments on spectral characterization of graphs[J]. Discrete Math, 20xx,309:576–586. [6] Cvetkovi180。c D, Doob M, Sachs H. Spectra of graphs – theory and application[J]. Academic, New York, 3rd edn, 1995. [7] Cvetkovi180。c D, Rowlinson P, Simic S. Eigenspaces of graphs[M]. Cambridge University Press: Cambridge,1997. [8] Mohar B. Some applications of Laplace eigenvalues of graphs[M]. Hahn G, Sabidussi G (eds) Graph symmetry: Kluwer, Dordrecht,1997,225–275. [9] Godsil CD, Royle G. Algebraic graph theory[M]. Berlin:Springer,20xx. [10] Chung FRK. Spectral graph theory[M]. American Mathematical Society, Providence, RI,1997. [11] ,Sinogowitz U. Spektren endlicher Grafen[J]. Abh Math Sem Univ Hamburg, : 63–77. 南通大學畢業(yè)論文 21 致 謝 本文是在導師呂大梅講師的悉心指導下完成的 ，從最初的定題到資料搜集，再到論文的寫作、修改和定稿，她都給了我細心的指導和耐心的幫助。她踏實的科學態(tài)度和嚴謹?shù)闹螌W精神及精益求精的工作作風時刻激勵著我前進，讓我受益無窮。在此，我向她表示我最真摯的感謝與真誠的敬意。