cayley图与点传递图之间关系讨论

《cayley图与点传递图之间关系讨论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、内蒙古师范大学硕士学位论文中文摘要在数学和计算机科学这两个平行发展的学术领域，都同时致力于研究组合结构中的相同课题：图论语言称之为点传递图，计算机语言称之为具有较强对称性的网络，特别是对于最初的典型例子Cayley图的研究，己经得到了很多令人满意的结果．我们知道，Cayley图一定是点传递图，但点传递图未必是Cayley图．然而Godsil在文献[1]得到结论：每一个连通的点传递图都是一个Cayley图的收缩核，并且具体地给出由点传递图构造Cayley图的方法．本文主要研究连通的点传图与由它构造的Cayley

2、图之间的关系．首先研究这两个图几个代数性质方面的关系．如邻接矩阵，特征多项式，邻接矩阵的特征根，Laplace矩阵的特征根之间的关系，然后研究这两个图在完美性，Hamiiton性，强正则性等图论性质方面的关系．关键词：邻接矩阵，特征多项式，Laplace矩阵，完美图，生成树内蒙古师范大学硕士学位论文ABSTRACTIntheacademicareaofmathematicsandcomputerscience，theyaimatstudyingthesimilartopicofcombinationstruc

3、ture：Graphtheorylanguageiscalledvertex—transitivegraph，computerlanguageisnamedthenetwithstrongersymmetry．Manyconclusionhavebeenprovedasthetypicalexample--Cayleygraph．Cayleygraphmustbeavertex—transitivegraph，butvertex—transitivegraphmaynotbeCayleygraph．Yet,G

4、odsilgotaresult：Anyconnectedvertex-transitivegraphisaretractofaCayleygraphandgavethewayconstructingtheCayleygraphbyaconnectedvertex—transitivegraph．Wemainlyresearchrelationsbetweentheminthispaper．Wefirstlyconcemalgebraicpropertiesincludingtheadjacencymatrix

5、，characteristicpolynomialandtheeigenvaluesoftheLaplace．Thenweinvestigatethegraphtheoryproperties--perfection，Hamiltonandstronglyregular．Keywords：Adjacencymatrix，Characteristicpolynomial，Laplacematrix，Perfectgraph．Thenumberofspanningtrees独创性声明本人声明所呈交的学位论文是本人

6、在导师指导下进行的研究工作及取得的研究成果，尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得内蒙古师范大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示感谢。签名：日期：年月日关于论文使用授权的说明本学位论文作者完全了解内蒙古师范大学有关保留、使用学位论文的规定：内蒙古师范大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容

7、编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。签名：导师签名：l勾童嗅日期：房砌尹年∥月罗日引言群和图一直是人们关注的数学对象．但是二者结合起来，用图来研究群及用群来研究图成为一个新的数学领域，是从上个世纪的三四十年代开始的．从已知的研究结果中可以看出，用群论方法研究有较高对称性的图有非常重要的意义，比较典型的具有较高对称性的图是点传递图(特别是Cayley图)．用对称性对图进行划分，可以分为：主

8、要有点传递图(也称为可迁图或点对称性图)，边传递图，对称图，距离传递图，弧传递图等．在计算机科学方面，计算机互联网络的拓扑结构是决定网络性能的重要因素，而网络结构的高对称性和正则性是网络设计者所追求的目标之一【¨，现在，网络设计者经常使用有限图或者有限有向图作为互联网络的模型．用图的顶点代表网络的结点，用图的边代表网络的通信线[21，在大型互联网络设计中，经常使用的模型大部分是各种熟悉的群的Cayl