离散数学第6章.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 图论,（,Graph Theory）,1,1.,图论朔源,2.,图的基本概念,3.,路与圈,4.,图的矩阵表示,5.,带权图的最短路径,6.,Euler,图,7.,Hamilton,图,8.,二分图,9.,平面图,10.,树,2,1.,图论朔源,图论最早处理的问题是哥尼斯堡（,konigsberg,）,城普雷格尔(,pregel,),河上的七桥问题。,问题：在十八世纪的东普鲁士有个哥尼斯堡城（后属于前苏联的立陶宛苏维埃社会主义共和国，其名为加里宁格勒。现属于立陶宛共和国）。哥尼斯堡城位于普雷格尔河畔，河中有两个岛，城市中的各个部分由七座桥相连。,3,问题：从四块陆地的任一块出发，怎样才能做到经过每座桥一次且仅一次，然后回到出发点。,4,1736年，瑞士数学家列昂哈德,.,欧拉(,Leonhard,.,Euler,),发表了他的著名论文“哥尼斯堡七座桥”。在这篇文章中他阐述了解决七桥问题的方法，引出了图论的观点，从而被誉为图论之父，成为图论的创始人。,哥尼斯堡七桥问题归结为：在图2 所示的图中，从,A,B,C,D,任一点出发，通过每条边一次且仅一次而返回出发点的回路是否存在？后人称如此的问题为,Euler,环游。,A,D,C,B,图2,5,欧拉断言这样的回路是不存在的。从图2中的任一结点出发，为了要回到原来的出发点，要求与每个结点相关联的边数均为偶数。这样才能保证从一条边进入某结点后，可从另一条边出去，而不经过已走过的边。从一个结点的不同的两条边一进一出才能回到原出发点。而图2中的,A,B,C,D,全,是与奇数条边相连，由此可知所要求的回路是不可能存在的。,欧拉给出了一个判定准则：若有,Euler,环游，,则,图中每个结点都必须是偶结点(与偶数条边相关联)；若不限定到回原出发点,，则只能有两个奇结点,(与奇数条边相关联)，一个起点，一个终点。,这是图论的第一篇文献。时年欧拉22岁。,注,列昂哈德,.,欧拉,Leonhard,.,Euler （1707-1783）,瑞士数学家.后移居俄罗斯。27岁双目失明，主要靠秘书帮助工作。,6,本世纪40年代的数学游戏：某人挑一担菜、并带一只狗、一只羊，要从河的北岸到南岸。由于船小，只允许带狗、羊、菜三者中的一种过河；当人不在场时狗与羊、羊与菜不能呆在一起。问此人应采取怎样的办法才能将这三样东西安全地带过河去？,方法一：不对称状态空间法,将人(,person)、,狗(,dog)、,羊(,sheep)、,菜(,cabbage),中任意几种在一起的情况看作是一种状态，则北岸可能出现的状态共有十六种，其中安全状态有下面十种：,(人，狗，羊，菜)，(空)；(,P,D,S,C),，,(,),；,(人，狗，羊)，(菜)；(,P,D,S,),，,(C),；,(人，狗，菜)，(羊)；(,P,D,C),，,(,S,),；,7,(人，羊，菜)，(狗)；(,P,S,C),，,(,D,),；,(人，羊)，(狗，菜)；(,P,S),，,(,D,C,),。,不安全的状态有如下六种：,(人)，(狗，羊，菜)；(,P),，,(D,S,C),；,(人，菜)，(狗，羊)；(,P,C),，,(D,S),；,(人，狗)，(羊，菜)；(,P,D),，,(S,C),。,可将十种安全状态表示成十个结点，而渡河的全过程则看作是状态间的转移。这样，上述问题就转化为求一条从(人，狗，羊，菜)或(,P,D,S,C),状态到(空)或,(,),状态的路径。图3中黑色箭头所表示的路径就是其中的一条。,另一条从(,P,D,S,C),到,(,),状态的路径不同的部分由图3中红色箭头所示的路径给出。,8,方法二：对称状态空间法,方法一仅考虑了河北岸的状态，没有考虑河南岸的状态。现在将用字符串表示的两岸状态放入一个二元组中，以表示两岸状态的变化，其前者表示河北岸的状态，后者表示河南岸的状态。其图示见下面图4。它具有对称性是明显的(状态的对称性，图的对称性，路径的对称性)。,(,P,D,S,C),(,),(,P,D,S),(,P,D,C),(,C),(,S),(,D),(,P,S,C),(,P,S),(,D,C),图3,9,注：,上述问题统称“渡河问题”。,“三对忌妒的夫妇渡河问题,”,参见离散数学基础美,C.L.Liu,著 刘振宏译,P162；,“三个传教士与三个吃人肉的野人渡河问题,”,参见,Prolog,高级程序设计美,L.,斯特林,E.,夏皮罗,著 刘家,佺,邓佑译 郑守淇校,P197；,渡河问题的条件也是可变的。比如夫妇的对数可以是四对，五对；渡河能力或渡河工具小船的容量也是可变的。,(,PDC,S),(,PDSC,),(,DC,PS),(,D,PSC,),(,PDS,C),(,C,PDS,),(,PSC,D),(,S,PDC,),(,PS,DC),(,PDSC,),图4,10,2.,图的基本概念,图的定义,图论的概念术语,子,图与补图,结点的度,图的同构,11,定义1.,(图的定义一)图,G=(V,E),是一个系统,，,其中,(1)V,是一个有限集合；,V,中的每一元素,v,V,都称为图,G,的一个结点(,node,vertex),，,V,称为图,G,的结点集；,(2)E,是一个有限集合；,E,中的每一元素,e,E,都称为图,G,的一条边(,edge),；,E,称为图,G,的边集,。,注：,此定义的优点是简单，适应面广；缺点是没有规定清楚点、线之间的关系。,图示：图与画的联系。,例1.,有四个城市,v,1，,v,2，,v,3，,v,4，,其中,v,1,与,v,2,间有公路,e,1,相连，,v,1,与,v,4,间有公路,e,2,相连，,v,2,与,v,3,间有公路,e,3,相连。,上述事实可用图,G=(V,E),表示。图,G,中结点集,V=,v,1,v,2,v,3,v,4，,边集,E=,e,1,e,2,e,3,。,12,定义2.,(图的定义二)图,G=(V,E),是一个系统，其中,(1)V,是一有限集合；,V,中的每一元素,v,V,都称为图,G,的一个结点(,node,vertex)；V,称为图,G,的结点集；,(2)E,V,V,是一有限集合，一个,V,上的关系；,E,中的每一元素(,u,v,),E,都称为图,G,的一条边(,edge)(,这里,u,v,V),；,E,称为图,G,的边集,。,注：,此定义的优点是简单，规定了清楚的点、线之间的关系，很适合简单图、特别是有向图（比如第二章的关系图、哈斯图）；缺点是无法表示平行边，因此不适合多重图（比如上节的七桥图）。,例,2,.,有四个程序，它们之间存在如下的调用关系：,P,1,能调用,P,2,，,P,2,能调用,P,3,，,P,2,能调用,P,4,。,上述事实也可用一图,G=(V,E),来表示。图中结点集,V=,v,1,v,2,v,3,v,4,，边集,E=,(,v,1,v,2,),(,v,2,v,3,),(,v,2,v,4,),。,13,定义3.,(图的定义三)图,G=(V,E),是一个系统，其中,(1)V,是一有限集合；,V,中的每一元素,v,V,都称为图,G,的一个结点(,node,vertex)；V,称为图,G,的结点集；,(2),是一有限集合；,中的每一元素,都称为图,G,中的一个标号,(label)；,称为图,G,的标号集；,(3)E,V,V,是一有限集合，一个三元关系；,E,中的每一元素(,u,v,),E,都称为图,G,的一条边(,edge),或弧(,arc),此边起自,u,而终于,v,；称,u,是此边的起点，称,是此边的标号，称,v,是此边的终点，起点和终点统称为边的端点(这里,u,v,V,),；,E,称为图,G,的边集,。,14,注：,此定义是由美国哈佛大学爱伦堡教授给出的；,此定义规定了严格的点、线之间的关系，适应面很广、特别适合多重图（比如上节的七桥图）；缺点是边表示比较复杂，简单图一般不采用。,标号实际上是为了区别两点间的平行边而设的；标号集的大小一般就是图中平行边的最大条数(图的重数，参见下面概念)。,当图的重数为,1，即图无,平行边时(简单图，参见下面概念)，有,=,1,，各边标号一样，全为,1,，这时可取掉各边标号及,标号集，,定义3就变成了定义2；所以定义3适合于图的一般情况，特别是(有,平行边的),多重图，而,定义2适合于(无,平行边的)简单图。,例3.,七桥图(见图3),按定义3，可用一图,G=(V,E),来表示。,图中结点集,V=,v,1,v,2,v,3,v,4,，,15,图中标号集,=,1,2,，,图中边集,E=,(,v,1,1,v,3,),(,v,1,2,v,3,),(,v,1,1,v,4,),(,v,1,2,v,4,),(,v,1,1,v,2,),(,v,2,1,v,3,),(,v,2,1,v,4,),，,它的图示如图3所示。,图论的基本概念性术语和一些特殊图：,(1)(,n,m),图:,|V|,=n,|E|,=m，,即有,n,个结点和,m,条边的图称,为(,n,m),图。,(2),无向边：,(,undirected edges,简,edges,),在定义3下，,若边(,u,v,)与边(,v,u,)表示同一条边，则称此边为无向边。,v,1,v,4,1,v,3,v,2,1,1,1,1,2,2,图3,16,(3)无向图：,(,undirected graph,简,graph),所有的边都是无向边的图称为无向图。记为,G。,(4)有向边：,(,directed arc,简,arc,或,arrow,),在定义3下，,若边(,u,v,)与边(,v,u,)表示不同的边，,则称此边为有向边。,(5)有向图：,(,directed graph,简,di,graph),所有的边都是有向边的图称为有向图。记为,D。,(6)混和图：,(,mixed graph),既有有,向边又有无向边的图称为混和图。,(7)空图：(,empty graph),V=,(,当然,E=,),，,即没有一个结点的图称为空图。,(8)零图：(,null graph),E=,，,即没有一条边的图称为零图。,17,(9)平凡图：(,trivial graph),|V|,=1，,即只有一个结点的图称为平凡图。,(10)二边相邻：(,adjacent),在图中，若两条边有一公共端点，则称此二边相邻,。,(11)二结点相邻：(,adjacent),若两个结点是同一条边的两个端点，则称此二结 点相邻,。,(12)一结点与一边相关联：(,incident),若一结点是一边的一个端点，则称此结点与该 边相 关联。,(13)孤立点：(,isolated vertex),不与任何边相关联的结点称为孤立点。,(14)自环：(,loop),两个端点相同的边称为自环。,18,(15)平行边：(,parallel edges),有相同端点(相同的起点，相同的终点)的两条边称为平行边。,(16)重数：(,multiplicity),两结点间平行边的条数称为平行边的重数。,(17)多重图：(,multiply graph),具有平行边的图称为多重图；多重图的重数是图中平行边重数的最大者,。,(18)简单图：(单图、单纯图(,simple graph),无平行边、无自环的图称为简单图。,(19)图的阶：(,order),图中结点的个数,|V|,称为图的阶。,19,(20)完全图：(,complete graph),每一对不同的结点间都有一条边的简单图称为完全图。,n,个结点,m,条边的无向完全图：,n,个结点,m,条边的有向完全图：,m=n(n-1),n,个结点的无向完全图记为：,K,n,图8.,K,5,图9,20,定义,4,.,(图的定义四),图,G=(V,E,),是一个系统，其中,(1)V,是一有限集合；,V,中的每一元素,v,V,都称为图,G,的一个结点(,node,vertex)；V,称为图,G,的结点集；,(2)E,是一个有限集合；,E,中的每一元素,e,E,都称为图,G,的一条边(,edge),；,E,称为图,G,的边集,。,(3),是边到结点集的一个关联函数，即,:,E2,V,(,无向图)或,:,E,V,V(,有向图)。,将,E,中的每条边,e,E,与结点集,V,中的一个二元子集,u,v,2,V,(或,u,v,V,)相关联或与结点集,V,上的一个二元组(,u,v,),V,V,相关联，即,(,e,)=,u,v,(,无向图),或,(,e,)=,(,u,v,),(,有向图),，称,u,是此边的起点，称,v,是此边的终点，结点,u,和,v,统称为边的端点。,21,注：,此定义是对美国库曼教授所给定义的一个修正；,此定义的优点是适应面较广，尤其是将边看作是和结点同样的独立的研究对象，边不再是由结点表示的一个附属对象，用函数概念规定了点、线之间的严格关联关系，这样一来，就便于边概念的进一步推广（比如引出超图概念）；缺点是关联函数表示比较烦琐，简单图一般不采用。,例4.,七桥图(见图10),按定义4，,可用一图,G=(V,E,),来表示。,图中结点集,V=,v,1,v,2,v,3,v,4,，,图中边集,E,=,e,1,e,2,e,3,e,4,e,5,e,6,e,7,，,图中,关联函数,:,E2,V,使,(,e,1,)=,v,1,v,3,(,e,2,)=,v,1,v,3,(,e,3,)=,v,1,v,2,(,e,4,)=,v,1,v,4,(,e,5,)=,v,1,v,4,(,e,6,)=,v,2,v,3,(,e,7,)=,v,2,v,4,。,v,1,v,4,e,6,v,3,v,2,e,3,e,7,e,1,e,5,e,4,e,2,图10,22,定义5.,子图(,subgraph,),设,G=(V,E),和,G,=(V,E,),是两个(有向的或无向的,),图。,(1)若,V,V,且,E,E，,则称,G,为,G,的子图；,(2)若,V,V,且,E,E，,则称,G,为,G,的真子图(,proper-)；,(3)若,V,=,V,且,E,E，,则称,G,为,G,的生成子图(,spanning-)；,(4)当,V,=,V,且,E,=,E，,或,V,=,V,且,E,=,时，称,G,为,G,的平凡子图(,trivial-)；,即，图,G,本身和,G,的零图是,G,的平凡子图。,例5.,图,G,及其子图、,生成子图、,真子图、平凡子图。,G,图1,1,23,定义6.,商图(,quotient graph),设,G=(V,E),是一(有向的或无向的)图，,R,V,V,是一结点集,V,上的等价关系。,那么，定义图,G,关于等价关系,R,的商图为简单图,G,R,=(V,R,E,R,),其中：,V,R,=V/R=,v,R,v,V,是,V,关于等价关系,R,的商集；,E,R,=(,u,R,v,R,),u,R,V,R,v,R,V,R,(,u,u,R,)(,v,v,R,),(,(,u,v,),E),。,例6.,在图12中，图,G,如(1)图所示；,其关于等价关系,R,1,(,以划分,v,1,v,5,v,9,v,2,v,6,v,10,v,3,v,7,v,11,v,4,v,8,v,12,给出)的商图,G,R1,如(2)图所示；,关于等价关系,R,2,(,以划分,v,1,v,5,v,2,v,3,v,6,v,4,v,7,v,8,v,9,v,10,v,11,v,12,给出)的商图,G,R2,如(3)图所示；,24,关于等价关系,R,3,(,以划分,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,v,10,v,1,v,12,给出)的,商图,G,R3,如(4)图所,示(称为由一条边,e,=(,v,9,v,10,),所导出的,商图，记为,G,e,)；,(2).G,R1,v,1,R1,v,2,R1,v,4,R1,v,3,R1,(3).G,R2,v,1,R2,v,2,R2,v,9,R2,v,8,R2,v,4,R2,v,7,R2,(1).G,v,1,v,2,v,3,v,4,v,5,v,6,v,8,v,7,v,9,v,10,v,12,v,11,(4).G,e,v,1,v,2,v,3,v,4,v,5,v,6,v,8,v,7,v,9,v,12,v,11,图12,25,定义7.,补图(,complement graph),设,G=(V,E),为一简单图，,G,*,=(V,E,*,),是与图,G,相应的完全图。定义图,G,的补图,=(V,),，其中：,=,E,*,E。,例7.,图,G,及其相应的完全图、补图,分别如下图13所示：,G,图13,26,(21)结点的出度：(,out-degree),有向图中以结点,v,为起点的有向边的条数称为结点,v,的出度。记为 。,(22)结点的进度：(入度(,in-degree),有向图中以结点,v,为终点的有向边的条数称为结点,v,的进度。记为 。,(23)结点的度：(,degree),图中与结点,v,关联的边的条数称为结点,v,的度。记为,deg(,v,)。,(24)奇结点：(,odd vertex),度数为奇数的结点称为奇结点,。,(25)偶结点：(,even vertex),度数为偶数的结点称为偶结点,。,27,(26)图,G,的最小度：(,minimal degree),图,G,中各结点度数的最小者。记为,(,G,),。,(27)图,G,的最大度：(,maximum degree),图,G,中各结点度数的最大者。记为,(,G,),。,(28)正则图：(,regular graph),若图,G,中各结点的度数都相等，则称图,G,是正则图,。,显然，这时,(,G,)=(,G,)。,(29),k,-,正则的：(,k,-,regular),若图,G,中各结点的度数都相等，且为,k,，则称图,G,是,k,-,正则的，或,k,度正则的,。,显然，这时,(,G,)=(,G,)=,k,。,28,(30)悬挂点：(,hang vertex),度数为1的结点称为悬挂点,。,(31)悬挂边：(,hang edge),与悬挂点关联的边称为悬挂边,。,例8.,在右面的有向图中，其中：,=3,=4,deg(,v,1,)=7,；,=2,=2,deg(,v,2,)=4,；,=3,=1,deg(,v,3,)=4,；,=1,=1,deg(,v,4,)=2,；,=0,=0,deg(,v,5,)=0,；,=0,=1,deg(,v,6,)=1,；,29,奇结点：,v,1,v,6,；,偶结点：,v,2,v,3,v,4,v,5,；,悬挂点：,v,6,；,悬挂边：(,v,2,v,6,)。,有如下结论：,(,1),所有结点的度数之和等于边数的二倍；,7+4+4+2+0+1=2,9,(,2),所有结点的进度之和等于出度之和等于边数；,4+2+1+1+0+1=3+2+3+1+0+0=,9,(,3),所有奇结点的度数之和是偶数；,7+1=8。,30,例9.,在下面的无向图中，其中：,deg(,v,1,)=5,deg(,v,2,)=3,deg(,v,3,)=3,deg(,v,4,)=2,deg(,v,5,)=0,deg(,v,6,)=1,；,奇结点：,v,1,v,2,v,3,v,6,；,偶结点：,v,4,v,5,；,悬挂点：,v,6,；,悬挂边：(,v,2,v,6,)。,并且有如下结论：,(,1),所有结点的度数之和等于边数的二倍；,5+3+3+2+0+1=2,7,(,2),所有奇结点的度数之和是偶数；,5+3+3+1=12。,v,1,v,2,v,3,v,4,v,5,v,6,图15,31,定理1.,设,G=(V,E),是(,n,m),图，则,(1)无向图,G,中，所有结点的度之和等于边数的二倍；即,dev(v,i,)=2m 。,(,2),有向图,G,中，所有结点的进度之和等于出度之和等于边数；即,。,证,.,(采用数钱法),(1)因为无向图,G,中的每条无向边都与两个结点相关联，所以每条边都能给,G,中结点的度数贡献2，因而,G,中所有的,m,条边能给,G,中结点的度数总计贡献2,m,，故,G,中所有结点的度数之和为2,m，,即,dev(v,i,)=2m,。,32,(2)对于有向图,G,，每条有向边都与一个终点和一个,起点相关联，因此每条有向边都能给,G,中结点的进度贡献1，给出度贡献1，因而,G,中所有的,m,条边能给,G,中结点的进度总计贡献,m，,给出度总计贡献,m，,故,G,中所有结点的进度之和等于出度之和等于边数,m,，,即,。,定理2.,任何图中所有奇结点的度数之和是偶数。,证,.,设图中共有,n,个结点；其中奇结点的个数为,n,1,，并且不妨设奇结点为,u,1,u,2,u,n1,；偶结点的个数为,n,2,(当然有,n,1,+,n,2,=,n),，并且不妨设偶结点为,w,1,w,2,w,n2,，,其对应的度数为2,k,1,2,k,2,2,k,n2,；于是有奇结点度数之和,33,=2,m-(,2,k,1,+,2,k,2,+,+2,k,n2,),(定理1),=2,m-(,k,1,+,k,2,+,+,k,n2,),是偶数。,推论1.,(握手引理,),在一次集会上和奇数个人握过手的人的数目是偶数。,证,.,用结点表示人，用边表示两人相互握过手，从而便可得到一个图。这个图表达了参加集会的人之间彼此握手打招呼的情况。于是直接应用定理2，即可知推论的结论成立。,34,u,1,u,2,u,3,u,4,(a),v,1,v,2,v,3,v,4,(b),w,1,w,2,w,3,w,4,(c),x,1,x,2,x,3,x,4,(d),图16,v,1,v,2,v,3,v,4,(b),图17,u,1,u,2,u,3,u,4,(a),35,定义8.,图的同构(,isomorphism of graphs),(1)称,G=(V,E),及,G,=(V,E,),二图同构，记为,G,G,存在 着两个双射函数,及,，,:,V,V,，,:,E,E,，使得,(,u,v,)=,(,u,v,),(,u,)=,u,(,v,)=,v,(*),(2),称,G=(V,E,),及,G,=(V,E,),二图同构，记为,G,G,存在着两个双射函数,及,，,:,V,V,，,:,E,E,，使得,(,e,)=,e,(,e,)=,u,v,(,e,)=,u,v,(,u,)=,u,(,v,)=,v,或,(,e,)=,e,(,e,)=,(,u,v,),(,e,)=,(,u,v,),(,u,)=,u,(,v,)=,v,u,v,u,v,u,v,u,v,(1),e,(2),e,图18,36,注：,此定义,(1),中(*)式也可改写为：,(,u,v,)=,(,(,u,),(,v,),(*),此定义,(2),中(*)式也可改写为：,(,e,)=,u,v,(,(,e,)=,(,u,),(,v,),或,(,e,)=,(,u,v,),(,(,e,)=,(,(,u,),(,v,),这实际上就是,图的同态公式,；,图的同构远比代数系统的同构复杂,。这是因为,图的同构在同态公式中牵扯着两个(甚至三个,考虑定义三)双射函数的交叉关系，而代数系统的同构在同态公式中只有一个双射函数。因此图的同构问题不象代数系统的同构问题那样有许多进展、有几个定理好用，迄今为止，没有任何进展，没有任何定理可用，仅仅只能用定义；,37,例10.,图19中的(,a),和(,b),二无向图是同构的。,(采用变形法,),其同构函数为,及,，使得,(,u,1,)=,v,1,(,u,2,)=,v,2,(,u,3,)=,v,3,(,u,4,)=,v,4,；,(,u,1,u,2,)=,(,v,1,v,2,),(,u,1,u,3,)=,(,v,1,v,3,),(,u,1,u,4,)=,(,v,1,v,4,),(,u,2,u,3,)=,(,v,2,v,3,),(,u,2,u,4,)=,(,v,1,v,2,),(,u,3,u,4,)=,(,v,3,v,4,)；,从而,及,是,两个双射函数，且满足同态公式(*)，因此(,a),和(,b),二图是同构的。,v,1,v,2,v,3,v,4,(b),图19,u,1,u,2,u,3,u,4,(a),38,例11.,图20中的(,a),和(,b),二无向图是同构的。,(采用抻路蹦圈法,),其同构函数为,及,，使得,(,v,1,)=,a,(,v,2,)=,c,(,v,3,)=,e,(,v,4,)=,b,(,v,5,)=,d,；,(,v,1,v,3,)=,(,a,e,),(,v,1,v,4,)=,(,a,b,),(,v,2,v,4,)=,(,c,b,),(,v,2,v,5,)=,(,c,d,),(,v,3,v,5,)=,(,e,d,),；,从而,及,是,两个双射函数，且满足同态公式(*)，因此(,a),和(,b),二图是同构的。,图20,(,a),v,1,v,2,v,4,v,3,v,5,(,b),e,d,c,b,a,39,两个图能否同构，从直观的意义上讲是能否将其中的一个图示通过某些“变形”后使它成为另一个图示的形状。在上面的例子中，将(,a),图示作如下变形蹦圈后就可得到(,b),图示：,(,d),v,3,v,5,v,2,v,4,v,1,(,c),v,1,v,2,v,4,v,3,v,5,v,2,v,5,翻转,旋转,图21,40,例12.,图22中的(,a),和(,b),二无向图是同构的。,v,1,v,2,v,3,v,4,v,5,v,6,(b),u,1,u,2,u,3,u,5,u,4,u,6,u,2,下翻,u,2,上翻,(a),图22,u,1,u,2,u,3,u,5,u,4,u,6,(c),41,(采用抻路蹦圈法,),其同构函数为,及,，使得,(,u,1,)=,v,1,(,u,2,)=,v,5,(,u,3,)=,v,3,(,u,4,)=,v,6,(,u,5,)=,v,2,(,u,6,)=,v,4,；,(,u,1,u,4,)=,(,v,1,v,6,),(,u,1,u,5,)=,(,v,1,v,2,),(,u,1,u,6,)=,(,v,1,v,4,),(,u,2,u,4,)=,(,v,5,v,6,),(,u,2,u,5,)=,(,v,5,v,2,),(,u,2,u,6,)=,(,v,5,v,4,),(,u,3,u,4,)=,(,v,3,v,6,),(,u,3,u,5,)=,(,v,3,v,2,),(,u,3,u,6,)=,(,v,3,v,4,),；,从而,及,是,两个双射函数，且满足同态公式(*)，因此(,a),和(,b),二图是同构的。,42,例13.,图23中的(,a),和(,b),二有向图是同构的。,(采用抻路蹦圈法,),其同构函数为,及,，使得,(,u,1,)=,v,1,(,u,2,)=,v,2,(,u,3,)=,v,4,(,u,4,)=,v,3,；,(,u,1,u,2,)=,(,v,1,v,2,),(,u,1,u,4,)=,(,v,1,v,3,),(,u,2,u,3,)=,(,v,2,v,4,),(,u,4,u,3,)=,(,v,3,v,4,),；,从而,及,是,两个双射函数，且满足同态公式(*)，因此(,a),和(,b),二图是同构的。,u,1,u,4,u,2,u,3,(a),图23,v,1,v,2,v,4,v,3,(b),v,3,v,4,翻转,43,若两个图同构，则它们必须满足：,(1)结点个数相等；,(2),边数相等；,(3),对应结点的进度、出度、度数均相等；,(4),度数相同的结点个数相等；,(5),平行边对应，重数相等；,(6),自环对应；悬挂点对应；孤立点对应；,(7),结点间的相邻关系对应；边间的相邻关系对应；结点与边的关联关系对应；,(8),圈对应；路对应；,(9),对应圈的长度相等；对应路的长度相等；,44,例14.,图24中(,a)、(b,),两图不同构。,u,1,u,2,u,3,(a),v,1,v,2,(b),图,24,45,Ulam,猜想,(1960),.,1960年,Ulam,提出如下关于图同构的著名猜想，至今无人能够证明或否定。,设,G=(V,E),及,G,=(V,E,),是两个图，其结点集分别为,V=,v,1,v,2,v,n,及,V,=,v,1,v,2,v,n,(n,3),，则,(,iN)(1in)(H,i,H,i,)(,G,G,),，,即,若,G,和,G,的,n,对,特殊真子图对应同构，则,G,和,G,同构,。,这里：,H,i,=G,v,i,=(,V,i,E,i,),V,i,=V,v,i,E,i,=(,u,v,),(,u,v,),E,u,v,i,v,v,i,；,H,i,=G,v,i,=(,V,i,E,i,),V,i,=V,v,i,E,i,=(,u,v,),(,u,v,),E,u,v,i,v,v,i,。,46,3.,路与圈,定义与实例,基本概念,可达性,图的连通性,47,3.,路与圈,定义,1.,途径(,way),设,G=(V,E,),是,一图。,G,的有限非空点边交错序列,w,=,v,0,e,1,v,1,e,2,v,2,e,k,v,k,若满足条件:,(1),(,e,i,)=,v,i-1,v,i,(,或(,v,i-1,v,i,)(1ik),(2)当,e,i,和,e,i+1,不是自环时，有,e,i+1,e,i,(1in)(,无向图),，则称其为,G,的一条从,v,0,到,v,k,的途径。,v,0,称为途径,w,的起点，,v,k,称为途径,w,的终点，,k,称为途径,w,的长度。,注：,当,G=(V,E),是,一简单图时,，,在实际应用中,，,常用纯边列或纯点列的方式表示途径,：,(1),w,=(,e,1,e,2,e,k,)；,(2),w,=(,v,0,v,1,),(,v,1,v,2,),(,v,k-1,v,k,)；,(3),w,=(,v,0,v,1,v,2,v,k-1,v,k,)。,48,途径,w,实际上是一个动态的过程；其在图,G,上的静态轨迹是,图,G,的一个子图,G(,w,)=(,V(,w,),E(,w,),(,w,),)，,其中,：,V(,w,)=,v,0,v,1,v,2,v,k,(,去掉重复,),E(,w,)=,e,1,e,2,e,k,(,去掉重复,),(,w,),:,E(,w,),2,V(,w,),(,无向图,)或,:,E,(,w,),V(,w,),V(,w,)(,有向图,),使得,(,w,)(,e,i,)=,v,i-1,v,i,(,或,(,v,i-1,v,i,)(1in),(,去掉重复,),。,途径定义,1,中条件(1)、,(2),的情况如下图1所示,：,v,i-1,(,v,i+1,),v,i,(b),e,i+1,e,i,不满足途径定义,1,中条件,(2),的情况,图1,v,0,(a),v,1,v,2,v,k-2,v,k-1,v,k,e,k,e,k-1,e,2,e,1,途径,w,49,定义,2.,路,(,path)、,圈,(,cycle),设,G=(V,E),是,一图，,w,=(,v,0,v,1,v,2,v,k-1,v,k,)是一,途径。,(1),若,v,0,v,k,，则称此途径,w,是从,v,0,到,v,k,的一条路；记为,P=(,v,0,v,1,v,2,v,k-1,v,k,)，并,称,k,为路,P,的长度,(,即,|P|,=k)。,(2),若,v,0,=,v,k,，则称此途径,w,是一个圈；记为,C=(,v,0,v,1,v,2,v,k-1,v,k,)，并,称,k,为圈,C,的长度,(,即,|C|,=k)。,定义3,.,可达性(,reachablility,)、,连通性(,connectivity),设,G=(V,E),是,一无向图，,u,v,V,(1),若,存在着,从结点,u,到结点,v,的,一条路,P,，,则称从结点,u,到结点,v,是,可达的,；,(2),若图,G,中任何两结点都是,可达的,，则称此图,G,是,连通的,。否则，称图,G,是非,连通的。,50,注一：,可达概念可以看作结点间的一个二元关系可达关系；,在无向图中,，,规定任一结点自己到自己总是可达的,，,即可,达关系具有自反性,；,在无向图中,，,可达性是相互的，从结点,u,可达结点,v,，,则从,结点,v,也可达结点,u,，即可达关系是对称的,；,可达关系是传递的,，,即若从结点,u,可达结点,v，,又从结点,v,可,达结点,w,，,则从结点,u,也可达结点,w,；,一般地,，,当从结点,u,可达结点,v,时,，,它们之间不一定只有一,条路,，,可能会有若干条路,。,称从结点,u,到结点,v,的所有,路中长度最短的那一条为短程线,，,并将短程线的长度叫做,从结点,u,到结点,v,的距离,，,用,d,(,u,v,),表示,。,规定,：,(1),d,(,u,u,)=0,；,(2),若结点,u,到结点,v,不可达,，,则,d,(,u,v,)=,。,短程线不一定是唯一的,有时可能会有好几条；,按照通常的理解，距离概念一般都具有下列性质,：,51,(1),非负性,：,d,(,u,v,),0,；,(2),对称性,；,d,(,u,v,)=,d,(,v,u,),；,(3),三角不等式,：,d,(,u,v,)+,d,(,v,w,),d,(,u,w,),对无向图，上述性质全成立,；,对有向图来说，第二条，对称性质不成立,。,注二：,连通性是有强弱之分的；,(1)若图,G,中任二结点间都至少存在着一条路可达，则称图,G,是1-连通的；,(2)若图,G,中任二结点间都至少存在着,k,条不同的路可达，则,称图,G,是,k-,连通的(,k,2)；,通常所说的连通性实际上是指1-连通,。,1-连通的,连通,性,较差,，,重要的信道图网络，比如军事信道图网络，其,连,通性至少在,2,-,连通以上,。,52,例1.,在图2中由结点,v,1,到结点,v,3,的路有：,P,1,=,(,v,1,v,2,v,3,),P,2,=,(,v,1,v,4,v,3,),P,3,=,(,v,1,v,2,v,4,v,3,),P,4,=,(,v,1,v,2,v,4,v,1,v,2,v,3,),P,5,=,(,v,1,v,2,v,4,v,1,v,4,v,3,),P,6,=,(,v,1,v,1,v,2,v,3,),在图2中，由结点,v,1,到,v,1,的圈有：,C,1,=(,v,1,v,1,),C,2,=(,v,1,v,2,v,1,),C,3,=(,v,1,v,2,v,3,v,1,),C,4,=(,v,1,v,4,v,3,v,1,),C,5,=(,v,1,v,2,v,3,v,2,v,1,),C,6,=(,v,1,v,2,v,3,v,2,v,3,v,1,),v,1,v,2,v,3,v,4,图2,53,例2.,路的概念可以用来描述很多东西，如：,(1)在,Pascal,语言中，一个复合语句以,BEGIN,开始，,END,结束，其中若干个语句用分号隔开。所以，执行一个,Pascal,语言中的一条复合语句，可以认为是从图3(,a),中的,BEGIN,开始到,END,结束走完一条路。,(2),Pascal,语言中的“标识符”可以认为是图3(,b),中从“入口”到“出口”的一条路。,(3)一个二进制数可以认为是图3(,c),中从“入口”到“出口”的一条路。,字母,数字,入口,出口,(,b),1,0,入口,出口,(,c),图3,说明,BEGIN,；,语句,END,(a),；,54,注：,实际上，分程序是如下的点列,：,而不是边列,。,各种程序设计语言的文法都可用图来表示,，,而且比通常所用的,Backus,元语言表示的更好、更直观,。,定义4.,简单路(,simple path),简单圈(,simple cycle),无重复边的路称为简单路；,无重复边的圈称为简单圈。,定义5.,初级路(,elementary path),初级圈(,elementary cycle),无重复点的路称为初级路；,无重复点的圈称为初级圈。,说明,BEGIN,；,语句,END,语句,语句,；,；,；,；,；,；,；,说明,说明,55,例4.,在图4中由结点,v,