【正文】 圖的情形。在 [1 ]中， 也 給出一些圖譜和它的結(jié)構(gòu)的關(guān)系以及這些關(guān)系在圖劃分、排名、網(wǎng)絡(luò)病毒傳播和聚集等領(lǐng)域的一些實(shí)際應(yīng)用。 i 和 j 是 G 的兩個(gè)頂點(diǎn)且 ji? ， 從 L 中刪除行 i 和列 j 得到矩陣 )(ijL 。 定理 ，設(shè)重組圖 nG =（1nK，2nK； Kk）的 Laplace 譜為 n??? ?, 21 ,則 ,0 114324321 1 nnk nkkk ?????????? ???? ???????? ?? 232 11 nnnn ???? ?? ??? ?。 定理 ， 設(shè)重組圖 nH 為 )。她踏實(shí)的科學(xué)態(tài)度和嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神及精益求精的工作作風(fēng)時(shí)刻激勵(lì)著我前進(jìn)，讓我受益無(wú)窮。 定理 ，設(shè)重組圖 nH 為 )。 本文主要結(jié)果 本文著重研究了兩個(gè)完全圖的重組圖的 Laplace 譜，然后研究了兩個(gè)完全圖的重組圖刪去一條邊所得的圖的 Laplace 譜 ，通過(guò)譜之間的比較得出相應(yīng)的結(jié)論，同時(shí)推廣研究了 p 個(gè)完全圖的重組圖的情形。 Laplace 矩陣 )(GL 的所有特征值稱(chēng)為圖 G 的 拉普拉斯（ Laplace）譜。 圖的特征值的研究是組合數(shù)學(xué)的一個(gè)重要組成部分 。 從歷史觀點(diǎn)上來(lái)說(shuō) ， 圖的譜和結(jié)構(gòu)之間的第一個(gè)關(guān)系是在 1876 年基爾霍夫證明了他著名的矩陣 樹(shù)定理時(shí)發(fā)現(xiàn)的 [2]。 下給出幾個(gè)簡(jiǎn)單圖的拉普拉斯譜 [11]。 南通大學(xué)畢業(yè)論文 7 第二章 重組圖的 Laplace 譜 兩個(gè)完全圖的重組圖的 Laplace 譜 設(shè) ? ?kvvU ,....,1? 為 Kk 的頂點(diǎn)集。,(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 。在此，我向她表示我最真摯的感謝與真誠(chéng)的敬意。,(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è) nG 表示完全圖1nK和2nK在 Kk 基礎(chǔ)上的重組圖，即 nG =（1nK，2nK； Kk），其中： knnn ??? 21 。 拉普拉斯算子矩陣 )(GL 的特征值按遞增順序列出： )()()( 21 GGG n??? ??? ?。通常，像色數(shù)和獨(dú)立數(shù)這樣難以計(jì)算的不變量，用含特征值的表達(dá)式比較它們是很有效的。 關(guān)鍵詞： Laplace 譜，重組圖，完全圖 南通大學(xué)畢業(yè)論文 II ABSTRACT Let ),( EVG? be a simple graph with the vertex set },{ 21 nvvvV ?? and the edge set )(GE . We use ija to express the number of edges between vertex iv and jv of G , and call nnijaGA ?? )()( as the adjacency matrix of G , view the eigenvalues of )(GA as the adjacency spectrum of G . The degree matrix )(GD is the diagonal matrix whose ith diagonal entry is the degree of vertex i in G . The Laplace matrix of G is given by )()()( GAGDGL ?? . The research on the characteristics value of Laplace matrix )(GL , is an important part of algebraic graph theory. In this paper, we study the Laplace spectrum of the rebinant graph of two plete graphs, and the Laplace spectrum of the rebinant graph of two plete graphs, furthermore, we obtain some results by parison. Furthermore, we study the Laplace spectrum of the rebinant graph of p plete graphs. Key words: Laplace spectrum, rebinant graph, plete graph 南通大學(xué)畢業(yè)論文 III 目錄 摘 要 ............................................... I ABSTRACT .............................................. II 目錄 .................................................. III 第一章 緒 論 ........................................... 4 引 言 ........................................... 4 基本概念及已有結(jié)果 ................................. 4 本文主要結(jié)果 ...................................... 6 第二章 重組圖的 Laplace 譜 ................................ 7 兩個(gè)完全圖的重組圖的 Laplace 譜 ....................... 7 去掉兩個(gè)完全圖的重組圖中 Kk內(nèi)一條邊的情況 .............. 9 去掉兩個(gè)完全圖的重組圖中 kn KK ?1內(nèi)一條邊的情況 ......... 12 去掉兩個(gè)完全圖的重組圖中 kK 與 kn KK ?1之間的一條邊的情況 .. 14 p 個(gè)完全圖的重組圖的情形 ........................... 18 第三章 歸 納 .......................................... 19 參考文獻(xiàn) .................................. 錯(cuò)誤 !未定義書(shū)簽。 定義 ： 矩陣 A 的特征值是 使得 XAX ?? 存在一個(gè)非零向量解 為 ? 。 R． Merris 給 出圖與其補(bǔ)圖 Laplace 譜之間的關(guān)系如下： 定理 [1] 若 G 的 Laplace 譜為 0)()()()( 121 ????? ? GGGG nn ???? ?，則 nGG cini ?? ? )()( ?? ， 1,2,1 ?? ni ? 。 定理 ，設(shè)重組圖 )。c D, Doob M, Sachs H. Spectra of graphs – theory and application[J]. Academic, New York, 3rd edn, 1995. [7] Cvetkovi180。 南通大學(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 無(wú) 無(wú) 無(wú) kK 內(nèi) 去邊 1 1 11 ??kn 12 ??kn 2?k 1 0 無(wú) 無(wú) 無(wú) kn KK ?1內(nèi)去邊 1 1 11 ??kn 12 ??kn k 0 1 無(wú) 無(wú) 無(wú) kn KK ?1與 kK 間去邊 1 無(wú) 21 ??kn 12 ??kn 1?k 無(wú) 無(wú) 1 1 1 通過(guò)上表 ，我們可以發(fā)現(xiàn)： 和定理 ，去掉重組圖中 kK 內(nèi)一條邊， 重組圖的譜半徑和代數(shù)連通度均未發(fā)生改變，只是定理 比定理 增加了 2?n 這個(gè)特征值，及特征值 n 的重?cái)?shù)發(fā)生了改變。 度矩陣 )( nGD =????????????knknkDDD2100 0000 ,其中： iiinnnnnnnD?????????