学位论文 > 优秀研究生学位论文题录展示

线性超图的谱

作　者: 李小华
导　师: 杜智华；王迪吉
学　校: 新疆师范大学
专　业: 基础数学
关键词: 线性超图邻接矩阵强色数谱半径
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 37次
引　用: 0次
阅　读: 论文下载

内容摘要

超图是普通图的推广,在图G中,用A(G)表示图G的邻接矩阵,则矩阵A(G)的特征值称为图G的特征值,图G的所有特征值组成的集合称为图G的谱,其中特征值模的最大值称为该图的谱半径. 1996年,冯克勤定义了超图的邻接矩阵,即超图的邻接矩阵A(H)是一个n×n阶矩阵,其中矩阵A(H)的元素aij的值为在超图的关联二部图中,从顶点vi到vj 2长路的数目,即若顶点vi和vj同时属于k条边中,则aij = k.类似地,矩阵A(H)的特征值称为超图H的特征值,超图H的所有特征值组成的集合称为超图H的谱,其中特征值模的最大值称为该超图的谱半径.在此基础上,本文推广图论中的一些经典结果,得到了r一致线性超图的几个重要性质,并且探讨了r一致线性超图H的谱半径,并且给出了r一致线性超图的谱半径的界的估计.本文总共分为五部分:第一部分介绍了本文的国内外研究背景.第二部分介绍了与本文有关的基本概念.第三部分推广了图论中的一些经典结果,首先推广了图论中的Perron ? Frobenius定理和内插定理,其次根据超图邻接矩阵的定义,得到了另外几个结果:定理3.1:假设H是连通的r一致线性超图,那么有(1)它的最大特征值λ1(>0)是一个单根.(2)如果x是特征值λ1对应的特征向量,那么x是正特征向量.(3)若λ是H的任意一个其他特征值,则?λ1<λ<λ1.(4)如果H的任意一条边被删去,那么它的最大特征值都将减小.定理3.2:设H = (E1,E2,···,Em)是r一致线性超图, H的谱为:定理3.3:设A = (aij)n×n是r一致线性超图H的邻接矩阵,那么在H中从顶点vi到vj长度为l的链的数目等于矩阵Al中(i,j)位置元素的值.定理3.4:设A = (aij)n×n是r一致线性超图H的邻接矩阵,λ1,λ2,···,λn是A的特征值, c是H中从顶点vi到vi长度为k的闭链的数目,那么c=trAk = n定理3.5:设H = (E1,E2,···,Em)是n阶r一致线性超图,H的直径d(H) = d,那么其邻接矩阵的s个不同的特征值满足n≥s≥d + 1.第四部分分为两节,第一节通过线性超图的秩r,边数m,顶点数n,各个顶点的度数,顶点的最大度?,最小度δ,色数γ(H)等刻画了线性超图的谱半径,主要结果有:定理4.1:设H = (E1,E2,···,Em)是连通r一致线性超图,且d1,d2,···,dn为超图中各顶点的度数.那么定理4.2:设H = (E1,E2,···,Em)是r一致线性超图,且ρ(H)是H的谱半径.那么(r- 1)≤ρ(H)≤(r ? 1).定理4.3:设H = (E1,E2,···,Em)是r-一致线性超图,λ1是H的最大特征值.那么有mr(nr? 1)≤λ1≤mr(r-n1)(n-1)定理4.4:设ρ(H) =λ1 >λ2≥···≥λn为r一致线性超图H的谱,且令k =γ(H).那么ρ(H)≤?(λn +λn-1 +···+λn-k+2).定理4.5:设H = (E1,E2,···,Em)为r一致线性超图,且ρ(H) =λ1≥λ2≥···≥λn为H的特征值.那么ρ(H)≤mr(r?γ1)((Hγ)(H)-1)定理4.6:设H = (E1,E2,···,Em)为n阶r一致线性超图, l是满足ρ(H)≤-(λn +λn-1 +···+λn-l+1)的最小整数.那么ρ(H)≤mrl(+r-1 1)l.定理4.7:设H = (E1,E2,···,Em)为连通的n阶r一致线性超图,其邻接矩阵为A,d1,d2,···,dn为其各顶点的度数.那么ρ(H)≤δ(r-1)-1+√[δ(r-1)2-1]2+4(r-1)(rm-n)第二节刻画了线性超图的第二大特征值的界,主要结果有:定理4.8:设H = (E1,E2,···,Em)是n阶r一致线性超图, H的邻接矩阵为A =(aij)n×n , X是特征值α<ρ(H)对应的特征向量.用n+,n?和n0分别表示X中正分量,负分量和0分量的个数,那么推论2:设H = (E1,E2,···,Em)为n阶r一致线性超图.那么λ2(H)≤n2 ? 1.第五部分这部份介绍了两种计算超图的特征多项式的简化公式以及求出了r一致星超图的谱,其主要结果有:定理5.1:设H = (E1,E2,···,Em)为超图,且E1 = {v1,v2,v3}. d(v1) = d(v2) = 1,H1 = H -{v1},H2 = H -{v1,v2},H3 = H -{v1,v2,v3}.那么PH(λ) = (λ2 - 1)PH2 ?2(λ+ 1)PH3(λ).定理5.2:设H1和H2为两个线性超图,用一条秩为r的边E连接超图H1中的顶点v1和H2中的顶点v2所得的超图记为H.从Hi中删除顶点vi (i = 1,2)所得的超图记为Hi,即Hi=Hi ? {vi}.那么PH(λ) = (λ+ 1)r?3P(λ).其中P(λ) = [λ- (r -3)][PH1(λ)PH2(λ) - PH1(λ)PH2(λ)]- (r - 2)[PH1(λ)PH2(λ) +2PH1(λ)PH2(λ) + PH1(λ)PH2(λ)].定理5.3:设H = (E1,E2,···,Em)为n阶连通的r一致星超图, |Ei Ej| = {v1}(i =j),那么

全文目录

中文摘要  3-5
Abstract  5-9
1 前言  9-11
2 预备知识  11-13
3 线性超图的几个性质  13-16
4 r一致线性超图谱半径界的估计  16-25
  4.1 线性超图谱半径的估计  16-23
  4.2 线性超图第二大特征值的估计  23-25
5 特征多项式计算的简化公式  25-30
参考文献  30-33
在读期间发表的论文  33-34
后记  34

相似论文

关于特征多项式的两个参数及其应用,O157.5
非线性奇异问题的正解和非平凡解,O175.8
几类非线性问题的正解与应用,O175.8
解鞍点问题的迭代法,O241.6
图的割点数与谱半径,O157.5
非负张量特征值研究中的若干问题,O183.2
给定点数和边数连通二部图的拉普拉斯谱半径,O157.5
三圈图中拉普拉斯谱的一些图性质,O157.5
超图的边着色,O157.5
基于Wielandt方法的Perron-Frobenius理论及其推广,O151.21
变电所电气主接线可靠性评估,TM732
超图各参数间的关系以及超图的边色数问题,O157.5
具有固定匹配数的双圈图的谱半径,O157.5
变电站微机五防闭锁规则库自动生成器的设计,TM63
解一类微分方程的预条件方法的收敛性,O241.6
由图的谱（和角）确定的问题,O157.5
基于混合人工免疫优化算法的机构运动链同构识别研究,TH112
超图的顶点着色,O157.5
非线性微分方程边值问题的解,O175.8
基于二分图邻接矩阵的压缩传感图像重建算法研究,TP391.41