论文部分内容阅读
赋权图的研究已经被用来解决许多实际问题,网络设计以及电路设计实际上都依赖于赋权图.设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）.