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

平顶山学院本科毕业论文（设计） 毕业论文(设计)题 目: 图同构的判定 院(系): 数学与信息科学学院 专业年级: 数学与应用数学 姓 名: 学 号: 指导教师: 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中文摘要本文对于两图的同构的判定方法进行探讨，通过同构定义、邻接矩阵、关联度序列、出入度序列等方法判定两图同构与否，并给出简单的应用.关键词 : 图，同构，邻接矩阵，关联度序列，出入度序列.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-degree 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用邻接矩阵判定图同构 42.3用关联度序列法判定同构 82.4用出入度序列法判定同构 103用不变量判定两图不同构 12参考文献 14致谢 “图论”是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系.图论是一门极有兴趣的学问，其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、电信领域等等.严格地讲，图论是组合数学的一个分支，例如，它交叉运用了拓扑学、群论和数论.图论就是研究一些事物及它们之间关系的学科，现实世界中的许多事物能用图来表示其拓扑结构，把实际问题的研究转化为图的研究，利用图论的相关结论对这些问题作分析或判断.在抽象代数中，同构指的是一个保持结构的双射.在更一般的范畴论语言中，同构指的是一个态射，且存在另一个态射，使得两者的复合是一个恒等态射.正式的表述是：同构是在数学对象之间定义的一类映射,它能揭示出在这些对象的属性之间存在的关系.若两个数学结构之间存在同构映射，那么这两个结构叫做是同构的.一般来说，如果忽略掉同构的对象的属性的具体定义，单从结构上讲，同构的对象是完全等价的.在数学中研究同构的主要目的是为了把数学理论应用于不同的领域.如果两个结构是同构的，那么其上的对象会有相似的属性，对某个结构成立的命题在另一个结构上也就成立.因此，如果在某个数学领域发现了一个对象结构同构于某个结构，且对于该结构已经证明了很多定理，那么这些定理马上就可以应用到该领域.如果某些数学方法可以用于该结构，那么这些方法也可以用于新领域的结构.图的同构是图论学科中的基本问题之一,属于图论中多个np一完全问题之一.所谓图的同构,简单地说,就是两个表示的关联关系完全相同，图同构与抽象代数中提到的同构密切联系，两个图同构意味着两个图具有完全相同的结构特征，即如果能识别出两个或多个图是同构的，则可以把这些图的研究归结为一个图的研究，因此，对同构图的探讨，无疑会给图论中许多问题的研究带来方便.1.图的同构定义定义 设v和e是有限集合,且v不是空集,如果e是 （, ）| v且v的子集,则称g=为无向图;如果e是vv (集合的笛卡儿乘积)的子集,则称g=为有向图。无向图和有向图统称为图,其中v的元素称为图g的结点, e的元素称为图g的边,图g的结点数目称为它的阶.定义 设，为两个无向图（两个有向图），若存在双射函数,使得 ,当且仅当 (当且仅当)并且与（与）的重数相同，则称和同构，记作,称作到的同构函数.图之间的同构关系构成全体图集合上的特殊二元关系等价关系，事实上，(1) (自反性);(2)若,则 (对称性);(3)若,则 (传递性).在这个等价关系的每一个等价类中的图都是同构的.2.图同构判定及简单应用2.1用同构定义判定图同构由于图包括无向图和有向图,所以可以把图同构的定义重新定义为无向图同构和有向图同构,即1)若无向图和的顶点之间保持一一对应,边之间也保持一一对应,则两图同构.2) 若有向图和的顶点之间保持一一对应,边之间保持一一对应,而且对应点与对应边之间保持相同的关联关系,则两图同构.例1 判定下面两个图，同构. ， 证明 取 , ， , .以上是点的对应，下面是边的对应: 综上所述，为双射函数，根据同构的定义，同构.例2 判定下面两图同构. 证明 取 ： , , , .以上是点的对应，下面是边的对应: 综上所述，g 为双射函数，根据图同构定义，以上两图同构.总之,通过图同构定义，只要找到点与点，边与边之间的一一对应，并且它们之间保持相同的关联关系,就可判定两图同构.但有时为了方便找对应关系，可以先列个图表表示结点间的关联度.如例2,可以通过表1观察到点对应：或，然后再找边对应，就可以判定两图同构.表1 通过图同构定义，了解同构可以用直观扮析方法:把线看作可伸缩的橡皮筋,把点看作固定这些橡皮筋的图钉.如果把一个图的某些“图钉”连同“橡皮筋”取下,钉在平面上的其他位置,得到与另一个图相同的结构和形状,则这两个图一定同构.如上例1,把的结点1移至边（2 , 3）的左下方,再把整个图顺时针旋转90,即得到图.2.2 用邻接矩阵判定图同构定义 设图g=,v=，令为顶点邻接到顶点边的条数，称为g的邻接矩阵，记作,或简记为a. 通过例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知，以上两图同构.例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阶标定图与同构的充要条件是存在的同构变换,使得化成.一般而言,待判定图顶点对应关系是未知的,而同构判定正是要找出这样的对应关系.通过定理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点连通子图相连接的边(不包括的内部边)称为关联边.关联边的边数称为的关联度,记作.定义若无向图g的n点连通子图一共有p个,则将这p个n点连通子图的关联度按从大到小的顺序排列起来所得到的有序集合称为n点连通子图的关联度序列,记为.定理 与同构的充要条件是, 与的n点连通子图的关联度序列分别为与,那么对所有的n都有= ,n=1,2,n-1.这里n是图或的点数.例1(续)证明 , , , .即 . , , , .即 . , , , , .即 . , , , , .即 . , , , .即 . , , , .即 .由于 , ,所以两图同构.用此定理2.3.1的逆否命题判定不同构时比较方便，只要找到一个，即可.例4 判定如下两图同构. 证明 即. 即.即 .,即.即 .即 .虽然 , ，但是即两图不同构.2.4 用出入度序列法判定同构定义在有向图g中,与一个n点连通子图g()相连接的边(不包括g()的内部边)称为关联边.关联边中方向指向这个子图的边称为入边，方向离开这个子图的边称为出边，入边的数目称为g()的入度,记作，出边的数目称为g()的出度，记为.定义 若有向图g的n点连通子图一共有p个,则将这p个n点连通子图的出度按从大到小的顺序排列起来所得到的有序集合称为n点连通子图的出度序列,记为；将这p个n点连通子图的入度按从大到小的顺序排列起来所得到的有序集合称为n点连通子图的入度序列,记为.定理 有向图与同构的充要条件是与的n点连通子图的入度和出度序列分别为，,和,，那么对任一n都有，,这里n是图与的点数.例5 判定如下两图同构. 证明 即 .即 . 即 .即 . 即 .即 .即 .即 . 即 .即. 即. 即.由于所以两图同构.3. 用不变量判定两图不同构对于两图和,我们可以找到一个的特性, 并不具备,则两图不同构，但如果和是同构的应该具有这个特性,这个特性称为不变量,更精确地说,一个特性p是不变量当和是同构图时,如果具有特性p,那么也具有特性p.命题3.1 同构的图具有的顶点数是不变量.命题3.2 同构的图具有的边数是不变量.命题3.3 同构的图具有的顶点度是不变量.命题3.4 同构的图度数相同的结点数是不变量.命题3.5 同构的图边数相同的回路数目是不变量.对于给定的图如果这些不变量有任一不同，则不同构，但是这些不变量相同，也不意味着两图一定同构.例如： （1） （2） （3） （4）如上图，很显然，（1）（2）两图很容易发现顶点数不同，所以不同构，但是（3）（4）两图，不变量都相同，但是不管用哪种判定同构的方法都不能判定两个图同构.事实上，不变量是同构具有的性质，即不变量不同，一定不同构，但同构时一定有不变量成立，可以综述为以上命题为充分不必要条件.判定图同构主要找点与边的双射函数，如果找不到一定可以找到不同的不变量，再判定图同构时可以先试着判定图不同构，这样会方便许多.如不能找到不同的不变量，则利用以上讨论的几种方法判定同构，在n很小时我们可以直观的找到双射函数，随着n的增大，找点与点，边与边之间的对应困难增大，我们可以用邻接矩阵，关联度序列，出入度序列等方法判定.但是随着n的增大,判定图同构的时间复杂度就越大,所以我们仍要继续努力学习,探讨出比较方便快