单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,河南工业大学离散数学课程组,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学 第七章 图论 习题课,复 习 时 注 意,准确掌握每个概念,灵活应用所学定理,注意解题思路清晰,证明问题时，先用反向思维,(,从结论入手,),分析问题，再按正向思维写出证明过程。,2,图,通路与回路,图的连通性,欧拉图,汉密尔顿图,无向树及其性质,平面图的基本性质,欧拉公式,平面图的对偶图,地图着色与平面图着色,平面图的判断,图的矩阵表示,无向树及其性质,根树及其应用,无向树及其性质,图论的结构图,3,4,一、无向图与有向图,1,、基本概念。,有向图与无向图的定义；有向边,无向边,平行边,环,孤立结点,关联与邻接,(,相邻,),；,结点的度数；结点的度,结点的出度,结点的入度,图的最大度,(G),最小度,(G),零图与平凡图；简单图与多重图；,完全图；子图，生成子图，补图；图的同构。,2,、运用。,(1),灵活运用握手定理及其推论，,(2),判断两个图是否同构，,(3),画出满足某些条件的子图，补图等。,5,二、通路、回路、图的连通性,1,、基本概念,路，回路，迹，通路，圈,无向图和有向图中结点之间的可达关系；连通图，连通分支，连通分支数,W(G),点割集，割点，点连通度,k(G),边割集，割边,(,桥,),，边连通度,(G),短程线，距离,有向图连通的分类，强连通，单侧连通，弱连通，强分图，单侧分图，弱分图,2,、运用,(1),判断有向图或无向图中通路,(,回路,),的类型。,(2),求短程线和距离。,(3),判断有向图连通的类型。,6,三、图的矩阵表示,1,、基本概念。,无向图的邻接矩阵,A,根据邻接矩阵判断,:,各结点的度,有向图结点出,入度。,由,A,k,可以求一个结点到另一个结点长度为,k的路条数.,有向图的可达矩阵,P,用P可以判定:,各结点的度,.,有向图的强分图。,关联矩阵,M:,是结点与边的关联关系矩阵,.,用,M,判定,:,各结点的度,7,大家应该也有点累了，稍作休息,大家有疑问的，可以询问和交流,8,重要定理：握手定理及其推论,推论：任何图,(,无向的或有向的,),中，奇度结点的个数是偶数。,无向图：,有向图：,且,9,(1),(2),(3),多重图,不是,典型题,设图,G=,，其中,V=a,b,c,d,e,，,E,分别由下面给,出。判断哪些是简单图，哪些是多重图？,简单图,10,下列各序列中，可以构成无向简单图的度数序列的,有哪些？,(1)(2,2,2,2,2),可以,(2)(1,1,2,2,3),不可以,(3)(1,1,2,2,2),可以,(4)(0,1,3,3,3),不可以,(5)(1,3,4,4,5),不可以,11,图,G,如右图所示，以下说法正确的是,(),A,(,a,d,),是割边,B,(,a,d,),是边割集,C,(,d,e,),是边割集,D,(,a,d,),(,a,c,),是边割集,正确答案是：,C,。,对割边、边割集的概念理解到位。,定义 设无向图,G,=,为连通图，若有边集,E,1,E,，使图,G,删除了,E,1,的所有边后，所得的子图是不连通图，而删除了,E,1,的任何真子集后，所得的子图是连通图，则称,E,1,是,G,的一个边割集若某个边构成一个边割集，则称该边为割边（或桥）,如果答案,A,正确，即删除边,(,a,d,),后，得到的图是不连通图，但事实上它还是连通的。因此,答案,A,是错误的。,12,设给定图,G,(,如由图所示,),，则图,G,的点割集是,应该填写：,f,，,c,，,e,。,定义 设无向图,G,=,为连通图，若有点集,V,1,V,，使图,G,删除了,V,1,的所有结点后，所得的子图是不连通图，而删除了,V,1,的任何真子集后，所得的子图是连通图，则称,V,1,是,G,的一个点割集若某个结点构成一个点割集，则称该结点为割点。,f,，,c,是不满定义的，因为,f,是,f,，,c,的真子集，而删除,f,后，图是不连通的。,13,单向连通,强连通,强连通,下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？,强连通,单向连通,弱连通,14,设图,G,的邻接矩阵为则,G,的边数为,(),A,5 B,6 C,3 D,4,正确答案是：,D,。,当给定的简单图是无向图时，邻接矩阵为对称的即当结点,v,i,与,v,j,相邻时，结点,v,j,与,v,i,也相邻，所以连接结点,v,i,与,v,j,的一条边在邻接矩阵的第,i,行第,j,列处和第,j,行第,i,列处各有一个,1,，题中给出的邻接矩阵中共有,8,个,1,，故有,8,2=4,条边。度数之和等于,2,倍的边数。,15,(1),D,是哪类连通图,?,(2),D,中,v,1,到,v,4,长度为,1,2,3,4,的通路各多少条？,(3),D,中长度为,4,的通路（不含回路）有多少条？,(4),D,中长度为,4,的回路有多少条？,(5),D,中长度,4,的通路有多少条？其中有几条是回路？,(6),写出,D,的可达矩阵。,有向图,D,如图所示，回答下列问题：,16,有向图,D,如图所示，回答下列诸问：,(1),D,是哪类连通图,?,D,是强连通图。,解答为解,(2)(6),，只需先求,D,的邻接矩阵的前,4,次幂。,17,(2),D,中,v,1,到,v,1,长度为,1,2,3,4,的回路各多少条？,答：,v,1,到,v,1,长度为,1,2,3,4,的回路数分别为,1,1,3,5,。,(3),D,中长度为,4,的通路（不含回路）有多少条？,答：长度为,4,的通路,(,不含回路,),为,33,条,.,(4),D,中长度为,4,的回路有多少条？,答：长度为,4,的回路为,11,条。,(5),D,中长度,4,的通路有多少条？其中有几条是回路？,答：长度,4,的通路,88,条，其中,22,条为回路。,(6),写出,D,的可达矩阵。,4,4,的全,1,矩阵。,18,简单无向图,G,必有,2,结点同度数。,证,:,令,G=v,1,v,n,，,若,G,中没有孤立点,则,G,中,n,个结点的度只取,n-1,个可能值：,1,2,n-1,，从而,G,中至少有两个结点的度数相同。,否则，,G,中有孤立点，不妨设,v,k,v,n,为全部孤立点,则,v,1,v,k-1,的度只取,k-2,个可能值,:1,2,k-2,，从而此,k-1,个结点中至少有两个同度数点。,19,握手定理及其推论的应用,设无向图,G,有,10,条边，,3,度与,4,度结点各,2,个，其余结点的度数均小于,3,，问,G,中至少有几个结点？在最少结点的情况下，写出,G,的度数列,(G),、,(G),。,设,G,的阶数为,n,，,4,个结点的度数分别为,3,，,3,，,4,，,4,其余,n-4,个结点的度数均小于或等于,2,，由握手定理可得,2(3+4)+(n-4)2=14+2n-8,deg(v,i,)=2m=20,解此不等式可得,n7,，即,G,中至少有,7,个结点，,7,个结点时，其度数列为,2,2,2,3,3,4,4,，,=4,=2,。,20,(1),设,n,阶图,G,中有,m,条边，证明：,(G)2m/n(G),(2)n,阶非连通的简单图的边数最多可为多少？最少呢？,(1),证明中关键步骤是握手定理：,2m=,deg(v,i,),(G)deg(v,i,)(G),，于是得,n(G)2mn(G)(G)2m/n(G),易知,2m/n,为,G,的平均度数，因而它大于或等于最小度,(G),，小于或等于最大度,(G),。,(2)n,阶非连通的简单图的边数最多可为,n-1,阶连通图加上一个孤立点，所以边数为,(n-1)(n-2)/2,，最少为,0,。,21,一个图如果同构于它的补图，则该图称为自补图。,1),一个图是自补图，其对应的完全图的边数必为偶数,2),证明：若,n,阶无向简单图是自补图，则,n=4k,或,n=4k+1,（,k,为正整数）。,解：,1),设图,G,是自补图，,G,有,e,条边，,G,对应的完全图的边数为,A,。,G,的补图,G,的边数应为,A,一,e,。因为,G,G,，故边数相等，,e=A,一,e,，,A,2e,，因此,G,对应的完全图的边数,A,为偶数。,2),由,1),可知，自补图对应的完全图的边数为偶数。,n,个结点的完全图,K,n,的边数为,n(n-1)/2,，,所以,n(n-1)/2=2m,，即,n(n-1)=4m,，因而,n,为,4,的倍数，即,n=4k,，,或,n-1,为,4,的倍数，即,n=4k+1,，,即,n=0,1(mod 4),。,22,对于任何一个具有,6,个结点的简单图，要么它包含一个三角形，要么它的补图包含一个三角形。,解：,设,6,个结点的简单图为,G,。考察,G,中的任意一个结点,a,，那么，另外,6,个结点中的任何一个结点，要么在,G,中与,a,邻接，要么在,G,的补图,G,中与,a,邻接。这样，就可把,5,个结点分成两类，将那些在,G,中与,a,邻接的结点归成一类，而将那些在,G,中与,a,邻接的结点归在另一类。于是必有一类至少含有三个结点，不妨假设其中的三个结点为,b,，,c,，,d,，如图所示。若边,(b,，,c),，,(c,，,d),，,(b,，,d),中有一条在,G,中，那么这条边所关联的两个结点都与,a,邻接形成一个三角形；若边,(b,，,c),，,(c,，,d),，,(b,d),都不在,G,中，则,(b,，,c),，,(c,，,d),，,(b,d),形成一个三角形。,23,a,b,c,d,b,c,d,b,c,d,b,c,d,推论,:,任何,6,人的人群中，或者有,3,人互相认识，或者有,3,人彼此陌生。,(,当二人,x,y,互相认识，边,(x,y),着红色，否则着兰色。则,6,人认识情况对应于,K,6,边有红,K,3,或者有兰,K,3,。,),a,a,a,24,证明简单图的最大度小于结点数。,证明：,设简单图,G,有,n,个结点。对任一结点,u,，由于,G,没有环和平行边，,u,至多与其余,n-1,个结点中每一个有一条边相连接，即,deg(u)n-1,，因此，,(G),maxdeg(u)n-1,。,25,设,G,是一个,n,阶无向简单图，,n,是大于等于,3,的奇数。证明图,G,与它的补图中度数为奇数的结点个数相等。,证明：,因为,G,是,n,阶无向简单图，且,n,是大于等于,3,的奇数，故无向图的结点数为奇数，则所对应的,n,阶完全图中每个结点的度数为,n-1,即为偶数，,利用奇数,+,奇数,=,偶数，偶数,+,偶数,=,偶数，所以，在,G,中结点度数为奇数的结点，在其补图中的度数也应为奇数，故,G,和其补图的奇数结点个数也是相同的。,26,P2861,、在无向图,G,中，从结点,u,到结点,v,有一条长度为偶数的通路，从结点,u,到结点,v,又有一条长度为奇数的通路，则在,G,中必有一条长度为奇数的回路。,证明：,设从结点,u,到结点,v,长度为偶数的通路是,ue,1,u,1,e,2,u,2,e,2k,v,，,长度为奇数的通路是,ue,11,u,11,e,12,u,12,e,12h-1,v,，,那么路,ue,1,u,1,e,2,u,2,e,2k,ve,12h-1,u,12,e,12,u,11,e,11,u,就是一条回路，它的边数,2k+(2h-1),2(h+k)-1,，是奇数，故这条回路的长度是奇数。,27,P286,2,、无向图,G,恰有的,2,个奇数度数的结点可达。,解,1,：令,u,w,为,G,恰有的,2,个奇度结点。考察,u,所在的连通分支,G,。因图,G,的奇度点为偶数，故,G,至少还有另一奇度点,w,，但,v,在,G,和,G,中有相同的度，所以,G,恰有,2,个奇度点而且就是,u,和,w,。再由,G,的连通性推出,u,到,w,可达。,解,2,：反证法,设,G,中的两个奇度结点为,u,与,v