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

一类赋权图的代数连通度

作　者: 陈正博
导　师: 杜智华；王迪吉
学　校: 新疆师范大学
专　业: 基础数学
关键词: 赋权图 代数连通度 Laplacian矩阵 移接变形 Fielder向量
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 33次
引　用: 0次
阅　读: 论文下载
 

内容摘要


赋权图的研究已经被用来解决许多实际问题,网络设计以及电路设计实际上都依赖于赋权图.设G为一个简单图,顶点集为V = {v1,v2...vn},边集为E ={e1,e2...em}.设集合W = {w1,w2...wm},其中wi依次递减且wi > 0,i = 1,2...m.定义一个函数f :E→W,则f叫做赋权函数.Gf = （V,E,W,f）被称为赋权图. Gf（W）的Laplacian矩阵为Lf.Lf的特征值称为赋权图的Laplacian特征值.1973年,Fielder提出图G是连通的当且仅当图G的第2个最小的Laplacian特征值un-1 > 0.因此un-1被称为图G的代数连通度,记为a（G）.类似的赋权图Gf的第2个最小的Laplacian特征值被称为赋权图Gf的代数连通度.本文在此基础上,通过移接变形讨论了赋权图代数连通度的变化情况.本文主要研究了三个方面的内容: k正则图如何赋权;对于k正则图的每个顶点均增加一个含有l个点的集合Ni,1≤l≤n,i = 1,2...n,对于Ni中的每个点都与vi连一条边.在赋权函数f作用下,对新图进行赋权,记为Hf,讨论了Gf与Hf的特征多项式的关系;Hf进行移接变形后代数连通度的变化情况,得到了具有尽可能小的代数连通度的赋权图.本文共分为四节.本文第一节是前言,介绍了赋权图代数连通度的发展史及其已经取得的成果.第二节介绍了文章的一些基本概念.在本文第三节中,我们首先给出了perron向量与赋权函数f的关系,得到如下主要结果:定理3.1:设Gf是具有n（n > 3）个顶点m条边的k正则赋权图,则赋权函数为f（e） = w1 = ... = wm（e∈Gf,wi > 0,i = 1,2...m）.定理3.3:设Af是赋权图Gf的邻接矩阵,Lf是赋权图Gf的Laplacian矩阵,对于赋权图Gf的任意一点来说,赋权度是一个常数C（C > 0）.如果Af的特征值为θ1,θ2...θn,则Lf的特征值为C-θ1,C -θ2...C -θn.定理3.4:设Gf是一个具有n（n≥2）个顶点的k正则赋权图,Hf的构造方式如下:（1）Gf的每个顶点增加一个含有l个点的集合Ni,1≤l≤n,i = 1, 2...n.（2）对于Ni中的每个点都与相应的点vi连一条边.如果f（e） = w1,e∈Gf,那么在Hf中,f（viNi） = w2并且w1 > w2 > 0.定理3.5:Hf和Gf分别是定理3.4中的赋权图,设PAf（λ）是赋权图Gf邻接矩阵的特征多项式,PLf（λ）是赋权图Gf Laplacian矩阵的特征多项式,PAf（λ）是赋权图Hf邻接矩阵的特征多项式,PLf（λ）是赋权图Hf Laplacian矩阵的特征多项式,则有:在本文第四节中,我们利用移接变形,讨论了赋权图Hf和Tf的代数连通度变化情况,得到了具有尽可能小的代数连通度的赋权图,得到如下主要结果:定理4.2:设v1 ,v2是赋权图Hf的两个不同悬挂点,设v1∈N（v0）,v2∈N（v0）,wv0v1 = wv0v2 = w2≠a（Hf）,如果H’f = Hf\{v0v1} + {v1v2},且新边上的权wv1v2 = wv0v2 = w2≠a（Hf）,则a（Hf）≤a（Hf）.定理4.4:在赋权图Hf中的一点u0处接一条长为pk的路,pk = u0u1...uk,k≥1且路上每条边的赋权均为w,w > a > 0,设X是赋权图Hf的代数连通度af对应的单位特征向量,若X的分量xu0>0,则{xpk}为正的严格单调上升数列.定理4.5:设X是赋权图Hf的代数连通度af对应的单位特征向量,xvi是X对应于点vi的分量,若在点u0处分别接出两条长为k和l的路,k≥l≥1,分别记为Pk+1 = u0u1...uk,Pl+1 = u0v1...vk,k≥l≥1,且pk和pl中每条边的权值为w2,H’f = Hf\{vl-1vl}+{ukvl},则a（H’f）≤a（Hf）等号成立仅有可能在xu0 = 0处.定理4.9:设u1,v1是赋权树Tf的2个悬挂顶点,v1∈N（v）,u1∈N（u）,wuu1 =w1,wvv1 = w2, w1 > w2,若T’f = Tf\{vv1}+{u1v1},xu > xu1 > xv > 0,则a（Tf） < a（Tf）.

全文目录


中文摘要  3-5
Abstract  5-8
1 前言  8-10
2 基本概念  10-13
3 赋权图的构造及其性质  13-19
  3.1 赋权图的构造  13-15
  3.2 赋权图的性质  15-19
4 移接变形对代数连通度的影响  19-30
参考文献  30-32
在读期间发表的论文  32-33
后记  33

相似论文

  1. 图谱研究的一般方法,O157.5
  2. 校园内服务设施选址问题的研究与评价建模,G47
  3. 杭州技师学院比赛项目排序系统的设计与实现,O223
  4. 一类多自主系统分散H_∞控制器的分解设计,TP13
  5. 树的谱半径,O157.5
  6. 复杂动态时滞网络的同步与无源性分析,O157.5
  7. FSO网络的拓扑形成和路由算法设计,TN929.12
  8. 时滞领航系统的协同控制器设计及稳定性分析,TP273
  9. 基于谱图理论的点模式匹配算法研究,TP391.41
  10. 几类冠图的临界群,O157.5
  11. 赋权图匹配理论研究及联机手写汉字识别应用,TP391.43
  12. 由图的谱（和角）确定的问题,O157.5
  13. 两类图的临界群,O157.5
  14. 关于直径固定的树的最小谱半径,O157.5
  15. 图的主特征向量及其应用,O157.5
  16. 最大赋权单圈图的谱半径,O157.5
  17. 构造健壮的虚拟骨干网分簇算法研究,TN929.5
  18. 某些图的谱半径与代数连通度,O157.5
  19. 关于图的Laplace谱和图的邻接谱的研究,O157.5
  20. 满二叉树的Laplacian特征值与图的Merris指数,O157.5

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com