本文選題：圖譜理論 + 廣義冠圖��； 參考：《蘭州理工大學(xué)》2017年碩士論文

【摘要】：圖譜理論在計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)、量子化學(xué)等眾多學(xué)科中都有應(yīng)用,由圖的特征多項(xiàng)式可以直接得到圖的譜,因此研究得到圖的特征多項(xiàng)式對(duì)于研究這些學(xué)科都很有益。圖的鄰接矩陣A(G)表示了圖中頂點(diǎn)與頂點(diǎn)之間的鄰接關(guān)系,鄰接矩陣的特征多項(xiàng)式稱為鄰接特征多項(xiàng)式。圖的度對(duì)角矩陣是對(duì)角線上為每個(gè)頂點(diǎn)的度的對(duì)角矩陣,記為D(G)。Laplacian矩陣記為L(zhǎng)(G)=D(G)-A(G),Laplacian矩陣的特征多項(xiàng)式稱為L(zhǎng)aplacian 特征多項(xiàng)式;signless Laplacian 矩陣記為Q(G)=D(G)+A(G), signless Laplacian矩陣的特征多項(xiàng)式稱為signlessLaplacian特征多項(xiàng)式。圖的各項(xiàng)特征多項(xiàng)式的特征根及其重?cái)?shù)稱為圖的譜,分別為鄰接譜、Laplacian譜和signless Laplacian譜。同譜而又非同構(gòu)的圖稱為同譜圖,分別為鄰接同譜圖(記為A-同譜圖)、Laplacian同譜圖(記為L(zhǎng) -同譜圖)和signless Laplacian同譜圖(記為Q-同譜圖)。冠圖是通過(guò)多個(gè)圖進(jìn)行圖操作所得到的復(fù)雜圖,剖分圖是在每條邊上新添加一個(gè)頂點(diǎn)所得到的圖。本文將冠圖廣義化并融合了剖分圖操作,構(gòu)造了兩種新的廣義冠圖:廣義剖分冠邊圖S(G)(?)H,和廣義剖分冠點(diǎn)圖S(G)(?)Hi。應(yīng)用分塊矩陣、舒爾補(bǔ)、矩陣的冠值等計(jì)算并證明了這兩類廣義冠圖的鄰接特征多項(xiàng)式、Laplacian特征多項(xiàng)式和signless Laplacian特征多項(xiàng)式。作為應(yīng)用還得到了在特殊情況下這兩種廣義冠圖的生成樹數(shù)目和Kirchhoff指數(shù),并給出了計(jì)算生成樹數(shù)目的例子。隨后還得到了一系列的鄰接同譜圖、Laplacian同譜圖和signless Laplacian同譜圖圖簇,并給出了例子。本文的主要成果有:(1)定義了一類新的廣義冠圖--廣義剖分冠邊圖S(G)(?)Hi。計(jì)算并證明了它的各項(xiàng)特征多項(xiàng)式。(2)計(jì)算并證明了在圖G為r-正則圖,圖H1,...Hm均為圖H時(shí)構(gòu)造的非廣義的剖分冠邊圖S(G)(?)H的L-譜、生成樹個(gè)數(shù)和Kirchhoff指數(shù)。并給出了計(jì)算生成樹數(shù)目的例子。(3)得到了一系列鄰接同譜、Laplacian同譜和signless Laplacian同譜的廣義剖分冠邊圖圖簇,并給出了同譜圖的例子。(4)定義了一類新的廣義冠圖--廣義剖分冠點(diǎn)圖S(G)(?)Hi。計(jì)算并證明了它的各項(xiàng)i特征多項(xiàng)式。(5)計(jì)算并證明了在圖G為r-正則圖,圖H1,...Hn均為圖H時(shí)構(gòu)造的非廣義的剖分冠點(diǎn)圖S(G)(?)的L-譜、生成樹個(gè)數(shù)和Kirchhoff指數(shù)。并給出了計(jì)算生成樹數(shù)目的例子。(6)得到了一系列鄰接同譜、Laplacian同譜和signless Laplacian 同譜的廣義剖分冠點(diǎn)圖圖簇,并給出了同譜圖的例子。
[Abstract]:The graph theory has been applied in many subjects such as computer science, communication network, quantum chemistry and so on. The spectrum of graphs can be obtained directly from the characteristic polynomials of graphs, so it is very useful to study the characteristic polynomials of graphs. The adjacency matrix A (G) of a graph represents the adjacency between vertices and vertices in a graph. The characteristic polynomial of the adjacency matrix is called the adjacent characteristic polynomial. The degree diagonal matrix of a graph is a diagonal matrix with a degree of each vertex on the diagonal line. The characteristic polynomial denoted by D (G). Laplacian matrix is called the signless Laplacian matrix, which is called the signless Laplacian matrix. The characteristic polynomial of the G) A (G), signless Laplacian matrix is called the signlessLaplacian characteristic polynomial. The eigenvalues and their multiplicity of characteristic polynomials of graphs are called the spectrum of graphs, which are adjacent spectrum and signless spectrum, respectively. Graphs with the same spectrum but not isomorphism are called isospectral graphs, which are adjacent isospectral graphs (referred to as A- isospectral graphs) and signless Laplacian isospectral graphs (referred to as Q-isospectral graphs), respectively. A crown graph is a complex graph which is obtained by the operation of multiple graphs, and a subdivision graph is a graph obtained by adding a new vertex to each edge. In this paper, two new generalized crown graphs are constructed: s (G) (?) H, S (G) (?) H and S (G) (?) Hi. By using block matrix, Schulm complement and the crown value of matrix, it is proved that the adjacent characteristic polynomials of these two classes of generalized crown graphs are Laplacian characteristic polynomials and signless Laplacian characteristic polynomials. As applications, the number of spanning trees and Kirchhoff exponents of these two generalized crown graphs are obtained, and an example is given to calculate the number of spanning trees. A series of adjacent Laplacian isospectral graphs and signless Laplacian isospectral graphs are obtained, and an example is given. The main results of this paper are as follows: (1) A new generalized crown graph S (G) (?) Hi. Its characteristic polynomials are calculated and proved. (2) the L- spectrum, the number of spanning trees and the Kirchhoff exponent of the non-generalized dissecting crown edge graph S (G) (?) H are calculated and proved when the graph G is r-regular and the graph H _ 1 路H _ m is a graph H. An example is given to calculate the number of spanning trees. (3) A series of generalized dissected crown edge graphs with adjacent isospectral and signless isospectral graphs are obtained. (4) A new class of generalized crown graphs S (G) (?) is defined. The various I characteristic polynomials of the graph are calculated and proved. (5) the graph S (G) (?) constructed when the graph G is r-regular and the graph H _ 1 路H _ n is all graph H. The number of spanning trees and Kirchhoff exponent. An example of calculating the number of spanning trees is given. (6) A series of generalized subdivision crown graph families adjacent to the isospectral Laplacian and signless Laplacian isospectrum are obtained, and an example of the isospectral graph is given.
【學(xué)位授予單位】：蘭州理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5;TP391.41

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 吳彥博;;譜聚類廣義模型和典型算法探析[J];通訊世界;2016年23期

2 沈玲;王年;;基于圖的譜系數(shù)夾角的特征點(diǎn)匹配[J];計(jì)算機(jī)技術(shù)與發(fā)展;2015年12期

3 尹宏偉;李凡長(zhǎng);;譜機(jī)器學(xué)習(xí)研究綜述[J];計(jì)算機(jī)科學(xué)與探索;2015年12期

4 譚躍生;楊寶光;王靜宇;張亞楠;;Hadoop云平臺(tái)下的聚類算法研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2014年05期

5 張聰;沈惠璋;;基于譜方法的復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的模塊度[J];系統(tǒng)工程理論與實(shí)踐;2013年05期

6 李海林;郭崇慧;;時(shí)間序列數(shù)據(jù)挖掘中特征表示與相似性度量研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2013年05期

7 翟永磊;田道坤;;基于圖譜理論的圖像分割[J];科技視界;2013年07期

8 謝明霞;陳科;郭建忠;;基于圖譜理論的FCM圖像分割方法研究[J];計(jì)算機(jī)應(yīng)用;2008年11期

9 趙永毅;史定華;;復(fù)雜網(wǎng)絡(luò)的特征譜及其應(yīng)用[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2006年01期

10 劉艷秋,張穎,汪定偉,Ip.W.H.;復(fù)雜裝置網(wǎng)絡(luò)可靠性評(píng)估模型與算法[J];東北大學(xué)學(xué)報(bào);2004年06期

相關(guān)博士學(xué)位論文 前4條

1 程希明;只有三個(gè)不同特征值的圖[D];中國(guó)科學(xué)技術(shù)大學(xué);2016年

2 丁嘯;基于序列特征的宏基因組數(shù)據(jù)分析方法研究[D];東南大學(xué);2016年

3 李海林;時(shí)間序列數(shù)據(jù)挖掘中的特征表示與相似性度量方法研究[D];大連理工大學(xué);2012年

4 支瑞聰;基于譜圖理論的人臉表情識(shí)別算法研究[D];北京交通大學(xué);2010年

相關(guān)碩士學(xué)位論文 前3條

1 張勇;圖像中模糊邊界目標(biāo)的閾值分割方法研究[D];合肥工業(yè)大學(xué);2011年

2 劉奎鳳;基于圖論的圖像譜分割技術(shù)[D];哈爾濱工程大學(xué);2010年

3 董瑞;基于圖譜理論的圖像匹配和圖像分割算法研究[D];安徽大學(xué);2007年

，

本文編號(hào)：2087334