《图同构的判定 数学毕业论文》由会员分享，可在线阅读，更多相关《图同构的判定 数学毕业论文（21页珍藏版）》请在金锄头文库上搜索。
1、平顶山学院本科毕业论文（设计） 毕业论文(设计)题 目: 图同构的判定 院(系): 数学与信息科学学院 专业年级: 数学与应用数学 姓 名: 学 号: 指导教师: 2009年 04月 2日17 Thesis (design)Subject: Isomorphism Judgment of Graphs College: Mathematics and Information Science Major and Grade: Mathematics and Applied Mathematics, Grade 2005 Name: No.: Advisor: April 2 , 20093中文摘
2、要本文对于两图的同构的判定方法进行探讨，通过同构定义、邻接矩阵、关联度序列、出入度序列等方法判定两图同构与否，并给出简单的应用.关键词 : 图，同构，邻接矩阵，关联度序列，出入度序列.AbstractAn interesting problem is to determine whether two graphs are isomorphic. The following is about some ways of the isomorphism definition,the adjacent matrix, the interrelatedness sequence,leaves in-de
3、gree sequence to show that two simple graphs are isomorphic or not, and meanwhile gives some simple application.Key words : graphs, isomorphism ，adjacent matrix，the interrelatedness sequence, leaves in-degree sequence .目 录中文标题 中文摘要 关键词 英文标题 英文摘要 关键词 正文 11图的同构定义 12图同构判定及简单应用 22.1用同构定义判定图同构 22.2用邻接矩阵判
4、定图同构 42.3用关联度序列法判定同构 82.4用出入度序列法判定同构 103用不变量判定两图不同构 12参考文献 14致谢 “图论”是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系.图论是一门极有兴趣的学问，其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、电信领域等等.严格地讲，图论是组合数学的一个分支，例如，它交叉运用了拓扑学、群论和数论.图论就是研究一些事物及它们之间关系的学科，现实世界中的许多事物能用图来表示其拓扑结构，把实际问
5、题的研究转化为图的研究，利用图论的相关结论对这些问题作分析或判断.在抽象代数中，同构指的是一个保持结构的双射.在更一般的范畴论语言中，同构指的是一个态射，且存在另一个态射，使得两者的复合是一个恒等态射.正式的表述是：同构是在数学对象之间定义的一类映射,它能揭示出在这些对象的属性之间存在的关系.若两个数学结构之间存在同构映射，那么这两个结构叫做是同构的.一般来说，如果忽略掉同构的对象的属性的具体定义，单从结构上讲，同构的对象是完全等价的.在数学中研究同构的主要目的是为了把数学理论应用于不同的领域.如果两个结构是同构的，那么其上的对象会有相似的属性，对某个结构成立的命题在另一个结构上也就成立.因此
6、，如果在某个数学领域发现了一个对象结构同构于某个结构，且对于该结构已经证明了很多定理，那么这些定理马上就可以应用到该领域.如果某些数学方法可以用于该结构，那么这些方法也可以用于新领域的结构.图的同构是图论学科中的基本问题之一,属于图论中多个NP一完全问题之一.所谓图的同构,简单地说,就是两个表示的关联关系完全相同，图同构与抽象代数中提到的同构密切联系，两个图同构意味着两个图具有完全相同的结构特征，即如果能识别出两个或多个图是同构的，则可以把这些图的研究归结为一个图的研究，因此，对同构图的探讨，无疑会给图论中许多问题的研究带来方便.1.图的同构定义定义 设V和E是有限集合,且V不是空集,如果E是
7、 （, ）| V且V的子集,则称G=为无向图;如果E是VV (集合的笛卡儿乘积)的子集,则称G=为有向图。无向图和有向图统称为图,其中V的元素称为图G的结点, E的元素称为图G的边,图G的结点数目称为它的阶.定义 设，为两个无向图（两个有向图），若存在双射函数,使得 ,当且仅当 (当且仅当)并且与（与）的重数相同，则称和同构，记作,称作到的同构函数.图之间的同构关系构成全体图集合上的特殊二元关系等价关系，事实上，(1) (自反性);(2)若,则 (对称性);(3)若,则 (传递性).在这个等价关系的每一个等价类中的图都是同构的.2.图同构判定及简单应用2.1用同构定义判定图同构由于图包括无向图
8、和有向图,所以可以把图同构的定义重新定义为无向图同构和有向图同构,即1)若无向图和的顶点之间保持一一对应,边之间也保持一一对应,则两图同构.2) 若有向图和的顶点之间保持一一对应,边之间保持一一对应,而且对应点与对应边之间保持相同的关联关系,则两图同构.例1 判定下面两个图，同构. ， 证明 取 , ， , .以上是点的对应，下面是边的对应: 综上所述，为双射函数，根据同构的定义，同构.例2 判定下面两图同构. 证明 取 ： , , , .以上是点的对应，下面是边的对应: 综上所述，g 为双射函数，根据图同构定义，以上两图同构.总之,通过图同构定义，只要找到点与点，边与边之间的一一对应，并且它
9、们之间保持相同的关联关系,就可判定两图同构.但有时为了方便找对应关系，可以先列个图表表示结点间的关联度.如例2,可以通过表1观察到点对应：或，然后再找边对应，就可以判定两图同构.表1 通过图同构定义，了解同构可以用直观扮析方法:把线看作可伸缩的橡皮筋,把点看作固定这些橡皮筋的图钉.如果把一个图的某些“图钉”连同“橡皮筋”取下,钉在平面上的其他位置,得到与另一个图相同的结构和形状,则这两个图一定同构.如上例1,把的结点1移至边（2 , 3）的左下方,再把整个图顺时针旋转90,即得到图.2.2 用邻接矩阵判定图同构定义 设图G=,V=，令为顶点邻接到顶点边的条数，称为G的邻接矩阵，记作,或简记为A
10、. 通过例2图表的提示以及定义2.2.1知道可以把点与点，边与边之间的一一对应用邻接矩阵表示出来.定理 如果图和图是同构的当且仅当对某一顶点的顺序,他们的邻接矩阵是一样的.例3 判定以下两图同构. 分析 为证明图同构，必须使结点，边一一对应，保持结点邻接性，此题两图都有5个顶点8条边，1个结点2度，2个结点3度，2个结点4度，很显然，c与2对应（都2度），又因为图的对称性，a与e 、b与d是对称的，b与3度的a相邻，3与3度的1、4相邻，可以任意选，如选a与1相邻，则可确定点的对应.证明 取 ： , , , , .A (1) = , A (2) = 即A (1)= A (2)，由定理2.2.1
11、知，以上两图同构.例4 判定如下两图同构. 证明 取 ： , , , , , , . A(1)= , A(2) =即A (1)= A (2)，由定理2.2.1知，以上两图同构. 定义 对矩阵A= 施行第1种初等行(或列)变换,是指交换矩阵A的2行(或2列).交换A的第行和第行记为,交换A的第列和第j列记为.定义 设A= 是一个n阶方阵,对任意选定的正整数,如果对矩阵A同时进行第一种初等变换与第一种初等列变换得到B,则称对A施行了一次对称变换得到矩阵B.记为.定理 n阶标定图与同构的充要条件是存在的同构变换,使得化成.一般而言,待判定图顶点对应关系是未知的,而同构判定正是要找出这样的对应关系.通
12、过定理2.2.2很容易判定图同构,即,先写出与的与,然后调整的行序和列序(行的交换与列的交换),如能使,则,如所有可能的行交换与列交换都不能使,则判定与两图不同构.例3(续)分析 在例3中,首先找到点的对应,在利用定理2.2.1判定图同构.而给出定理2.2.2之后,发现判定图同构时用定理2.2.2方便了很多,即,不必先找到点的对应, 直接把邻接矩阵写出就可以了.证明 = , = =由定理2.2.2知，两图同构.在以上例题中,也可找到点的对应.2.3 用关联度序列判定同构定义 如果无向图G中n(1nN,N为G的数)个点以及连接于这n个点之间的边组成的子图是连通的,那么,这个子图称为图G的n点连通子图,记为, 是这n个点的集合.定义在无向图G中,与一个n点连通子图相连接的边(不包括的内部边)称为关联边.关
