邱婉玲耿素云离散数学ch公开课一等奖优质课大赛微课获奖课件.pptx

单击此处编辑母版标题样式,*,第五部分,图论,本部分主要内容,图基本概念,欧拉图、哈密顿图,树,平面图,支配集、覆盖集、独立集、匹配与着色,1,第1页,第1页,第十四章,图基本概念,主要内容,图,通路与回路,图连通性,图矩阵表示,图运算,预备知识,多重集合元素能够重复出现集合,无序集,A,B,=(,x,y,)|,x,A,y,B,2,第2页,第2页,14.1,图,定义14.1,无向图,G,=,其中,(1),V,为顶点集，元素称为,顶点,(2),E,为,V,V,多重集，其元素称为无向边，简称,边,实例,设,V,=,v,1,v,2,v,5,E,=(,v,1,v,1,),(,v,1,v,2,),(,v2,v,3,),(,v,2,v,3,),(,v,2,v,5,),(,v,1,v,5,),(,v,4,v,5,),则,G,=为一无向图,3,第3页,第3页,有向图,定义14.2,有向图,D,=,只需注意,E,是,V,V,多重子集,图2表示是一个有向图，试写出它,V,和,E,注意：图数学定义与图形表示，在同构（待叙）意义下,是一一相应,4,第4页,第4页,相关概念,1.图,可用,G,泛指图（无向或有向）,V,(,G,),E,(,G,),V,(,D,),E,(,D,),n,阶图,2.有限图,3.,n,阶零图与平凡图,4.空图,5.用,e,k,表示无向边或有向边,6.顶点与边关联关系,关联、关联次数环,孤立点,7.顶点之间相邻与邻接关系,5,第5页,第5页,8.邻域与关联集,v,V,(,G,)(,G,为无向图),v,关联集,v,V,(,D,)(,D,为有向图),9.标定图与非标定图,10.基图,相关概念,6,第6页,第6页,多重图与简朴图,定义14.3,(1)无向图中平行边及重数,(2)有向图中平行边及重数（注意方向性）,(3)多重图,(4)简朴图,在定义14.3中定义简朴图是极其主要概念,7,第7页,第7页,顶点度数,定义14.4,(1)设,G,=为无向图,v,V,d,(,v,),v,度数,简称度,(2)设,D,=为有向图,v,V,d,+,(,v,),v,出度,d,(,v,),v,入度,d,(,v,),v,度或度数,(3),(,G,),(,G,),(4),+,(,D,),+,(,D,),(,D,),(,D,),(,D,),(,D,),(5)奇顶点度与偶度顶点,8,第8页,第8页,定理,14.1,设,G,=,为任意无向图，,V,=,v,1,v,2,v,n,|,E,|=,m,则,证,G,中每条边(包括环)都有两个端点，因此在计算,G,中各顶点度数之和时，每条边均提供2度，,m,条边共提供 2,m,度.,本定理证实类似于定理,14.1,握手定理,定理14.2,设,D,=为任意有向图，,V,=,v,1,v,2,v,n,|,E,|=,m,则,9,第9页,第9页,握手定理推论,推论,任何图(无向或有向)中，奇度顶点个数是偶数.,证,设,G,=为任意图，令,V,1,=,v,|,v,V,d,(,v,)为奇数,V,2,=,v,|,v,V,d,(,v,)为偶数,则,V,1,V,2,=,V,V,1,V,2,=,，由握手定理可知,由于2,m,均为偶数，因此 为偶数，但由于,V,1,中,顶点度数为奇数，因此|,V,1,|必为偶数.,10,第10页,第10页,例1,无向图,G,有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问,G,阶数,n,为几？,解 本题关键是应用握手定理.,设除3度与4度顶点外，尚有,x,个顶点,v,1,v,2,v,x,，则,d,(,v,i,),2,，i,=1,2,x,，,于是得不等式,32,24+2,x,得,x,4,阶数,n,4+4+3=11.,握手定理应用,11,第11页,第11页,图度数列,1.,V,=,v,1,v,2,v,n,为无向图,G,顶点集，称,d,(,v,1,),d,(,v,2,),d,(,v,n,)为,G,度数列,2.,V,=,v,1,v,2,v,n,为有向图,D,顶点集，,D,度数列,：,d,(,v,1,),d,(,v,2,),d,(,v,n,),D,出度列,：,d,+,(,v,1,),d,+,(,v,2,),d,+,(,v,n,),D,入度列,：,d,(,v,1,),d,(,v,2,),d,(,v,n,),3.非负整数列,d,=(,d,1,d,2,d,n,)是,可图化,，是,可简朴图化,.,易知：(2,4,6,8,10)，(1,3,3,3,4)是可图化，后者又是可,简朴图化，而(2,2,3,4,5)，(3,3,3,4)都不是可简朴图化,，尤其是后者也不是可图化,12,第12页,第12页,图同构,定义14.5,设,G,1,=,G,2,=为两个无向图(两个有向,图)，若存在双射函数,f,:,V,1,V,2,对于,v,i,v,j,V,1,(,v,i,v,j,),E,1,当且仅当(,f,(,v,i,),f,(,v,j,),E,2,（,E,1,当且仅当,E,2,),并且,(,v,i,v,j,)（）与(,f,(,v,i,),f,(,v,j,)（）重数相,同，则称,G,1,与,G,2,是,同构,，记作,G,1,G,2,.,图之间同构关系含有自反性、对称性和传递性.,能找到多条同构必要条件，但它们全不是充分条件：,边数相同，顶点数相同;度数列相同;,对应顶点关联集及邻域元素个数相同，等等,若破坏必要条件，则两图不同构,判断两个图同构是个难题,13,第13页,第13页,图同构实例,图中(1)与(2)度数列相同，它们同构吗？为何？,(1)(2)(3)(4),图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.,(1)(2),14,第14页,第14页,n,阶完全图与竞赛图,定义14.6,(1),n,(n,1)阶无向完全图,每个顶点与其余顶点均相邻无向简朴图，记作,K,n,.,简朴性质：边数,(2),n,(,n,1)阶,有向完全图,每对顶点之间都有两条方向相反有向边有向简朴图.,简朴性质：,(3),n,(,n,1)阶,竞赛图,基图为,K,n,有向简朴图.,简朴性质：边数,15,第15页,第15页,n,阶,k,正则图,(1)为,K,5,，(2)为3阶有向完全图，(3)为4阶竞赛图.,(1)(2)(3),定义14.7,n,阶,k,正则图,=,=,k,无向简朴图,简朴性质：边数（由握手定理得）,K,n,是,n,1正则图，,彼得松图（见书上图14.3(1)所表示，记住它）,16,第16页,第16页子图,定义14.8,G,=,G,=,(1),G,G,G,为,G,子图,，,G,为,G,母图,(2)若,G,G,且,V,=,V,，则称,G,为,G,生成子图,(3)若,V,V,或,E,E,，称,G,为,G,真子图,(4),V,（,V,V,且,V,）,导出子图,，记作,G,V,(5),E,（,E,E,且,E,）,导出子图,，记作,G,E,17,第17页,第17页,例2,画出,K,4,所有非同构生成子图,实例,18,第18页,第18页,补图,定义14.9,设,G,=为,n,阶无向简朴图，以,V,为顶点集，以所有使,G,成为完全图,K,n,添加边构成集合为边集图，称为,G,补图,，记作 .,若,G,则称,G,是,自补图,.,相对于,K,4,求上面图中所有图补图，并指出哪些是自补图.,问：互为自补图两个图边数有何关系？,19,第19页,第19页,14.2,通路与回路,定义14.11,给定图,G,=（无向或有向），,G,中,顶点与,边交替序列,=,v,0,e,1,v,1,e,2,e,l,v,l,，,v,i,1,v,i,是,e,i,端点.,(1)通路与回路：,为,通路,；若,v,0,=,v,l,，,为,回路,，,l,为,回路长,度,.,(2)简朴通路与回路：所有边各异，,为,简朴通路,，又若,v,0,=,v,l,，,为,简朴回路,(3)初级通路(路径)与初级回路(圈)：,中所有顶点各异，则称,为,初级通路,(,路径,)，又若除,v,0,=,v,l,，所有顶点各不相同且所有边各异，则称,为,初级回路,(,圈,),(4)复杂通路与回路：有边重复出现,20,第20页,第20页,几点阐明,表示法,定义表示法,只用边表示法,只用顶点表示法（在简朴图中）,混合表示法,环（长为1圈）长度为1，两条平行边组成圈长度为,2，无向简朴图中，圈长3，有向简朴图中圈长度2.,不同圈（以长度3为例）,定义意义下,无向图：图中长度为l（l3）圈，定义意义下为2l个,有向图：图中长度为l（l3）圈，定义意义下为l个,同构意义下：长度相同圈均为1个,试讨论l=3和l=4情况,21,第21页,第21页,通路与回路长度,定理14.5,在,n,阶图,G,中，若从顶点,v,i,到,v,j,（,v,i,v,j,）存在通路，,则从,v,i,到,v,j,存在长度小于或等于,n,1 通路.,推论,在,n,阶图,G,中，若从顶点,v,i,到,v,j,（,v,i,v,j,）存在通路，则,从,v,i,到,v,j,存在长度小于或等于,n,1初级通路（路径）.,定理14.6,在一个,n,阶图,G,中，若存在,v,i,到本身回路，则一,定存在,v,i,到本身长度小于或等于,n,回路.,推论,在一个,n,阶图,G,中，若存在,v,i,到本身简朴回路，则一,定存在长度小于或等于,n,初级回路.,22,第22页,第22页,14.3,图连通性,无向图连通性,(1)顶点之间连通关系：,G,=为无向图,若,v,i,与,v,j,之间有通路，则,v,i,v,j,是,V,上等价关系,R,=|,u,v,V,且,u,v,(2),G,连通性与连通分支,若,u,v,V,，,u,v,，则称,G,连通,V,/,R,=,V,1,V,2,V,k,，称,G,V,1,G,V,2,G,V,k,为,连通分,支,，其个数,p,(,G,)=,k,(,k,1)；,k,=1，,G,连通,23,第23页,第23页,短程线与距离,(3)短程线与距离,u,与,v,之间,短程线,：,u,v,，,u,与,v,之间长度最短通路,u,与,v,之间,距离,：,d,(,u,v,)短程线长度,d,(,u,v,)性质：,d,(,u,v,),0,u,v,时,d,(,u,v,)=,d,(,u,v,)=,d,(,v,u,),d,(,u,v,)+,d,(,v,w,),d,(,u,w,),24,第24页,第24页,无向图连通度,1.删除顶点及删除边,G,v,从,G,中将,v,及关联边去掉,G,V,从,G,中删除,V,中所有顶点,G,e,将,e,从,G,中去掉,G,E,删除,E,中所有边,2.点割集与边割集,点割集与割点,定义14.16,G,=,V,V,V,为,点割集,p,(,G,V,),p,(,G,)且有极小性,v,为,割点,v,为点割集,定义14.17,G,=,E,E,E,是,边割集p,(,G,E,),p,(,G,)且有极小性,e,是,割边,（桥）,e,为边割集,25,第25页,第25页,点割集与割点,例3,v,1,v,4,，,v,6,是点,割集，,v,6,是割点.,v,2,v,5,是点割集吗？,e,1,e,2,，,e,1,e,3,e,5,e,6,，,e,8,等是边割集，,e,8,是,桥，,e,7,e,9,e,5,e,6,是边割,集吗？,几点阐明：,K,n,中无点割集，,N,n,中既无点割集，也无边割集，其中,N,n,为,n,阶零图.,若,G,连通，,E,为边割集，则,p,(,G,E,)=2，,V,为点割集，则,p,(,G,V,),2,26,第26页,第26页,点连通度与边连通度,定义14.18,G,为连通非完全图,点连通度,(,G,)=min|,V,|,V,为点割集,要求,(,K,n,)=,n,1,若,G,非连通，,(,G,)=0,若,(,G,),k,，则称,G,为,k,-连通图,定义14.19,设,G,为连通图,边连通度,(,G,)=min|,E,|,E,为边割集,若,G,非连通，则,(,G,)=0,若,(,G,),r,，则称,G,是,r,边-连通图,图中，,=,=1，它是 1-连通图 和 1边-连通图,27,第27页,第27页,几点阐明,(,K,n,)=,(,K,n,)=,n,1,G,非连通，则,=,=0,若,G,中有割点，则,=1，若有桥，则,=1,若,(,G,)=,k,则,G,是1-连通图，2-连通图，,k,-连通图，但不是(,k,+,s,)-连通图，,s,1,若,(,G,)=,r,则,G,是1-边连通图，2-边连通图，,r,-边连通图，但不是(,r,+,s,)-边连通图，,s,1,之间关系.,定理7.5,(,G,),(,G,),(,G,),请画出一个,无向简朴图,28,第28页,第28页,有向图连通性,定义14.20 D=为有向图,vi vj（vi 可达 vj）vi 到vj 有通路,vi vj（vi 与vj 相互可达）,性质,含有自反性(vi vi)、传递性,含有自反性、对称性、传递性,vi 到vj 短程线与距离,类似于无向图中，只需注意距离表示法不同,(无向图中d(vi,vj)，有向图中d)及 d无对称性,29,第29页,第29页,有向图连通性及分类,定义14.22,D,=为有向图,D,弱连通,(连通)基图为无向连通图,D,单向连通,v,i,v,j,V,，,v,i,v,j,或,v,j,v,i,D,强连通,v,i,v,j,V,，,v,i,v,j,易知，强连通,单向连通,弱连通,判别法,定理14.8,D,强连通当且仅当,D,中存在通过每个顶点至少一次,回路,定理14.9,D,单向连通当且仅当,D,中存在通过每个顶点至少一,次通路,30,第30页,第30页,扩大路径法,无向图中,设,G,=为,n,阶无向图，,E,.设,l,为,G,中一条路径，若,此路径始点或终点与通路外顶点相邻，就将它们扩到通,路中来，继续这一过程，直到最后得到通路两个端点不,与通路外顶点相邻为止.设最后得到路径为,l,+,k,（长度,为,l,路径扩大成了长度为,l,+,k,路径），称,l,+,k,为“极大路,径”，称使用此种办法证实问题办法为“,扩大路径法,”.,有向图中类似讨论，只需注意，在每步扩大中确保有向边方,向一致性.,31,第31页,第31页,实例,由某条路径扩大出极大路径不惟一，极大路径不一定是,图中最长路径,上图中，(1)中实线边所表示长为2初始路径,，(2),(3),(4),中实线边所表示都是它扩展成极大路径.,还能找到另外极大路径吗？,(1),(2),(4),(3),32,第32页,第32页,扩大路径法应用,例4,设,G,为,n,（,n,3）阶无向简朴图，,2，证实,G,中存在,长度,+1 圈.,证 设,=,v,0,v,1,v,l,是由初始路径,0,用扩大路径法得到极,大路径，则,l,（为何？）.,由于,v,0,不与,外顶点相邻，又,d,(,v,0,),，因而在,上除,v,1,外，至少还存在,1个顶点与,v,0,相邻.设,v,x,是离,v,0,最远顶,点，于是,v,0,v,1,v,x,v,0,为,G,中长度,+1 圈.,33,第33页,第33页,二部图,定义14.23,设,G,=为一个无向图，若能将,V,分成,V,1和,V,2,(,V,1,V,2,=,V,，,V,1,V,2,=,),，使得,G,中每条边两个端点都是,一个属于,V,1,，另一个属于,V,2,，则称,G,为,二部图,(或称,二分,图,、,偶图,等)，称,V,1,和,V,2,为,互补顶点子集,，常将二部图,G,记为.,又若,G,是简朴二部图，,V,1,中每个顶点均与,V,2,中所有顶点相,邻，则称,G,为,完全二部图,，记为,K,r,s,，其中,r,=|,V,1,|，,s,=|,V,2,|.,注意，,n,阶零图为二部图.,34,第34页,第34页,二部图判别法,定理14.10,无向图,G,=是,二部图,当且仅当,G,中无奇圈,由定理14.10可知图9中各图都是二部图，哪些是完全二部,图？哪些图是同构？,35,第35页,第35页,14.4,图矩阵表示,无向图关联矩阵（对图无限制）,定义14.24,无向图,G,=，|,V,|=,n,，|,E,|=,m,，令,m,ij,为,v,i,与,e,j,关联次数，称(,m,ij,),n,m,为,G,关联矩阵,，记为,M,(,G,).,性质,36,第36页,第36页,有向图关联矩阵（无环有向图）,定义,14.25,有向图,D,=，令,则称(,m,ij,),n,m,为,D,关联矩阵,，记为,M,(,D,).,(4),平行边相应列相同,性质,有向图关联矩阵,37,第37页,第37页,有向图邻接矩阵（无限制）,定义14.26,设有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,令为顶点,v,i,邻接到顶点,v,j,边条数，称为,D,邻接矩,阵,，记作,A,(,D,)，或简记为,A,.,性质,38,第38页,第38页,推论,设,B,l,=,A,+,A,2,+,A,l,（,l,1,），则,B,l,中元素,为,D,中长度为,l,通路总数，,定理14.11,设,A,为有向图,D,邻接矩阵，,V,=,v,1,v,2,v,n,为顶点集，则,A,l,次幂,A,l,（,l,1,）中元素,为,D,中,v,i,到,v,j,长度为,l,通路数，其中,为,v,i,到本身长度为,l,回路数而,为,D,中长度小于或等于,l,回路数,为,D,中长度小于或等于,l,通路数.,邻接矩阵应用,为,D,中长度为,l,回路总数.,39,第39页,第39页,例5,有向图,D,如图所表示，求,A,A,2,A,3,A,4,，并回答诸问题：,(1),D,中长度为1,2,3,4通路各有多少条？其中回路分别为多少条？,(2),D,中长度小于或等于4通路为多少条？其中有多少条回路？,实例,40,第40页,第40页,(1),D,中长度为1通路为8条，其中有1条是回路.,D,中长度为2通路为11条，其中有3条是回路.,D,中长度为3和4通路分别为14和17条，回路分别,为1与3条.,(2),D,中长度小于等于4通路为50条，其中有8条是回路.,实例求解,41,第41页,第41页,定义14.27,设,D,=为有向图.,V,=,v,1,v,2,v,n,令,有向图可达矩阵（无限制）,称(,p,ij,),n,n,为,D,可达矩阵，记作,P,(,D,)，简记为,P,.,由于,v,i,V,，,v,i,v,i,，因此,P,(,D,)主对角线上元素全为1.,由定义不难看出,D,强连通当且仅当,P,(,D,)为全1矩阵.,下图所表示有向图,D,可达矩阵为,42,第42页,第42页,第十四章,习题课,主要内容,无向图、有向图、关联与相邻、简朴图、完全图、正则图、子图、补图；握手定理与推论；图同构,通路与回路及其分类无向图连通性与连通度,有向图连通性及其分类,图矩阵表示,43,第43页,第43页,基本要求,深刻理解握手定理及推论内容并能灵活地应用它们,深刻理解图同构、简朴图、完全图、正则图、子图、补图、二部图概念以及它们性质及互相之间关系,记住通路与回路定义、分类及表示法,深刻理解与无向图连通性、连通度相关诸多概念,会判别有向图连通性类型,纯熟掌握用邻接矩阵及其幂求有向图中通路与回路数办法，会求可达矩阵,44,第44页,第44页,19阶无向图,G,中，每个顶点度数不是5就是6.证实,G,中至少有5个6度顶点或至少有6个5度顶点.,练习,1,证 关键是利用握手定理推论.,办法一：穷举法,设,G,中有,x,个5度顶点，则必有(9,x,)个6度顶点，由握手定理推论可知，(,x,9,x,)只有5种也许：(0,9),(2,7),(4,5),(6,3),(8,1）它们都满足要求.,办法二：反证法,不然，由握手定理推论可知，“,G,至多有4个5度顶点并且至多有4个6度顶点”，这与,G,是 9 阶图矛盾.,45,第45页,第45页,2数组2,2,2,2,3,3能简朴图化吗？若能，画出尽也许多非同构图来.,练习,2,只要能画出6 阶无向简朴图，就说明它可简朴图化.下图4个图都以此数列为度数列，请证实它们彼此不同构，都是K6子图.,46,第46页,第46页,用扩大路径法证实.,情况一：,+,.证实,D,中存在长度,+1,圈.,设,=,v,0,v,1,v,l,为极大路径，则,l,(为何?),.由于,d,(,v,0,),，因此在,上存在,PLAY,邻接到,v,0,，于是,情况二：,+,，只需注意,d,+,(,v,l,),+,.,3设,D,=为有向简朴图，已知,(,D,),2,，,+,(,D,)0，,(,D,)0，证实,D,中存在长度,max,+,+1,圈.,为,D,中长度,+1,有向圈,练习,3,47,第47页,第47页,(1),D,中有几种非同构圈？,(2),D,中有几种非圈非同构简朴回路？,(3),D,是哪类连通图?,(4),D,中,v,1,到,v,4,长度为1,2,3,4通路各多少,条？其中几条是非初级简朴通路？,(5),D,中,v,1,到,v,1,长度为1,2,3,4回路各多少,条？讨论它们类型.,(6),D,中长度为4通路（不含回路）有多少条？,(7),D,中长度为4回路有多少条？,(8),D,中长度,4通路有多少条？其中有几条是回路？,(9)写出,D,可达矩阵.,4有向图,D,如图所表示，,回答下列诸问：,练习,4,48,第48页,第48页,解答,(1),D,中有3种非同构圈，长度分别为1,2,3，请画出它们图形.,(2),D,中有3种非圈非同构简朴回路，它们长度分别为 4,5,6.请画出它们图形来.,(3),D,是强连通（为何？）,为解(4)(8)，只需先求,D,邻接矩阵前4次幂.,49,第49页,第49页,(4),v,1,到,v,4,长度为1,2,3,4通路数分别为0,0,2,2.其中只有长度为4两条是非初级简朴通路（定义意义下），见下图所表示.,解答,50,第50页,第50页,解答,(5),v,1,到,v,1,长度为1,2,3,4回路数分别为1,1,3,5.其中长度为1是初级(环)；长度为2是复杂；长度为3中有1条是复杂，2条是初级；长度为4有1条是复杂，有4条是非初级简朴回路.请在图中行遍以上各回路.,(6)长度为4通路(不含回路)为33条.,(7)长度为4回路为11条.,(8)长度,4通路88条，其中22条为回路.,(9)4,4全1矩阵.,51,第51页,第51页,