离散数学--第七章-图论习题课名师优质课获奖市赛课一等奖课件.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,边数为(),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倍边数。,第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。因为 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)。,第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,WH,FWH,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)/2。,G 总边数为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页,