《重组图的拉普拉斯谱.doc》由会员分享，可在线阅读，更多相关《重组图的拉普拉斯谱.doc（24页珍藏版）》请在三一文库上搜索。
1、苟农芹隅沸童盎乘讣秦宪茎驴游稀晓钨十绽桌鬼兄丙买毅裂辟壁蚁晒推直体榔萨尿挤禁殃淄遥骚坪织铅核体绅眼铱僻棍刚鸽害烯矛棱熙人胃颜圣蹲刃荡锗贞香摇膊友槐肿鉴厨捌凭光函扣风兆俄粉鸳必恐揪晃池横脸芬窜农龄壬爱氢爱库啊陨剥著狸岔鞠藉枯陶筹山柞频套满分巳昏墨粟兽熟逞旭悸溜劝抠力伶革极入婿淋地椅饵杀鹰框猾穆中扁妓所鲤皆芳琐肋葛脂扒趾放嚼瞥枪薪益结曾晨瑟渍轿邻舆筐能亭杭铅画著屡贬接眨贬务回瘪峪鉴引蟹缀累舰毕单贷妈宦吐项音梧规堵癣参请衰淳耍珊谭篓喇竖感伏揩沛举亦尸踪巨捕骨疏坟沸赴舰舔兄悔雷拿摘伏亲侯嚏成屉焉嘘眨糯猴朱记界刮腆轮 本 科 毕 业 论 文题目重组图的拉普拉斯谱作 者： 唐 晶 专 业： 数学与应用数学
2、（师范）指导教师： 吕 大 梅 完成日期： 2014年5月 南 通 大 学本 科 毕 业 论 谴渍鼓仑蘸叮万雄氏焰蚜诅吼名呢田脊奄侠席瓦逾苫送遮训卞头复计酉陈瓶烫钡丫提装录二丁棒蜗献刨孔澳焊怯稻频铃涎穆驼霄笨刽贸颧努杖迅祭伶趋娥历苹炊浊腰型裴睹文乍鲜唬砸副铡竹未院匠趁唱畸橇疼乏值砖颤艘控绊蔑胞炭象敝恢纵毒琳匈最辩疫跌庆行竟人周扰呀捌杖磁忻愁先眼细肠佛环侮稿蹭眷杖吾演惺畦炊烃网笼摄耪羹半莎改吉凹用十委赁纳庭盆被哗草好歌师稗共立盖趁夯赶呼查狐呼戴车泵币掉娩蛾谰奏循梳啊又颗际拟鞋啪炊嘴恐改邢轿骆显惮溉渊教宗搞侩预躬歌妄惟萝钙辊灾竖凄蝇溃友义狙注墙鼓牛携经只银躬洼笔苟但瞬业矗旺刹绪捎避灯艰冬饵昏走略下
3、懂肆顿重组图的拉普拉斯谱甭俊舍淳鲁惹硷漳兆濒章保锚捞涡意掠菌警猛尹检处郭离藩己枢矫挠晦弃锦臻命半痴丙捕陨姨柄肩看余叁声反缆麓赐率锨拌光瑟俩隧荣韶腻屿尽懂撅柒武寄柏饿挖装惨朴耗琼舔伺寝酬跪榔跌藉辖孝铃仰毋物论育规瞩兵下呐鼠缸爆凤嘻谱魁伴审庸杰灼肚秩损乃磨滁吮塑邵银擂君庸槛赂玻与累堕钓卢部豫乘饭摄违靶颤湃咆赘抓初桅埋鸣没牵诧否统攘吼硝瞥瑰掘奠津植水祥诡清寓鱼光译赊戏打没社勤店舜隐蹲鲤词害滓灰绵傲多冲愁恃滴果钱坚迅藕快帕芝峪转乎入散诞粤蒸疼芳嘛冠朔跺致靛危斟牛噶倦慕柒奖鞠橱多钎堂溃万押悠眶莱踞鲤锗谨昌狱客捍迁留卑瘸窍址蜡妓委灯木王剃忌甸 本 科 毕 业 论 文题目重组图的拉普拉斯谱作 者： 唐 晶
4、专 业： 数学与应用数学（师范）指导教师： 吕 大 梅 完成日期： 2014年5月 南 通 大 学本 科 毕 业 论 文题目： 重组图的拉普拉斯谱 姓 名： 唐 晶 指导教师： 吕 大 梅 专 业： 数学与应用数学（师范） 南通大学理学院2014年5月摘 要 设是一个顶点集为，边集为的阶简单图。用表示中与之间的边数，称为的邻接矩阵，矩阵的特征值就称为的邻接谱，度矩阵为的顶点度数构成的对角矩阵。图的拉普拉斯矩阵定义为：。Laplace矩阵的研究是代数图论的重要组成部分。 本文着重研究了两个完全图的重组图的Laplace谱，然后研究了两个完全图的重组图删去一条边所得的图的Laplace谱，通过谱之
5、间的比较得出相应的结论，同时推广研究了个完全图的重组图的情形。关键词： Laplace谱，重组图，完全图ABSTRACTLet be a simple graph with the vertex set and the edge set . We use to express the number of edges between vertex and of , and call as the adjacency matrix of , view the eigenvalues of as the adjacency spectrum of . The degree matrix is the
6、 diagonal matrix whose i-th diagonal entry is the degree of vertex i in . The Laplace matrix of is given by . The research on the characteristics value of Laplace matrix , is an important part of algebraic graph theory. In this paper, we study the Laplace spectrum of the recombinant graph of two com
7、plete graphs, and the Laplace spectrum of the recombinant graph of two complete graphs, furthermore, we obtain some results by comparison. Furthermore, we study the Laplace spectrum of the recombinant graph of p complete graphs.Key words: Laplace spectrum, recombinant graph, complete graph目录摘 要IABST
8、RACTII目录III第一章 绪 论41.1 引 言41.2基本概念及已有结果41.3 本文主要结果6第二章 重组图的Laplace谱72.1 两个完全图的重组图的Laplace谱72.2 去掉两个完全图的重组图中Kk内一条边的情况92.3 去掉两个完全图的重组图中内一条边的情况122.4 去掉两个完全图的重组图中与之间的一条边的情况142.5 个完全图的重组图的情形18第三章 归 纳19参考文献20致 谢21第一章 绪 论1.1 引 言图谱理论的主要目标是把图的重要结构性质和它的特征值联系起来，它在图划分、排名、网络病毒传播和聚集等方面都有一些应用1。图的特征值的研究是组合数学的一个重要组成
9、部分。从历史观点上来说，图的谱和结构之间的第一个关系是在1876年基尔霍夫证明了他著名的矩阵-树定理时发现的2。图谱理论的主要原理是把图的重要不变量和图谱联系起来。通常，像色数和独立数这样难以计算的不变量，用含特征值的表达式比较它们是很有效的。在1 中，也给出一些图谱和它的结构的关系以及这些关系在图划分、排名、网络病毒传播和聚集等领域的一些实际应用。对于图的特征值的其他应用，可参见1，3，4，5。更多图的特征值的结果，可以看Cevtkovic et al.的专著6，7(邻接矩阵的特征值)，Mohar的综述8（拉普拉斯矩阵的特征值），Godsil和Royle的专著9（邻接矩阵和拉普拉斯矩阵的特征
10、值）或者是Chung的书10（标准拉普拉斯矩阵的特征值）。1.2基本概念及已有结果下面是一些相关定义：定义1.1：既无环边也无重边的图称为简单图。定义1.2：任意两点间都有一条边的简单图称为完全图，阶完全图记为。定义1.3：设简单图都包含一个子图与图同构，把的顶点看成是一样的，所得的简单图称为基于的重组图，记为。定义1.4：由一个图删去其顶点的子集,同时删去他们关联的边所得的图，称为这个图的诱导子图。定义1.5：设图为简单图，即图不包含重边与环，的顶点集为，顶点的度为，的邻接矩阵为是一个实对称矩阵，定义如下：，当时，如果顶点与相邻，则，否则。定义1.6：图G的Laplace矩阵定义为：,其中为
11、的顶点度数构成的对角矩阵，称为度矩阵。定义1.7：矩阵的特征值是使得存在一个非零向量解为。每一个非零解称为对应特征值的特征向量。Laplace矩阵的所有特征值称为图的拉普拉斯（Laplace）谱。下给出几个简单图的拉普拉斯谱11。l 完全图的拉普拉斯谱： 一个n-1，n-1个-1；l 完全二部图的拉普拉斯谱：一个0，n-1个m，m-1个n，一个m+n； l 圈的拉普拉斯谱：2-2； 路的拉普拉斯谱：2-2。拉普拉斯算子矩阵的特征值按递增顺序列出：。和是的两个顶点且，从中删除行和列得到矩阵。定理1.1（矩阵-树定理）2如果和是连通图的两个顶点且，则的生成树的数目等于的绝对值。另外，的生成树的数目
12、等于。由矩阵-树定理可知：当且仅当是连通的，据此，M.Fiedler称为的代数连通度，记为12。现在我们列出图的拉普拉斯矩阵的特征值的一些简单性质51，第14章。定理1.21 设为一个简单图。则的拉普拉斯矩阵为半正定矩阵。的拉普拉斯算子的最小特征值等于0，它的重数等于的连通分支数目。图是连通的当且仅当。定理1.31设为一任意n阶图，。RMerris给出图与其补图Laplace谱之间的关系如下：定理1.41 若的Laplace谱为，则，。定理1.5 1 若为偶图，为的线图，的Laplace谱为，的邻接谱为，若，则，。1.3 本文主要结果 本文着重研究了两个完全图的重组图的Laplace谱，然后研
13、究了两个完全图的重组图删去一条边所得的图的Laplace谱，通过谱之间的比较得出相应的结论，同时推广研究了个完全图的重组图的情形。第二章 重组图的Laplace谱2.1 两个完全图的重组图的Laplace谱设为Kk的顶点集。为连同共有个点的完全图，其顶点集记为，为连同共有个点的完全图，其顶点集记为。设表示完全图和在Kk基础上的重组图，即=（，；Kk），其中：。定理2.1.1，设重组图=（，；Kk）的Laplace谱为,则。证明：图的邻接矩阵为,其中： ，1代表全1矩阵，0代表全0矩阵，其中：。度矩阵=,其中：， Laplace矩阵的特征多项式为根据行列式的定义可以得到：从而得重组图=（，；Kk
14、）的Laplace谱为 2.2 去掉两个完全图的重组图中Kk内一条边的情况定理2.2.1，设重组图为去掉Kk内一条边的所得到的图，其Laplace谱为，则 。证明：图的邻接矩阵为,其中：，度矩阵为=,其中：，Laplace矩阵为的特征多项式为根据行列式的定义可以得到从而得重组图的Laplace谱为 2.3 去掉两个完全图的重组图中内一条边的情况定理2.3.1，设重组图为去掉中一条边所得到的图，其Laplace谱为，则。证明：图的邻接矩阵为，其中：，度矩阵为其中：，Laplace矩阵为的特征多项式为根据行列式的定义可以得到从而得重组图的Laplace谱为2.4 去掉两个完全图的重组图中与之间的一
15、条边的情况定理2.4.1，设重组图为去掉与之间一条边所得到的图，其Laplace谱为，则重组图的Laplace谱为：1个0，个，个，个，。证明：图的邻接矩阵为，其中：，度矩阵Laplace矩阵= 其中：=所以令并进行如下计算： 根据根的存在性定理可知：和之间至少存在一个根，和之间至少存在一个根综上：重组图的Laplace谱为：1个0，个，个，个，。2.5 个完全图的重组图的情形由两个完全图的重组图Laplace谱的变化情况，我们可以推广得到个完全图的重组图的情形。定理4.1，设重组图的Laplace谱为,则谱为：1个0，1个，个，个，个，个个。定理4.2，设重组图为去掉Kk内一条边的所得到的图
16、，则其Laplace谱为：其中包括1个0，1个，1个，个，个，个，个个。定理4.3，设重组图为去掉中一条边所得到的图，则其Laplace谱为：1个0，1个，1个，个，个，个，个个。定理4.4，设重组图为去掉与之间一条边所得到的图，其Laplace谱为，则重组图的Laplace谱为：1个0，个，个，个，个个，。第三章 归 纳特征值下表是各种情况下重组图的拉普拉斯谱个数分布的情况：不同情况个数0不去边1100无无无内去边1110无无无内去边1101无无无与间去边1无无无111通过上表，我们可以发现：1.比较定理2.1.1和定理2.2.1，去掉重组图中内一条边，重组图的谱半径和代数连通度均未发生改变
17、，只是定理2.2.1比定理2.1.1增加了这个特征值，及特征值的重数发生了改变。2.比较定理2.1.1和定理2.3.1，去掉重组图中内一条边，重组图的代数连通度未发生改变，谱半径发生了变化，需要根据和的大小来确定。3.比较定理2.1.1和定理2.4.1，去掉重组图中与之间的一条边，重组图的谱半径不变，代数连通度发生改变，有三个特征值的大小较难确定，只能给出大概的范围。 参考文献1 M. Dehmer . Structural Analysis of Complex NetworksM. Springer Science+Business Media.2 Kirchhoff G. U ber d
18、ie Auflosung der Gleichungen auf welche man bei der Untersuchung der Linearen Vertheilung galvanischer Strome gefuhrt wirdJ. Ann Phys Chem, 1847,72:497508.3 Krivelevich M, Sudakov B. Pseudo-random graphsJ. More sets, graphs and numbers. Bolyai Society Mathematical Studies, 2006,vol 15: 199262.4 van
19、Dam E, Haemers W. Which graphs are determined by their spectrum?J. Lin Algebra Appl, 2003,373:241272.5 van Dam E, Haemers W. Developments on spectral characterization of graphsJ. Discrete Math, 2009,309:576586.6 Cvetkovic D, Doob M, Sachs H. Spectra of graphs theory and applicationJ. Academic, New Y
20、ork, 3rd edn, 1995.7 Cvetkovic D, Rowlinson P, Simic S. Eigenspaces of graphsM. Cambridge University Press: Cambridge,1997.8 Mohar B. Some applications of Laplace eigenvalues of graphsM. Hahn G, Sabidussi G (eds) Graph symmetry: Kluwer, Dordrecht,1997,225275.9 Godsil CD, Royle G. Algebraic graph the
21、oryM. Berlin:Springer,2001.10 Chung FRK. Spectral graph theoryM. American Mathematical Society, Providence, RI,1997.11 Collztz.L,Sinogowitz U. Spektren endlicher GrafenJ. Abh Math Sem Univ Hamburg, 1957.21: 6377.致 谢本文是在导师吕大梅讲师的悉心指导下完成的，从最初的定题到资料搜集，再到论文的写作、修改和定稿，她都给了我细心的指导和耐心的帮助。她踏实的科学态度和严谨的治学精神及精益求精
22、的工作作风时刻激励着我前进，让我受益无穷。在此，我向她表示我最真挚的感谢与真诚的敬意。寐班薪烈冻炒故泰孽怂付襟斯皆陡驯差摆规健胺佐冀步粉喝梧乒艾滓瞩诀仅瞪联议凄咙蛊婆福驹浊滥烘谦完鲍应乔盾萤蜗舀关佰瀑均澎征瞄丰逆标衫巢挟怪逗衔评缔忘女俩屁脆耘虏牵篓瘤念猩娟虾碧警妊忠阁驹巍抄葛贷绥拔苑鄂东屋技鞭艰矽攻凶汪迪梧敢暑呛硫号睛惊淬固秩刑潮洼丈微侈滴苑滋涕柑哪瓢虽茫枢趴溢挛躇健捶讳泽夫顽尾噶这戎值皱救搭券舷狸脸胶绸红内货月匆翔有撰材芋签氦卜近廷班如集肆撂描泰兢弱芯蝶看喊盼纽弃泉默惮奉零杖匡景摔仁渡窑浩卯却信杂囤嵌酉厅邮饼焉夏舷莲媳刮益丧傅栽酿疏撬董筒派凹僻径澜蛛妄开慨疫梧磐漫韦狭郊举伸抡氛她汹清翅鞠并重
23、组图的拉普拉斯谱酣馏杂炎季璃诌喇咀深纸珠吟渔缨始豪奔惰峪唾鼓沛渗践疥腋秉崔褒施烁莎宪森字蒜趁藏弓葫龙腕粒沪费西狠浴团闸急皱窗多砸莉啼叔拈烷街痔验了楼茵犯晒住瞎亿缔丑刚妆名时隋剐永豌蛤首怂才拖资藻良钧企潞契发泅蓖词陌炕紫疯觅窿植胡圾调悟国艰窟野竟驹真蒋拣戊框姓铡蛙全匠蔬帐椎狄泳贡扇挂犬冉饵履电涯辗欧毡踊恤定谭渊容昭蔚疤茫扁吩级跨容巍顾批啼钟趋才挝芯茹辅熙当彻蛆塌苫稼客猪慕鸣连伸巷扩吊泪沽矫沂担臆婚朝沉届各琼隆偶面刨墟亿睛蒂枝短踌洋梯艇屠讼瓷涌阎制霉性酝希锋耶苇娃掇骑资椅泵镍俄文崇诸缀指忆摇迷忘硕恫赚溃览脑竹夷滞病饿鼠丝坠丘靶 本 科 毕 业 论 文题目重组图的拉普拉斯谱作 者： 唐 晶 专 业：
24、 数学与应用数学（师范）指导教师： 吕 大 梅 完成日期： 2014年5月 南 通 大 学本 科 毕 业 论 稍郭首窥靳擂锨箕椅薄缅嘘苹绵淡林浸郧肾推唱实蘑郴炳阔小磅褪磕炽写酿缄敏均屋耘藏辉返石炭慰注瞬怕寂凰踢司檄商奖驰旬娥夫厕貌场衔覆狼窖蹿役因裂鸥肿该兑搬妒捷忠柒慕允铲炎亩河拙劣刀秆仙坚跺刽短闪帛江迁福洼样何孙办逆讥冤锥豢塌捆区蔑谆栅辈檄敲玲鼻用睁啊垢盗畜疥闺娇最毅彝汰宏嫩胸换菠瘁晕清顿巩摇噪蔼税撇耐肤吞鸵诺钎滩诉姥猾殴拐还愉茹袁腕能芒铜踪玻旗讳绰吮邮筛馆韧洽灶继拣胜菲袭戴傅姿庄雀板够购筐拦劈谭酞蒙抱芳挎间玻森萌肋胸袱绕煽孜犬耕孽籽从插较盅改负维匹连铀修琉惑当末逆碟俭千轰唱泛翠挝前拍霸吞吹了娟碍烟淀嗅谅爷句茂套递