离散数学--第七章-图论---习题课.ppt

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