离散数学第8章图论课件

*,主要内容如下,8.1,基本概念,8.6,有向树,8.2,图的矩阵表示,8.7,二部图,8.4,欧拉图和哈密尔顿图,8.8,平面图,8.5,树,8.9,有向图,第,8,章 图论,在第,2,章讨论关系时，曾引进过图的一些概念。在那里，图只是作为表达集合上二元关系的一种工具。在这一章介绍图的基本概念、基本性质以及几种在实际应用中有重要意义的特殊图。鉴于学时有限，只介绍最基本的内容。,8.1,基本概念,一、图的定义及其表示,（,1,）,V=v,1,，,v,2,，,，,v,n,是一个有限非空的集合，,V,中的元素称为,G,的,结点（或顶点）,，,V,称为图,G,的,结点集,，记作,V,（,G,）；,（,2,）,E,是,V,中,不同,元素的,非有序,对偶的集合，,E,中的元素称为,G,的,边（或弧）,，,E,称为图,G,的,边集,，记作,E,（,G,）。,一个图,G,是一个有序二元组（,V,，,E,），其中：,1.,图的定义,(1),图解表示法,(2),矩阵表示法：,8.2,节,例,2,下图,(,a).(b,),分别给出了例,1,中图,G,的图解表示。,例,1,设,V=v,1,，,v,2,，,v,3,，,v,4,，,v,5,E=,2.,图的表示方法,则,G=,（,V,，,E,）,是一个图。,二,.,有关概念,1,（,n,，,m,）图,:,（,n,，,0,）图；（,1,，,0,）图；,定义,8-2,在图,G,中，如果任意两个不同的结点都是邻接的，则称图,G,是,完全图,。,n,个结点的完全图记作,K,n,例,3,K,1,K,2,K,3,K,4,K,5,2,两结点是,邻接的；,3,边和结点是,关联的；,4,孤立点；,5,两条边是,邻接的；,6,孤立边；,零图,平凡图,定义,8-3,图,G,的,补图,是由,G,的所有结点和为了使,G,成为完全图所需添加的那些边组成的图，用 表示。,例,4,下,图中（,b,）所表示的图是（,a,）图的补图。,注意：在,K,n,中，边的数目为：,n(n-1)/2,三、关于图的基本术语,1,、伪图：设图,G,（,V,，,E,），,V,是一个有限非空集合，,E,是,V,中,任意元素,的,非有序,对偶的,多重集,，则称,G,是一个,伪图,。,多重集,：元素可重复出现，且不要求,E,中元素,v,i,v,j,满足,v,i,v,j,这样若,v,i,V,，则有可能,v,i,v,i,E,，称这样的边为,自环,。例：,V,1,V,2,V,3,V,4,V,3,V,1,V,2,V,4,2,、多重图：没有自环的伪图称为,多重图,。,3,、边的重数：连接于同一对结点间的边的数目称为边的,重数,。,4,、简单图：没有自环且没有重数大于,1,的边的图，称为,简单图,。,定义,8-4,：,若图,G,的所有结点都具有相同的度数,d,，则称图,G,为,d,次正则图,。,例如：,G,G,是,3,次正则图,四、,结点的度和正则图,图,G,中关联结点,v,i,的边的总数称为结点,v,i,的,度,，用,deg(v,i,),表示。,握手定理,设图,G,具有结点集,v,1,，,v,2,，,，,v,n,和,m,条边，则,G,中所有结点的度之和 。,例如,右图中所有结点的度之和,刚好是边数,7,的两倍。,推论,任何图,G,中，度为奇数的结点个数为偶数。,证明,设图,G,中，奇数度结点集为,V,1,，偶数度结点,集为,V,2,，边数为,m,，,则,于是,因为 和,2m,均为偶数，所以,也必为偶数。由于当,v,V,1,时，,deg(v,),均为奇数，因此,#V,1,必为偶数。,五、图的同构,定义,8-5,设,G,和,G,是分别具有结点集,V,和,V,的两个图，若存在一个双射,h,：,V,V,，使得当且仅当,v,i,，,v,j,是,G,的边时，,h(v,i,),，,h(v,j,),是,G,的边，则称图,G,与,G,同构。,两个图同构的必要条件是：,（,1,）它们有相同的结点数和相同的边数；,（,2,）对应结点的度数相同。,例,4,判断下面的两个图是否同构？,V,3,V,1,V,2,V,6,V,5,V,4,U,6,U,1,U,2,U,3,U,4,U,5,六、子图,利用子集的概念可定义图,G,的子图。,定义,8-6,设有图,G,1,=,（,V,1,，,E,1,）和图,G,2,=,（,V,2,，,E,2,）,（,1,）若,V,2,V,1,，,E,2,E,1,，则称,G,2,是,G,1,的,子图,，,记作,G,2,G,1,；,。,非真生成,真生成,真非生成,非真非生成,真非生成,（,2,）若,V,2,V,1,，,E,2,E,1,，则称,G,2,是,G,1,的,真子图,；,（,3,）若,V,2,=V,1,，,E,2,E,1,，则称,G,2,是,G,1,的,生成子图,.,七、路与回路,定义,:,图,G,中,l,条边的序列,v,0,，,v,1,v,1,，,v,2,v,l,1,，,v,l,称为连,接,v,0,到,v,l,的一条长为,l,的,路,。它常简单地用结点的序列,v,0,v,1,v,2,v,l,1,v,l,来表示。其中,v,0,和,v,l,分别称为这条路的起点和终点。,开路,：若,v,0,v,l,，则称路,v,0,v,1,v,2,v,l,1,v,l,为,开路,；,回路,：若,v,0,=,v,l,，则称路,v,0,v,1,v,2,v,l,1,v,l,为,回路,；,环,：在,回路,v,0,v,1,v,2,v,l,1,v,0,中，若,v,0,，,v,1,，,v,2,，,，,v,l,1,各不相同,（此时所有边也互不相同），则称该回路为,环,。,真路,：若,开路,v,0,v,1,v,2,v,l,1,v,l,中，所有结点互不相同（此时所有,边也互不相同），则称该路为,真路,；,例,在图,G,中，若存在一条路连接,v,i,和,v,j,，则称结点,v,i,与,v,j,是,连接的,.,例,上例给出的图是连通图，下图给出的是非连通图。,八、连通图和分图,定义,8-7,在图,G,中，若任意两个结点都是,连接,的，则称,G,是,连通图,，否则，称,G,为,非连通图,。仅有一个孤立结点的图定义它为连通图。,定义,设,H,是图,G,的子图，若,H,满足以下两个条件：,（,1,）,H,是连通的；,（,2,）对,G,的任意子图,H,，若,H,H,，且,H,H,G,，则,H,不是连通的。,注,:,（,2,）的言外之意是：,H,是,G,的最大连通子图。,则称,H,是,G,的,分图,。,例,解,（,b,）显然不是,G,的分图，因为（,b,）不连通；,（,c,）也不是,G,的分图；,（,d,）是,G,的分图；,（,e,）是,G,的分图。,2,割边,：如果在图,G,中删去边,v,i,，,v,j,后，图,G,的分图数增加，则称边,v,i,，,v,j,是,G,的,割边,。,边,v,4,，,v,5,和,v,4,，,v,6,均是割边。,1,割点,：如果在图,G,中删去结点,v,（及与其相关联的所有边后），图,G,的分图数增加，则称结点,v,是,G,的,割点,。,例,10,下,图中,v,4,，,v,6,均是割点；,结论：在图,G,中，边,v,i,，,v,j,为割边当且仅当,边,v,i,，,v,j,不在,G,的任何环中出现。,证明：设,e,是,G,（,V,，,E,）的任意一条边，,e,v,i,v,j,设,e,是割边，用反证法,假设,e,包含在,G,的某一环路,C,中，则,C=l,v,i,v,j,，其中,l,是一条不含,e,的连接,v,i,，,v,j,的真路。,所以删去,e,后，得,G,=G-e,，,G,仍然联通，这与,e,是割边矛盾。,因此，,e,不包含在,G,的任一环路中。,设,e,不包含在,G,的任何环路中。用反证法,假设,e,不是割边，则在,G,中删去边,e=v,i,v,j,后得图,G,，,G,是联通的，所以在,G,中有一条连接,v,i,，,v,j,的路。,由定理,8-2,知，可得到一条连接,v,i,，,v,j,的真路,l,，则,G,中,l,v,I,v,j,是,G,中的一个环路，这与条件矛盾。,因此，假设错误，,e,是割边。,2,距离,：结点,v,i,和,v,j,间的短程的长度称为,v,i,和,v,j,间的,距离,，用,d,（,v,i,，,v,j,）表示。,九、短程和距离,1,短程,：在图,G,中，结点,v,i,和,v,j,若由一条或更多条路相连接，则其中必有长度最短的路，称它为从,v,i,到,v,j,的,短程,。,例,证明,设,为任一连接,v,i,到,v,j,的路，且,=v,i,u,1,u,2,u,r,u,k,u,l,1,v,j,，若,中有相同的结点，设为,u,r,=,u,k,（,r2n,2,，也与,S=2n,2,矛盾。,由上可知，,T,中至少有两片树叶。,树的有些性质可用来作为树的定义，我们列出下面四条,：,（,1,）每两个结点间由唯一的真路相连接的图是树；,（,2,）,m=n,1,的连通图是树；,(3,）,m=n,1,且无环的图是树；,(4),每条边为割边的连通图是树。,（,树的等价定义,）,8.5,树,一、树的定义,二、树的性质,三、生成树与最小生成树,三、生成树与最小生成树,1,生成树,定义,若连通图,G,的生成子图,T,是一棵树，则称,T,为,G,的,生成树,。,例,2,下,图中（,b,）和（,c,）都是（,a,）的生成树。,2,构造连通图,G=,（,V,，,E,）的生成树的方法,（,a,）破环法,例,3,用破环法，构造上页图（,a,）的生成树的过程如下：,（,b,）避环法,例,4,用避环法构造（,a,）的生成树过程如下：,3,最小生成树,定义,8-15,每条边都指定了权的图称为,有权图,。,当,G,是一有权图时，常将其表示为有序三元组,G=,（,V,，,E,，,f,），这里,f,是一由边集,E,到实数集,R,的函数,f,：,E,R.,例,5,下图是一连通有权图。,v,定义,设,G=,（,V,，,E,，,f,）是一连通有权图，,T,是,G,的一棵生成树，,T,的边集用,E,（,T,）表示，,T,的各边权值之和,W,（,T,）,=,称为,T,的权。,G,的所有生成树中权最小的生成树称为,G,的,最小生成树,。,例,6,它们的权,W,（,T,1,）,=24,，,W,（,T,2,）,=30,。,4,构造连通有权图的最小生成树的方法,例,7,以例,5,中图为例，,（,1,）破环法,G=G,1,G,2,G,3,G,4,G,5,G,6,=T,0,W(T,0,)=18,（,2,）避环法,G=G,1,G,1,G,2,G,3,G,4,G,5,=T,0,练习,8-5,1,设树,T,有,7,条边，问,T,有多少个结点？（）,2,设,G,是一个树林，由,3,个分图组成，若,G,有,15,个结点，问,G,有多少条边？（）,3,互不同构的,2,结点树有（）棵？,互不同构的,4,结点树有（）棵？,8,12,1,2,24,4,求下图给出的有权图的最小生成树的权（,）,8.6,有向树,一、有向图,若在图,G=,（,V,，,E,）中，,V,是一有限非空集合，,E,是,V,中不同元素的,有序,对偶的集合，则称,G,是一,有向图,。,有向图中的概念,（,2,）始点，终点；,（,3,）出度，入度，度。,（,1,）有向路：有向开路，有向回路，有向真路，有向环；,二、有向树的定义,定义,8-22,一个不包含环的有向图,G,，若它只有一个结点,v,0,的,入度,为,0,，而其它所有结点的,入度,都等于,1,，则称,G,是,有向树,，,v,0,称为树的,根,。,例,1,下,图给出的图是否有向树？,一个孤立的结点也是一棵有向树。,有向树中的一些概念,（,1,）树叶；,（,2,）分枝结点；,（,3,）级，树高；,一级结点,二级结点,三级结点,（,4,）儿子、父亲、兄弟、祖先和子孙（后代）；,有向树的图解,(,箭头可省,),表示,有向树,：一个结点,v,0,的,入度,为,0,，其它所有结点的,入度,都等于,1,（,4,）,以,u,为根的子树：,设,u,是有向树,T,的分枝结点，由结点,u,和它的所有子孙构成的结点集,U,，以及从,u,出发的所有有向路中的边构成的边集,E,组成,T,的子图,T,=,（,U,，,E,）称为是以,u,为根的,T,的子树；,有向树中的一些概念,一级结点,二级结点,三级结点,（,5,）,u,的子树：,以,u,的儿子为根的子树。,T,1,又称为是,v,0,的子树。,v,0,的另一棵子树是以,v,2,为根的子树。,子图,T,1,=,（,V,1,，,E,1,）是以,v,1,为根的子树。其中,V,1,=,v,1,，,v,3,，,v,4,，,v,5,E,1,=,（,v,1,v,3,）,（,v,1,v,4,）,，,（,v,1,，,v,5,）,。,例,2,T,1,=,（,V,1,，,E,1,）,三、二元树,定义,8-23,在一有向树中，若每一结点的出度都小于或等于,m,，则称这棵树为,m,元树,；若每一个结点的出度恰好等于,m,或,0,，则称这棵树为,完全,m,元树,。,例,3,二元树,完全二元树,满,二元树,三元树,当,m=2,时，分别称其为,二元树,和,完全二元树,。若二元树的所有树叶结点在同一级别则称它为,满二元树,。,1,先根通过,（,1,）访问根；,(2,）在根的左子树上执行先根通过；,（,3,）在根的右子树上执行先根,通过,。,四、访问二元树,下面介绍访问二元树常用的三种方法：,先根访问结果为,_,。,a,b,c,d,f,g,i,e,h,例,2,中根通过,（,1,）在根的左子树上执行中根,通过,；,（,2,）访问根；,（,3,）在根的右子树上执行中根,通过,。,四、访问二元树,下面介绍访问二元树常用的三种方法：,d,b,c,e,a,f,i,g,h,中根访问结果为,_,。,例,3,后根通过,（,1,）在根的左子树上执行后根,通过,；,（,2,）在根的右子树上执行后根,通过,；,（,3,）访问根。,四、访问二元树,下面介绍访问二元树常用的三种方法：,d,f,c,h,i,e,g,b,a,后根访问结果为,_,。,例,定义,8-24,在有向树中，若规定了每一级上结点的次序，则称这样的有向树为,有序树,。,例,4,用二元有序树表示算术表达式,和 。,例如,右图（,a,）和（,b,）表示两棵不同的有序树。,解,例,5,（,1,）用二元有序树表示算术表达式,（,2,）用三种方法访问此树，写出访问结果。,先根访问,中根访问,后根访问,五、有向树中的一些数量关系,有向树和无向树一样，满足关系式,m=n,1,定理,8-20,设,T,是一棵完全,m,元树，树叶结点数为,n,0,，分枝结点数为,t,，则（,m,1,）,t=n,0,1,。,结点数为,n,0,+t,，,于是,mt,=n,0,+t,1,证明,由完全,m,元树的定义知，,T,的边数,=,mt,，,即（,m,1,）,t=n,0,1,定理,8-18,设,T,是一棵二元树，,n,0,表示树叶结点数，,n,2,表示出度为,2,的结点数，则,n,2,=n,0,-1,。,证明,设,T,的结点数为,n,，出度为,1,的,结点数为,n,1,，边数为,m,，,则,n=n,0,+n,1,+n,2,m=n,1,+2n,2,于是,n,1,+2n,2,=n,0,+n,1,+n,2,1,因此,n,2,=,n,0,1,。,m=n,1,又,定理,8-19,设,T,是一棵完全二元树，有,n,个结点，,n,0,个树叶结点，则,n,=2n,0,-1,。,证明,设,T,有,n,2,个出度为,2,的结点，则,n=n,0,+n,2,n=n,0,+,（,n,0,-1,）,即,n,=,2,n,0,-,1,。,n,2,=,n,0,1,推论,完全二元树有奇数个结点。,由定理,8-18,因此,练习,8-6,填空：,（,1,）,2,个结点非同构的有向树的个数是,。,（,2,）,3,个结点非同构的有向树的个数是,。,（,3,）,4,个结点非同构的有向树的个数是,。,1,4,2,8.7,二部图,二、匹配,一、二部图,若,V,1,中任一结点与,V,2,中每一结点均有边相连接，则称二部图为,完全二部图,。若,#V,1,=r,，,#V,2,=t,，则记完全二部图,G,为,K,r,t,。,定义,8-26,二部图,:,G=,（,V,1,，,V,2,，,E,）,V,1,和,V,2,称为,G,的互补结点子集。,一、二部图,例,V,4,V,1,V,2,例,1,如下所示的图是否二部图？,二部图不一定是连通图。,定理,8-23,图,G,为二部图的充要条件是,G,的所有回路均为偶数长。,二、匹配,例,2,下,图所给出的二部图是否存在,V,1,对,V,2,的匹配？是否存在,V,2,对,V,1,的匹配？,定义,8-27,设,G,是具有互补结点子集,V,1,和,V,2,的二部图，其中,V,1,=v,1,，,v,2,，,，,v,r,，,V,1,对,V,2,的匹配是,G,的一个子图，它由,r,条边,v,1,，,v,1,，,v,2,，,v,2,，,，,v,r,，,v,r,组成，其中，,v,1,，,v,2,，,，,v,r,是,V,2,中,r,个不同的元素,。,例,3,某班级成立了三个运动队：篮球队、排球队和足球队。今有张、王、李、赵、陈,5,名同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这,5,人中选出,3,名不兼职的队长？,在图中存在,V,1,对,V,2,的匹配，因此题目的要求可以满足。,解,构造二部图,G=,（,V,1,，,V,2,，,E,）如下：,V,1,V,2,定理,8-24,设,G,（,V,1,，,V,2,，,E,）是一个二部图，则,G,中存在一个,V,1,对,V,2,的匹配的充要条件是，,V,1,中每,k,个结点（,k=1,2,.,#V,1,),至少和,V,2,中的,k,个结点相邻接。（该条件为相异性条件）,定理,8-25,设,G,是一具有互补结点子集,V,1,和,V,2,的二部图，则,G,具有,V,1,对,V,2,的匹配的充分条件是：存在某一整数,t0,，使：,（,1,）对,V,1,中的每个结点，至少有,t,条边与其相关联；,（,2,）对,V,2,中的每个结点，至多有,t,条边与其相关联。,v,1,v,3,v,2,v,4,v,8,v,5,v,6,v,7,v,9,v,10,v,11,v,12,V,1,V,2,例,它的互补结点子集是：,V,1,=,V,2,=,练习,8-7,1,（,1,）图,(a),是否为二部图？（）,v,1,，,v,3,，,v,5,，,v,6,v,2,，,v,4,，,v,7,Y,(a),1,（,2,）图,(b),是否为二部图？（）,N,(b),8.8,平面图,二、平面图的判定,一、平面图的定义,一、平面图的定义,例,1,定义,8-28,一个图,G,若能画在平面上而边无任何交叉，则称,G,为,平面图,否则称图,G,为非平面图,。画出的没有边交叉的图解称为,G,的一个,平面嵌入,。,设,G,是画于平面上的一个图，,=v,1,v,2,v,3,v,4,v,1,是,G,中任意一个环。,=v,1,v,3,和,=v,2,v,4,是,G,中任意两条边无公共结点的真路。,二、平面图的判定,1,简单、直观判定法,例,2,用上述简单、直观的方法判断下图中的两图是否平面图。,2.,欧拉公式判断法,例,3,概念,(1),面,，,边界,；,(2),有限面,，,无限面,；,注意：,对于每一个平面图，恰有一个无限面。,(3),面是相邻的,，,面是不相邻的,。,定理,8-26,设,G,是一连通平面图，有,n,个结点，,m,条边，,k,个面，则,n,m+k,=2,此定理中的公式称为欧拉公式。,证明,（对边数,m,进行归纳）,当,m=0,和,m=1,时，定理显然成立。,假设定理对,m,1,条边的任何连通平面图均成立，设,G,是一具有,n,个结点，,m,条边，,k,个面的连通平面图（,m2,）,由归纳假设,G,中欧拉公式成立。,因此,n,（,m,1,）,+,（,k,1,）,=2,，即,n,m+k,=2,。,若,G,中没有环，则,G,是一棵树，,k=1,，且,m,=,n-1,，于是,n,m,+,k,=,n,-,(,n,-,1,),+,1=2,。,若,G,中有环，则去掉,G,的任一环上的一条边,e,，剩下的图,G,仍连通，有,n,个结点，,k,1,个面，,m,1,条边，,定理,8-27,设,G,是一（,n,，,m,）的连通平面图，,m2,，则,m3n,6.,证明,当,m=2,时，因,G,是简单图必无环，所以,n=3,，上式成立。,当,m2,时，每个面至少由三条边围成，因此各面边界的边数之和,3k,；,另一方面，因为一条边最多在两个面的边界中，,在,中作了重复计数，所以,2m,。,于是得到不等,式,3k,2m,，即,k,2m,/,3,。,根据欧拉公式，。,因此,m,3,n,6.,推论,设,G,是一个（,n,，,m,）的连通平面图。,（,1,）若每个面至少由三条边围成，则,m,3,n,6,；,（,2,）若每个面至少由四条边围成，则,m,2,n,4,。,例,4,利用上述推论判断,K,5,和,K,3,3,是否平面图。,解,在,K,5,中,n=5,，,m=10,，,3n,6=9,。,显然,m,3n,6,，因此,K,5,不是平面图。,在图,K,3,3,中,n=6,，,m=9,，,3n,6=12,，因此,m3n,6,，故据此无法判断,K,3,3,是否平面图。,但是，注意到,K,3,3,是二部图，其每个面必由,4,条或更多偶数条边围成，则应满足,m2n,4,，但它并不满足，因此,K,3,3,也不是平面图。,例,4,利用上述推论判断,K,5,和,K,3,3,是否平面图。,3,库拉托斯基定理判别法,定义,边的剖分，图,G,的,剖分图,边的收缩，图,G,的,收缩图,定理,（,Kuratowski,1930,）,一个图,G,是平面图的充要条件是,G,中既不含,K,5,的剖分图，也不含,K,3,3,的剖分图。,定理,（,Wagner,1937,）,一个图,G,是平面图的充要条件是,G,中既没有可收缩到,K,5,的子图，也没有可收缩到,K,3,3,的子图。,解法一,（,1,）去掉边,a,，,c,，,a,，,d,，,d,，,e,，,b,，,e,例,5,判断下图,G,是否平面图。,图,G,G,子图,G,1,解法二,（,1,）去掉边,d,，,f,和,e,，,g,G,子图,G,2,2,判别下图是否平面图。,(),N,练习,8-8,1,用简单、直观判别法判断下图所给出的,两个图是否平面图。,(),(),Y,Y,8.9,有向图,一、有向图的定义及表示,二、与无向图类似的概念,三、与无向图类似的性质,例,1,设,G=,（,V,，,E,），,V,=,v,1,，,v,2,，,v,3,，,v,4,，,E,=,，,则,G,是一个有向图。,定义,有向图,G,是一个有序二元组（,V,，,E,），其中结点集,V,是一有限非空集合，边集,E,是,V,中不同元素的,有序,对偶的集合。,一、有向图的定义及表示,图解表示：,1,邻接矩阵，可达矩阵,邻接矩阵,可达矩阵,二、与无向图类似的概念,例,2,利用下图的邻接矩阵,A,求其可达矩阵,P,。,将,B,中非零元素改为,1,，得可达矩阵,P,与前面结果相同,解,在有向图中从,v,i,到,v,j,可达，并不意味着从,v,j,到,v,i,也可达；,即便从,v,i,到,v,j,可达，从,v,j,到,v,i,也可达，,d(v,i,，,v,j,),与,d(v,j,，,v,i,),也不一定相等。,2,路、开路、回路、真路和环,3,可达、短程和距离,注：,4,结点的度,结点,v,的出度，记作,deg,+,(v,);,结点,v,的入度，记作,deg,(v);,结点,v,度，用,deg(v,),表示,deg(v,)=,deg,+,(v,)+deg,(v),5,连通性,定义,弱连通,；,单向连通,；,强连通,。,例,3,弱连通,单向连通,强连通,6,子图、真子图和生成子图,例,4,7,同构,例,5,三、与无向图类似的性质,定理,8-30,设,G,是具有,n,个结点和邻接矩阵,A,的有向图，则,A,l,（,l,=1,2,）的第,i,行,j,列的元素表示从结点,v,i,到,v,j,长为,l,的有向路的条数。,定理,8-29,设,G,是具有,n,个结点的有向图，若从结点,v,i,到,v,j,可达，则其短程是一条长度不大于,n,1,的真路。,定理,8-31,一个连通（弱连通）有向图具有欧拉回路的充要条件是,G,的每一个结点的入度和出度相等。具有欧拉路的充要条件是除两个结点外，每个结点的入度等于出度。对于这两个结点，一个结点的出度比入度多,1,，另一个结点的出度比入度少,1,。,例,6,练习,8-9,1.,对下图回答以下问题，在相应题目后面的括号中键入你的答案。,（,1,）由,b,到,e,的短程是 （）,（,2,）由,b,到,e,的路的条数是：,A.1,条；,B.3,条；,C.,无数条,（）,（,3,）写出从,g,到,e,的一条非真路 （）,（,4,）,deg,+,（,e,）,=,（）,（,5,）,deg,（,e,）,=,（）,（,6,）,deg,（,e,）,=,（）,（,7,）,d,（,a,，,f,）,=,（）,d,（,f,，,a,）,=,（）,bage,C,gfedce,1,3,4,25,例 题,1,下面各图有几个结点？,（,1,）,16,条边，每个结点度均为,2,。,（,2,）,21,条边，,3,个度为,4,的结点，其余都是度为,3,的结点。,解,根据握手定理 计算,（,1,）,2m=32,，所以 ，因此结点数,n=16,因此结点数,n=10+3=13,。,（,2,）设度为,3,的结点,x,个，,2m=42,，,所以,3,4+3x=42,，解得,x=10,2,设图,G,的每一结点的度均为,2,，试证明,G,的每一分图均将包含一个环。,证明,设,G,是,G,的任一分图，包含,n,个结点,v,1,，,v,2,，,，,v,n,和,m,条边。,因为,G,中每一结点的度为,2,，所以 ，于是,m=n,，,若,G,不包含环，则,G,是一棵树，有,m=n,1,但这与,m=n,相矛盾，因此,G,必包含有环。,3,一棵树,T,有,5,个度为,2,的结点，,3,个度为,3,的结点，,4,个度为,4,的结点，,2,个度为,5,的结点，其余均是度为,1,的结点，问,T,有几个度为,1,的结点？,解以上三个方程得,x=19,解,设,T,有,x,个度为,1,的结点，则有,5,2+3,3+4,4+2,5+x=2m,m=n,1,5+3+4+2+x=n,4,某次会议有,12,人参加，其中每人都至少有,6,个朋友，这,12,个人围成一圆桌入席，要想使每人相邻的两位都是朋友是否可能？说明理由。,解,题目的要求可以办到，其理由如下：,在平面上用,12,个结点分别表示,12,个人，若,两人是朋友，则在相应的两结点间连一条边，,设得到的图为,G,，则,G,中每一结点的度,6,。,根据推论,8-2,，,G,是哈密尔顿图，即,G,中存在,哈密尔顿环，故,12,人围成一桌时，可以使每人,与相邻两人是朋友。,