冠圖的譜及其應(yīng)用研究.pdf

1、譜圖理論是圖論的一個(gè)非常活躍而又重要的分支，它在計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)、信息科學(xué)和量子化學(xué)等領(lǐng)域都有著廣泛的應(yīng)用。譜圖理論研究的主要對(duì)象包括圖的鄰接譜，Laplacian譜以及圖的signless Laplacian譜，并且圖的各種譜之間相互聯(lián)系。譜圖理論研究的一個(gè)主要問題就是由矩陣的代數(shù)性質(zhì)反映圖的性質(zhì)，而矩陣的代數(shù)性質(zhì)主要為矩陣的特征根性質(zhì)。圖的鄰接矩陣表示圖中各頂點(diǎn)之間的連接關(guān)系，記為A(G)；圖的Laplacian矩陣記為L(zhǎng)(G)

2、?D(G)?A(G)，其中D(G)表示圖G的度對(duì)角矩陣；圖的signless Laplacian矩陣記為Q(G)?D(G)?A(G)。圖G的矩陣的特征根及其對(duì)應(yīng)的重?cái)?shù)構(gòu)成圖的譜。圖的鄰接矩陣的特征根及其對(duì)應(yīng)的重?cái)?shù)構(gòu)成圖的鄰接譜，記為A-譜；圖的 Laplacian矩陣的特征根及其對(duì)應(yīng)的重?cái)?shù)構(gòu)成圖的 Laplacian譜，記為L(zhǎng)-譜；圖的 signless Laplacian矩陣的特征根及其對(duì)應(yīng)的重?cái)?shù)構(gòu)成圖的signless Laplac

3、ian譜，記為Q-譜。
　　圖的矩陣與圖的結(jié)構(gòu)有著緊密的聯(lián)系。由矩陣的定義可知，圖的 Laplacian矩陣和signless Laplacian矩陣都表示為鄰接矩陣與度矩陣的關(guān)系。由此可以通過一個(gè)參數(shù)t將三個(gè)矩陣聯(lián)系在一起，表示成廣義矩陣A(G)-tD(G)。當(dāng)t=0時(shí)，得到的是圖G鄰接矩陣A(G)；當(dāng)t=1時(shí)，得到的是-L(G)；當(dāng)t=-1時(shí)，得到的是圖G的 signless Laplacian矩陣 Q(G)。圖 G的廣義特征

4、多項(xiàng)式記為此處為公式，其中I是與鄰接矩陣 A(G)同維數(shù)的單位矩陣。根據(jù)參數(shù)t的不同取值，圖G的鄰接特征多項(xiàng)式、Laplacian特征多項(xiàng)式及signless Laplacian特征多項(xiàng)式分別可以表示為此處為公式。廣義特征多項(xiàng)式將鄰接特征多項(xiàng)式、Laplacian特征多項(xiàng)式和signless Laplacian特征多項(xiàng)式合成在一起，大大減少了圖譜計(jì)算的工作量。
　　圖的譜蘊(yùn)含著圖的許多信息。冠圖是一種由圖操作得到的復(fù)雜圖，冠圖的譜

5、更加難以計(jì)算。文中定義了四類冠圖分別是：剖分圖的冠點(diǎn)圖 G1◇G2、剖分圖的冠邊圖 G1☆G2、點(diǎn)剖分冠圖G1⊙G2、邊剖分冠圖G1(-)2G。應(yīng)用分塊矩陣、矩陣的coronal、克羅內(nèi)克積等計(jì)算并證明了這幾類冠圖的譜可以表示為原圖G1和G2的譜；得到了許多A-同譜圖，L-同譜圖及Q-同譜圖；作為應(yīng)用，由冠圖的Laplacian譜得到了生成樹數(shù)目以及Kirchhoff指數(shù)；并構(gòu)造出了新冠圖的一些A-整譜圖。
　　本文的主要成果有：

6、
　?。?）計(jì)算并證明了剖分圖的冠點(diǎn)圖G1◇G2、剖分圖的冠邊圖G1☆G2的鄰接譜，Laplacian譜以及signless Laplacian譜；
　?。?）得到剖分圖的冠點(diǎn)圖G1◇G2、剖分圖的冠邊圖G1☆G2的生成樹數(shù)目及Kirchhoff指數(shù)；
　?。?）計(jì)算并證明了剖分圖的冠點(diǎn)圖G1◇G2、剖分圖的冠邊圖G1☆G2的A-整譜圖。
　?。?）計(jì)算并證明了點(diǎn)剖分冠圖G1⊙G2、邊剖分冠圖G1(-)2G的廣義

7、特征多項(xiàng)式；
　　（5）得到點(diǎn)剖分冠圖G1⊙G2、邊剖分冠圖G1(-)2G的廣義同譜圖；
　?。?）計(jì)算并證明了點(diǎn)剖分冠圖G1⊙G2、邊剖分冠圖G1(-)2G的鄰接特征多項(xiàng)式、Laplacian特征多項(xiàng)式及signless特征多項(xiàng)式；
　　（7）計(jì)算并證明了點(diǎn)剖分冠圖G1⊙G2、邊剖分冠圖G1(-)2G的A-整譜圖；
　?。?）得到點(diǎn)剖分冠圖G1⊙G2、邊剖分冠圖G1(-)2G的生成樹數(shù)目及Kirchhoff指數(shù)