数学与应用数学毕业论文（设计）-图同构的判定

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

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

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

3、followingisaboutsomewaysoftheisomorphismdefinition,theadjacentmatrix,theinterrelatednesssequence,leavesin-degreesequencetoshowthattwosimplegraphsareisomorphicornot,andmeanwhilegivessomesimpleapplication.Keywords:graphs,isomorphism，adjacentmatrix，theinterrelated

4、nesssequence,leavesin-degreesequence.目录中文标题中文摘要关键词英文标题英文摘要关键词正文·······················································11图的同构定义············································12图同构判定及简单应用··································22.1用同构定义判定图同构·······························

5、22.2用邻接矩阵判定图同构·······························42.3用关联度序列法判定同构·····························82.4用出入度序列法判定同构·····························103用不变量判定两图不同构·································12参考文献···················································14致谢平顶山学院本科毕业论文（设计）“图论”是

6、数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系.图论是一门极有兴趣的学问，其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、电信领域等等.严格地讲，图论是组合数学的一个分支，例如，它交叉运用了拓扑学、群论和数论.图论就是研究一些事物及它们之间关系的学科，现实世界中的许多事物能用图来表示其拓扑结构，把实际问题的研究转化为图的研究，利用图论的相关结论对这些问题作分析或

7、判断.在抽象代数中，同构指的是一个保持结构的双射.在更一般的范畴论语言中，同构指的是一个态射，且存在另一个态射，使得两者的复合是一个恒等态射.正式的表述是：同构是在数学对象之间定义的一类映射,它能揭示出在这些对象的属性之间存在的关系.若两个数学结构之间存在同构映射，那么这两个结构叫做是同构的.一般来说，如果忽略掉同构的对象的属性的具体定义，单从结构上讲，同构的对象是完全等价的.在数学中研究同构的主要目的是为了把数学理论应用于不同的领域.如果两个结构是同构的，那么其上的对象会有相似的属性，对某个结构成立的命题在另一个结

8、构上也就成立.因此，如果在某个数学领域发现了一个对象结构同构于某个结构，且对于该结构已经证明了很多定理，那么这些定理马上就可以应用到该领域.如果某些数学方法可以用于该结构，那么这些方法也可以用于新领域的结构.图的同构是图论学科中的基本问题之一,属于图论中多个NP一完全问题之一.所谓图的同构,简单地说,就是两个表示的关联关系完全相同，图同构与抽象