第3章同构图精选文档.ppt

《第3章同构图精选文档.ppt》由会员分享，可在线阅读，更多相关《第3章同构图精选文档.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章同构章同构图本讲稿第一页，共二十一页 主要内容3.1 同构的定义3.2 同构关系3.4 延伸阅读:重构与可解性本讲稿第二页，共二十一页 3.1 同构的定义回顾:两个图G和H称为相同的,若V(G)=V(H)且E(G)=E(H).两个图G和H是“同构的”,若它们有相同的结构，并记之为GH.换句话说：定义定义1 如果G和H的顶点可以通过标号(或重新标号)而形成两个相同的图,那么GH.本讲稿第三页，共二十一页 3.1 同构的定义更精确的描述:定义定义2 若两个图仅仅区别在画法与(或顶点)的标号方式上,则称它们为同构的.正式地说:定义定义3 两个(标号)图G1和G2称为同构的同构的(isomor

2、phic)(或者,有相同结构),如果存在一个从V(G1)到V(G2)的一一对应 ,使得：当且仅当 .此时,称为是从G1到G2的一个同构(isomorphism).本讲稿第四页，共二十一页 3.1 同构的定义举个例子加深理解:图 3.1 阶和边数均为 5 的图H1H2H3本讲稿第五页，共二十一页 3.1 同构的定义通过重新放置H2的顶点,H2可以被重新画为图3.2中的H2.类似地,H3也可以被重画为图3.2中的H3.图 3.2 一个阶和边数均为 5 的图H1H2H3本讲稿第六页，共二十一页 3.1 同构的定义从图3.2中 H2 的画法中可以看出,如下定义的映射 ：V(H1)V(H2),是一个同构

3、.因此 H1 H2.从上述例子中我们可以看出,同构的图之间必须满足的条件是:有相同的阶和想同的边数.但这只是个必要条件,并不充分.也就是说,即使两个图有相同的阶和相同的边数,这也不能确保它们是同构的.本讲稿第七页，共二十一页 3.1 同构的定义以下举一个例子说明:有相同的阶且有相同的边数,但并不同构的两个图.如图3.6 所示.G1G2图3.6 两个非同构图本讲稿第八页，共二十一页 3.1 同构的定义重述同构的定义:定义定义4 两个图G1和G2是同构的,如果存在从V(G1)到V(G2)的一个一一对应 使得G1中的每对邻接顶点映射到G2中邻接的顶点,且G1中的每对不邻接顶点映射到G2中不邻接的顶点

4、.具有这些性质的映射 是一个同构.本讲稿第九页，共二十一页 3.1 同构的定义 定理定理 3.1 两个图G1和G2是同构的当且仅当它们的补图 和 是同构的.(同构的充分必要条件)注意到,所以同一映射 ：也把 中邻接的顶点映射到 中邻接的顶点,中不邻接的顶点映射到 中不邻接的顶点.本讲稿第十页，共二十一页 3.1 同构的定义看一个例子:H1H2图3.7 图 H1 和 H2注:用两种方法判断图H1和H2是否同构.本讲稿第十一页，共二十一页 3.1 同构的定义 定理定理 3.2 如果图G和H是同构图,则它们对应的顶点有相同的度.证 直接证法 因为G和H是同构的,所以存在一个同构 ：.设u是G中的一个

5、顶点且 其中v是H中的顶点.我们来证明H中v的度等于G中u的度.(1)首先假设 degGu=0,则G中没有与u邻接的顶点.假设 y是H中除v之外的任一顶点,则G中存在一个顶点x使得 因为x和u是G中不邻接的顶点(因为degGu=0),故y和v是H中不邻接的顶点.所以,H中不含与v邻接的顶点,即degHv=0.本讲稿第十二页，共二十一页 3.1 同构的定义 下面假设degGu=k 1.设 N(u)=x1,x1,xk 是G中与顶点u邻接的顶点集合,其中 因为u和 xi(1i k)是邻接的,所以v和 yi(1i k)是邻接的(定义4).若y是H中的一个顶点,满足 则在G中存在顶点x使得 其中 因为x

6、和u在G中是不邻接的,所以y和v在H中是不邻接的(定义4).因此degHv=k.(证毕)本讲稿第十三页，共二十一页 3.1 同构的定义 定理定理 3.5 设G和H为同构图,则 (a)G是二部的当且仅当H是二部的,(b)G是连通的当且仅当H是连通的.注:该定理更多地当作同构的性质来用.更一般地,G所具有的任何结构性质也应该被H所具有.本讲稿第十四页，共二十一页 3.2 同构关系 什么是“双射”？既是单射又是满射的映射称为双射，亦称“一一映射”.(1)设 f 是从集合A到集合B的映射,若 R(f)=B,即B中任一元素b都是 A中某元素的像,则称f为A到B上的满射满射；(2)若对A中任意两个不同元素

7、a1不等于a2,他们的像 f(a1)不等f(a2),则称 f 为A到B的单射单射；(3)若映射 f 既是单射,又是满射,则称映射 f 为 A 到 B 的“双射”(或“一一映射”).函数为双射当且仅当每个可能的像有且仅有一个变量与之对应.本讲稿第十五页，共二十一页 3.2 同构关系 定理定理 3.6 在图的集合上,同构是一种等价关系.(自反的、对称的、传递的)同构的等价关系的证明依赖于双射的三个基本性质:1)每一个恒等映射是双射;2)每一个双射有一个逆映射,并且该逆映射也是一个双射;3)两个双射的复合是一个双射.注:定理3.5的证明过程见书本 P56.本讲稿第十六页，共二十一页 3.4 重构与可

8、解性首先看一个例子:12345图3.35 由五张卡片组成的一副纸牌本讲稿第十七页，共二十一页 3.4 重构与可解性可以证明,存在某个n阶图G,使得对每个 非标号子图G-v (G-v 为非平凡图G的子图,其顶点为G除去v之外的所有顶点,其边为G除去v相关联的边之外的所有边)就画在图3.35中纸牌的某一张卡片上.其中n=5.(两种解释)定义定义5 如果图G的某个参数值或某个性质可以由(非标号)图G-v()所确定,则对于图G而言,这个参数或这个性质称为是可识别的.定理定理 3.11 每个图的阶都是可识别的.本讲稿第十八页，共二十一页 3.4 重构与可解性 定理定理 3.12 每个阶至少为 3 的图的

9、边数是可识别的.证证 直接证法 设G是一个阶为 n 3 且边数为 m 的图.设V(G)=v1,v2,vn.在由子图G-vi(1 i n)组成的纸牌中,所有顶点都没有标号.设e是G的一条边,例如e=v1v2.那么边e将出现在每个子图 G-vi(3 i n)中,但是不出现在G-v1 或 G-v2 中.设G-vi 的边数为mi(1 i n),则在和式 中,每一条边被计数了 n-2 次,即 本讲稿第十九页，共二十一页 3.4 重构与可解性定理定理 3.13 每个阶至少为 3 的图G 的度序列都是可识别的.定义定义6 一个阶为n 2的图G 称为是可重构的,如果G可由它的子图 G-vi(1 i n)唯一确定(在同构的意义下).重构猜想重构猜想 阶至少为 3 的每个图都是可重构的.定理定理 3.14 对所有阶至少为 3 的图,连通性和非连通性都是 可识别的性质.(由定理 1.10(P15)可得证.)本讲稿第二十页，共二十一页Thank you!本讲稿第二十一页，共二十一页