离散数学--第七章-图论---习题课PPT参考课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,河南工业大学离散数学课程组,第,7,章 图 论习题课,离 散 数 学,河南工业大学,信息科学与工程学院,1,复 习 时 注 意,准确掌握每个概念,灵活应用所学定理,注意解题思路清晰,证明问题时，先用反向思维,(,从结论入手,),分析问题，再按正向思维写出证明过程。,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,(1),(2),(3),多重图,不是,典型题,设图,G=,，其中,V=a,b,c,d,e,，,E,分别由下面给,出。判断哪些是简单图，哪些是多重图？,简单图,9,下列各序列中，可以构成无向简单图的度数序列的,有哪些？,(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),不可以,10,图,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,是错误的。,11,设给定图,G,(,如由图所示,),，则图,G,的点割集是,应该填写f,，,c,，,e,。,定义 设无向图,G,=,为连通图，若有点集,V,1,V,，使图,G,删除了,V,1,的所有结点后，所得的子图是不连通图，而删除了,V,1,的任何真子集后，所得的子图是连通图，则称,V,1,是,G,的一个点割集若某个结点构成一个点割集，则称该结点为割点。,f,，,c,是不满定义的，因为,f,是,f,，,c,的真子集，而删除,f,后，图是不连通的。,12,单向连通,强连通,强连通,下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？,强连通,单向连通,弱连通,13,设图,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,倍的边数。,14,(1),D,是哪类连通图,?,(2),D,中,v,1,到,v,4,长度为,1,2,3,4,的通路各多少条？,(3),D,中长度为,4,的通路（不含回路）有多少条？,(4),D,中长度为,4,的回路有多少条？,(5),D,中长度,4,的通路有多少条？其中有几条是回路？,(6),写出,D,的可达矩阵。,有向图,D,如图所示，回答下列问题：,15,有向图,D,如图所示，回答下列诸问：,(1),D,是哪类连通图,?,D,是强连通图。,解答为解,(2)(6),，只需先求,D,的邻接矩阵的前,4,次幂。,16,(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,矩阵。,17,简单无向图,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,个结点中至少有两个同度数点。,18,握手定理及其推论的应用,设无向图,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,。,19,(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,。,20,一个图如果同构于它的补图，则该图称为自补图。,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),。,21,对于任何一个具有,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),形成一个三角形。,22,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,23,证明简单图的最大度小于结点数。,证明：,设简单图,G,有,n,个结点。对任一结点,u,，由于,G,没有环和平行边，,u,至多与其余,n-1,个结点中每一个有一条边相连接，即,deg(u)n-1,，因此，,(G),maxdeg(u)n-1,。,24,设,G,是一个,n,阶无向简单图，,n,是大于等于,3,的奇数。证明图,G,与它的补图中度数为奇数的结点个数相等。,证明：,因为,G,是,n,阶无向简单图，且,n,是大于等于,3,的奇数，故无向图的结点数为奇数，则所对应的,n,阶完全图中每个结点的度数为,n-1,即为偶数，,利用奇数,+,奇数,=,偶数，偶数,+,偶数,=,偶数，所以，在,G,中结点度数为奇数的结点，在其补图中的度数也应为奇数，故,G,和其补图的奇数结点个数也是相同的。,25,P286,1,、在无向图,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,v,e,12h-1,u,12,e,12,u,11,e,11,u,就是一条回路，它的边数,2k+(2h-1),2(h+k)-1,，是奇数，故这条回路的长度是奇数。,26,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,，若,u,与,v,不连通，即它们之间无路，因而,u,与,v,处于,G,中恰有不同连通分支中，设,u,在,G,1,中，,v,在,G,2,中，,G,1,与,G,2,是,G,的连通分支，由于,G,中恰有两个奇度结点，因而当作为独立的图时，均有一个奇度结点，这与握手定理的推论相矛盾。,27,3,、若图,G,是不连通的，则,G,的补图,G,是连通的。,证明：,若图,G,是不连通的，可设图,G,的连通分支是,G(V,1,),，,G(V,2,),，,，,G(V,m,)(m2),。由于任意两个连通分支,G(V,i,),与,G(V,j,)(ij),之间不连通，因此两个结点子集,V,i,与,V,j,之间的所有连线都在图,G,的补图,G,中。任取两个结点,u,和,v,，有两种情形：,a)u,和,v,分别属于两个不同结点子集,V,i,与,V,j,。由上可知,G,包含边,(u,，,v),，故,u,和,v,在,G,中是连通的。,b)u,和,v,属于同,个结点子集,V,i,。可在另一个结点子集,V,j,中取一个结点,w,，由上可知边,(u,w),及边,(v,w),均在,G,中，故邻接边,(u,w),和,(w,v),组成的路连接结点,u,和,v,，即,u,和,v,在,G,中也是连通的。,由此可知，当图,G,不是连通图时，,G,必是连通图。,28,在具有,n,个结点的,无向简单图,G,中,，,若任意,2,个不同结点的度数之和大于等于,n-1,，则图,G,是连通图。,证明：,反证法,设图,G,不是连通图，不妨设图,G,有,2,个连通分支,G,1,和,G,2,，其中,G,1,有,k(k 1),个结点，,G,2,有,n-k,个结点。在,G,1,中任取一点,v,i,，,G,2,中任取一点,v,j,，则,:,deg(v,i,)k-1,deg(v,j,)(n-k)-1,由此可得,:,deg(v,i,)+deg(v,j,)(k-1)+(n-k)-1=n-2,与题设矛盾，故图,G,是连通图。,29,证明,n,个结点,k,条边的简单图,G,，若,k(n-1)(n-2)/2,，则图,G,是连通图。,证明：,反证法,设,G,的补图为,G,，边数记为,k,G,，,则,k,G,+k,G,=n(n-1)/2,，,假设,G,不连通，则,G,的补图是连通，,k,G,n-1;,k,G,+k,G,k,G,+n-1,，利用,k,G,+k,G,=n(n-1)/2,；,推出,k,G,(n-1)(n-2)/2,，和题设矛盾；,故图,G,是连通图。,30,（渡河问题）一个摆渡人，要把一只狼、一只羊和一捆干草运过河去，河上有一只木船，每次除了人以外，只能带一样东西。另外，如果人不在旁时，狼就要吃羊，羊就要吃干草。问这人怎样才能把它们运过河去？,解,:,用,F,表示摆渡人，,W,表示狼，,S,表示羊，,H,表示干草。,若用,FWSH,表示人和其它,3,样东西在河的左岸的状态。这样在左岸全部可能出现的状态为以下,16,种：,FWSH FWS FWH FSH,WSH,FW FS FH,WS WH SH F,W S H ,这里,表示左岸是空集，即人、狼、羊、干草都已运到右岸去了。,利用通路的概念解决一个古老的著名问题。,31,根据题意检查一下就可以知道，,FWSH FWS FWH FSH,WSH,FW,FS,FH,WS,WH,SH,F,W S H ,这,16,种情况中有,6,种情况是不允许出现的。,它们是：,WSH,、,FW,、,FH,、,WS,、,SH,、,F,。如,FH,表示人和干草在左岸，而狼和羊在右岸，这当然是不行的。因此，允许出现的情况只有,10,种。,我们构造一个图，它的结点就是这,10,种状态。若一种状态可以转移到另一种状态，,就在表示它们的两结点间连一条边，这样就画出图。本题就转化为找结点,FWSH,到结点,的通路。从图中得到两条这样的通路，即有两种渡河方案。,FWSH,WHFWH,H,W,FSH,FSW,S,FS,32,欧拉路，欧拉回路，欧拉图。,判定,:,有欧拉路的充要条件：,无或有两个奇数度的结点。,有欧拉回路的充要条件：,所有结点度数均为偶数。,汉密尔顿路，汉密尔顿回路，汉密尔顿图,汉密尔顿图的判定,:,必要条件：,设无向图,G,=,是,汉密尔顿,图，则对于任意,非空子集,S,，有,W(G-S)|S|,。,推论,设无向图,G,=,是半,汉密尔顿,图，则对于任意,非空子集,S,，有,W(G-S)|S|+1,。,充分条件：若简单图,G,中每对结点的度数和,|V|=n,，则,G,是汉密尔顿图。,半汉密尔顿图，若简单图,G,中每对结点的度数和,|V|-1,，则,G,是半汉密尔顿图。,四、欧拉图与汉密尔顿图,(,会判定,),33,P311 2,试构造一个欧拉图，其结点数,v,和边数,e,满足下述条件,(1)v,和,e,的奇偶性相同；,(2)v,和,e,的奇偶性相反。,解：,(1),(2),说明：欧拉图中，结点数和边数的奇偶性既可以相同也可以相反。,34,n,个结点的有向完全图，哪些是有向欧拉图，为什么？,解：,n,个结点的有向完全图是有向欧拉图，对于,n,个结点的有向完全图，每个结点的度数均相等，都是偶数,2(n-1),，且每个结点的入度,=,出度，所以,n,个结点的有向完全图是有向欧拉图。,无向完全图,Kn,是几笔画图？为什么？,(1),当,n=1,时，,Kn,为平凡图；,(2),当,n=,奇数时，,Kn,中每个结点度数,=n-1,为偶数，所以,Kn,为欧拉图，可以一笔画出；,(3),当,n=,偶数时，,Kn,中每个结点度数,=n-1,为奇数，对应的有,n/2,对奇数度结点，因此可以,n/2,笔画出。,35,删除,A,和,B,后，形成,3,个连通分支，,即,W(G-S)=3|S|=2,因此，图,G,不是汉密尔顿图。,图,G,是否是汉密尔顿图。,A,B,36,7,位客人入席，,A,只会讲英语，,B,会讲英，汉语，,C,会讲英，意大利，俄语，,D,会讲日，汉语，,E,会讲德，意大利语，,F,会讲法，日，俄语，,G,会讲法，德语。能否安排圆桌席位使每位客人与,其左右邻不用翻译便可交谈,?,解：,建立无向图模型,:,结点为客人；,会共同语言的,2,结点相邻接。,则问题,归结为,求此图的一条,汉密尔顿回路,。,不难验证，此图有一条汉密尔顿,回路是,:(A,B,D,F,G,E,C,A),。,按此回路安排席位可,以,使得每个人都可以和它两边的人直接交谈,。,汉密尔顿图,的应用,B,C,D,E,F,G,A,英,英,法,德,俄,意,日,汉,37,某地有,5,个风景点，若每个风景点均有,2,条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这,5,处？,解：,将,5,个风景点看成是有,5,个结点的无向图，两风景点间的道路看成是无向图的边,因为每处均有两条道路与其他结点相通，故每个结点的度数均为,2,，,从而任意两个不相邻的结点的度数之和等于,4,，正好为总结点数减,1,。,故此图中存在一条,汉密尔顿路,，因此游人可以经过每个风景点恰好一次而游完这,5,处。,38,设图,G,有,n,个结点，,e,条边，证明：若 ，则,G,为汉密尔顿图。,证明：,反证法,假设,G,不是汉密尔顿图，则根据汉密尔顿图的判定定理，知至少存在两个结点的度数之和小于,n,，则该两个结点所关联的边的数目,m,1,小于,n,，即,m,1,n-1,，而当其余,n-2,个结点构成完全图时，其所关联的边数目,m,2,为最大值，即,m,2,(n-2)(n-3)/2G,的总的边数为,m,1,+m,2,，从而,与题设 矛盾。,所以，图,G,为汉密尔顿图。,39,将,6,个人分成,3,组（每组,2,个人）去完成,3,项任务。已知每个人至少与其余,5,个人中的,3,个人能互相合作。问：能否使得每组的,2,个人都能相互合作？请说明理由。,解：,用,v,1,v,2,v,6,代表,6,个人，若,v,i,v,j,能相互合作，就在,v,i,与,v,j,之间连无向边，得无向图,G=(V,E),。,由已知条件可知，对于任意的,v,i,V,deg(v,i,)n/2,，因此,deg(v,i,)+deg(v,j,)n,，由定理可知,G,是汉密尔顿图，,因而,G,中存在汉密尔顿回路，不妨设,C=v,i1,v,i2,v,i3,v,i4,v,i5,v,i6,v,i1,为其中一条，在这种回路上相邻两个结点代表的二人能相互合作。,40,某工厂生产由,6,种不同颜色的纱织成的双色布，已知在品种中，每种颜色至少分别和其他,5,种颜色中的,3,种颜色搭配，证明可以挑出,3,种双色布，它们恰有,6,种不同的颜色。,解：,用,v,i,表示颜色,(i=1,26),，作无向图,G(V,E),，其中,V=v,1,v,2,v,6,，,E=(u,v)|u,vV,且,uv,并且,u,与,v,搭配,u,vV,deg(u)+deg(v)6,所以,G,是汉密尔顿图，因而,G,中存在汉密尔顿回路，不妨设,v,1,v,2,v,3,v,4,v,5,v,6,v,1,为其中一条，在这种回路上每个结点代表的颜色都能与它相邻结点代表的颜色相搭配，于是让,v,1,与,v,2,v,3,与,v,4,v,5,与,v,6,搭配，织成,3,种双色布，包含了,6,种颜色。,41,下列命题中,(),是正确的,.,1.,欧拉图的子图一定是欧拉图,2.,汉密尔顿图的子图一定是汉密尔顿图,42,反证法在图论中的应用,图论这门学科理论性强，与其它数学分支学科不同的是，在它的理论证明之中反证法使用的特别多。反证法最大的优点是无形中多了一个或几个条件，因此在图论中证明有些命题时，若感到条件“不足”或无从下手，不妨考虑使用反证法。用反证法证明图论命题有时能起到其它方法所办不到的功效，下面从几个不同类型出发，结合适当的实例介绍反证法在图论中的应用。,43,有关“存在性”问题,在简单图,G,中，若,v,(,G,)2,，则在,G,中必存在度数相等的两个结点。,证：,设图,G,中各点的度均不相等，那么必有最大度,v,1,。若,=,v,1,，必有,1,，从而，,-+1,v,1,，又与,G,是简单图矛盾。,44,有关涉及“至少”的问题,若,G,是,k,的树，试证,G,至少有,k,个结点度为,1,。,证：若,G,中度为,1,的结点个数,s,小于,k,，由度和定理得，但对树,G,却有，两者矛盾。,45,有些以否定判断为结论的命题,若,G,中每个结点的度均为偶数，试证,G,中的任何一,条边都不是割边。,证：,假设,G,中存在割边,e,，取,G,e,中含,e,的一个端点,u,的连通分支为,G,1,，则,G,1,中除,u,的度为奇数外，其余结点的度均为偶数，这与定理“在任何图中度为奇数的结点有偶数个”相矛盾，故,G,中的任何一条边都不是割边。,46,有些已知条件较少，或仅从已知条件出发能够得出的信息知之甚少的问题,若一个连通图,G,的每条边都是割边，则,G,是树。,证：假设,G,是连通图但不是树，则包含一个圈,C,。由于割边不应该包含在任何一个圈中，故导致矛盾。,47,7.,采用直接证明的方法不够多，或者用直接证法较困难的命题,例,7,：若,e,不包含在,G,的一个圈中，试证,e,是,G,的割边。,证：假设,e,=,xy,不是,G,的割边，则。由于在,G,中存在一条,(,x,y,),路（即,xy,），所以,x,和,y,都在,G,的同一个分支中。由此推知,x,和,y,在,G,e,的同一个分支中，从而在,G-e,中存在一条,(,x,y,),路,p,，于是,e,就位于,G,的圈中，导致矛盾。,48,