图同构的判定 数学毕业论文

《图同构的判定 数学毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、平顶山学院本科毕业论文（设计）毕业论文(设计)题目:图同构的判定院(系):数学与信息科学学院专业年级:数学与应用数学姓名:学号:指导教师:2009年04月2日2010年17平顶山学院本科毕业论文（设计）Thesis(design)Subject:IsomorphismJudgmentofGraphsCollege:MathematicsandInformationScienceMajorandGrade:MathematicsandAppliedMathematics,Grade2005Name:No.:Advisor:

2、April2,20093中文摘要本文对于两图的同构的判定方法进行探讨，通过同构定义、邻接矩阵、关联度序列、出入度序列等方法判定两图同构与否，并给出简单的应用.关键词:图，同构，邻接矩阵，关联度序列，出入度序列.AbstractAninterestingproblemistodeterminewhethertwographsareisomorphic.Thefollowingisaboutsomewaysoftheisomorphismdefinition,theadjacentmatrix,theinterrelated

3、nesssequence,leavesin-degreesequencetoshowthattwosimplegraphsareisomorphicornot,andmeanwhilegivessomesimpleapplication.Keywords:graphs,isomorphism，adjacentmatrix，theinterrelatednesssequence,leavesin-degreesequence.目录中文标题中文摘要关键词英文标题英文摘要关键词正文·······················

4、································11图的同构定义············································12图同构判定及简单应用··································22.1用同构定义判定图同构·······························22.2用邻接矩阵判定图同构·······························42.3用关联度序列法判定同构····························

5、·82.4用出入度序列法判定同构·····························103用不变量判定两图不同构·································12参考文献···················································14致谢“图论”是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系.图论是一门极有

6、兴趣的学问，其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、电信领域等等.严格地讲，图论是组合数学的一个分支，例如，它交叉运用了拓扑学、群论和数论.图论就是研究一些事物及它们之间关系的学科，现实世界中的许多事物能用图来表示其拓扑结构，把实际问题的研究转化为图的研究，利用图论的相关结论对这些问题作分析或判断.在抽象代数中，同构指的是一个保持结构的双射.在更一般的范畴论语言中，同构指的是一个态射，且存在另一个态射，使得两者的复合是一个恒等态射.正式的表述是：同构是在数学对象之间定义的一类映射,它能揭示出在这些对象的

7、属性之间存在的关系.若两个数学结构之间存在同构映射，那么这两个结构叫做是同构的.一般来说，如果忽略掉同构的对象的属性的具体定义，单从结构上讲，同构的对象是完全等价的.在数学中研究同构的主要目的是为了把数学理论应用于不同的领域.如果两个结构是同构的，那么其上的对象会有相似的属性，对某个结构成立的命题在另一个结构上也就成立.因此，如果在某个数学领域发现了一个对象结构同构于某个结构，且对于该结构已经证明了很多定理，那么这些定理马上就可以应用到该领域.如果某些数学方法可以用于该结构，那么这些方法也可以用于新领域的结构.图的同构是

8、图论学科中的基本问题之一,属于图论中多个NP一完全问题之一.所谓图的同构,简单地说,就是两个表示的关联关系完全相同，图同构与抽象代数中提到的同构密切联系，两个图同构意味着两个图具有完全相同的结构特征，即如果能识别出两个或多个图是同构的，则可以把这些图的研究归结为一个图的研究，因此，对同构图的探讨，无疑会给图论中许多问