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

　　

【正文】 knknknk?????????????????????00110100011110010111111211 =kknkknknknn????????????????????001101001100001002001121 =0101100010201121nkknknknn????????????????? =011102)(1121nkknkknnn????????????????? 所以 011102)()()()(112112211 21nkknkknnnnnHL knknkn??????????????? ?????????????? 令011102)(1121nkknkknng???????????????? 并進(jìn)行如下計(jì)算： 0)1)(1()1)(()1( 1112 ??????????? nkknknknkg 0)( 2 ??? nkkg 0)1)(()2( 121 ??????? knknng 0)1)(()( 121 ????? knknng 南通大學(xué)畢業(yè)論文 18 01)1( 1 ????? knng 0)1)(()( 2 ?????? knknng 根據(jù)根的存在性定理可知： 1?k 和 k 之間至少存在一個(gè)根， k 和 1n 之間至少存在一個(gè)根 綜上：重組圖 nH 的 Laplace 譜為： 1 個(gè) 0， )1( ?k 個(gè) n ， )2( 1 ??kn 個(gè) 1n ， )1( 2 ??kn 個(gè) 2n ，kk ??? 11 ? ， 121 2 nn ??? ? ， nn ??? 31 ? 。 p 個(gè)完全圖的重組圖的情形 由兩個(gè)完全圖的重組圖 Laplace 譜的變化情況，我們可以推廣得到 p 個(gè)完全圖的重組圖的情形。 定理 ，設(shè)重組圖 )。,(321 knnnn KKKKKG p??的 Laplace 譜為 n??? ?, 21 ,則譜為： 1 個(gè) 0，1 個(gè) k ， k 個(gè) n ， )1( 1 ??kn 個(gè) 1n ， )1( 2 ??kn 個(gè) 2n ， )1( 3 ??kn 個(gè) ?,3n )1( ??knp 個(gè) pn 。 定理 ，設(shè)重組圖 nH 為 )。,(321 knnnn KKKKKG p??去掉 Kk 內(nèi) 一條邊的所得到的圖， 則 其Laplace 譜 n??? ?, 21 為：其中包括 1 個(gè) 0， 1 個(gè) k ， 1 個(gè) 2?n ， )2( ?k 個(gè) n ， )1( 1 ??kn 個(gè) 1n ，)1( 2 ??kn 個(gè) 2n ， )1( 3 ??kn 個(gè) ?,3n )1( ??knp 個(gè) pn 。 定理 ，設(shè)重組圖 nH 為 )。,(321 knnnn KKKKKG p??去掉 kn KK ?1中一條邊所得到的圖，則其 Laplace 譜 n??? ?, 21 為： 1 個(gè) 0， 1 個(gè) k ， 1 個(gè) 21?n ， k 個(gè) n ， )1( 1 ??kn 個(gè) 1n ， )1( 2 ??kn個(gè) 2n ， )1( 3 ??kn 個(gè) ?,3n )1( ??knp 個(gè) pn 。 定理 ， 設(shè)重組圖 nH 為 )。,(321 knnnn KKKKKG p??去掉 kK 與 knK?1之間 一條邊所 得到的圖，其 Laplace 譜 為 n??? ?, 21 ， 則 重組圖 nH 的 Laplace 譜為： 1 個(gè) 0， )1( ?k 個(gè) n ， )2( 1 ??kn 個(gè) 1n ， )1( 2 ??kn 個(gè) 2n ， )1( 3 ??kn 個(gè) ?,3n )1( ??knp 個(gè) pn kk ??? 11 ? ， 121 2 nn ??? ? ， nn ??? 31 ? 。 南通大學(xué)畢業(yè)論文 19 第三章 歸 納 下表 是 各種情況下重組圖的拉普拉斯譜個(gè)數(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 這個(gè)特征值，及特征值 n 的重?cái)?shù)發(fā)生了改變。 和定理 ，去掉重組圖中 kn KK ?1內(nèi)一條邊， 重組圖的代數(shù)連通度未發(fā)生改變，譜半徑發(fā)生了變化，需要根據(jù) 1n 和 2n 的大小來確定。 和定理 ，去掉重組圖中 kK 與 kn KK ?1之間的一條邊， 重組圖的譜半徑不變，代數(shù)連通度發(fā)生改變，有三個(gè)特征值的大小較難確定，只能給出大概的范圍。特征值 個(gè)數(shù) 不同情況 南通大學(xué)畢業(yè)論文 20 參考文獻(xiàn) [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. 南通大學(xué)畢業(yè)論文 21 致 謝 本文是在導(dǎo)師呂大梅講師的悉心指導(dǎo)下完成的 ，從最初的定題到資料搜集，再到論文的寫作、修改和定稿，她都給了我細(xì)心的指導(dǎo)和耐心的幫助。她踏實(shí)的科學(xué)態(tài)度和嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神及精益求精的工作作風(fēng)時(shí)刻激勵(lì)著我前進(jìn)，讓我受益無窮。在此，我向她表示我最真摯的感謝與真誠的敬意。