离散数学-耿素云PPT(第5版)5.1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,图论,2,图论部分,第,5,章 图的基本概念,第,6,章 特殊的图,第,7,章 树,3,第,5,章 图的基本概念,5.1,无向图及有向图,5.2,通路,回路和图的连通性,5.3,图的矩阵表示,5.4,最短路径,关键路径和着色,4,5.1,无向图及有向图,无向图与有向图,顶点的度数,握手定理,简单图,完全图,子图,补图,5,无向图,多重集合,:,元素可以重复出现的集合,无序积,:,A,B,=(,x,y,)|,x,A,y,B,定义 无向图,G,=,其中,(1),顶点集,V,是非空有穷集合,其,元素称为,顶点,(2),边集,E,为,V,V,的多重子集，,其元素称为,无向边,，简称,边,.,例如,G,=,其中,V,=,v,1,v,2,v,5,E,=(,v,1,v,1,),(,v,1,v,2,),(,v,2,v,3,),(,v,2,v,3,),(,v,2,v,5,),(,v,1,v,5,),(,v,4,v,5,),6,有向图,定义 有向图,D,=,其中,(1),顶点集,V,是非空有穷集合,其元素称为,顶点,(2),边集,E,为,V,V,的多重子集，其,元素称为,有向边,，简称,边,.,D,的,基图,:,用无向边代替有向边,如,D,=,其中,V,=,a,b,c,d,E,=,图的数学定义与图形表示,在同构意义下,一一对应,7,无向图与有向图,(,续,),通常用,G,表示无向图,D,表示有向图,也常用,G,泛指,无向图和有向图,.,V,(,G,),E,(,G,),V,(,D,),E,(,D,):,G,和,D,的顶点集,边集,.,n,阶图,:,n,个顶点的图,零图,:,E,=,平凡图,:1,阶零图,空图,:,V,=,8,顶点和边的关联与相邻,定义,设,e,=(,u,v,),是无向图,G,=,的一条边,称,u,v,为,e,的,端点,e,与,u,(,v,),关联,.,若,u,v,则称,e,与,u,(,v,),的,关联次数为,1,;,若,u=v,则,称,e,为,环,此时称,e,与,u,的,关联次数为,2,;,若,w,不是,e,端点,则称,e,与,w,的,关联次数为,0,.,无边关联的顶点称作,孤立点,.,定义,设无向图,G,=,u,v,V,e,e,E,若,(,u,v,),E,则称,u,v,相邻,;,若,e,e,至少有一个公共端点,则称,e,e,相邻,.,对有向图有类似定义,.,设,e,=,u,v,是有向图的一条边,又称,u,是,e,的,始点,v,是,e,的,终点,u,邻接到,v,v,邻接于,u,.,9,顶点的度数,设,G,=,为无向图,v,V,v,的度数,(,度,),d,(,v,),:,v,作为边的端点次数之和,悬挂顶点,:,度数为,1,的顶点,悬挂边,:,与悬挂顶点关联的边,G,的最大度G,),=max,d,(,v,)|,v,V,G,的最小度,(,G,),=min,d,(,v,)|,v,V,例如,d,(,v,5,)=3,d,(,v,2,)=4,d,(,v,1,)=4,(,G,)=4,(,G,)=1,v,4,是悬挂顶点,e,7,是悬挂边,e,1,是环,10,顶点的度数,(,续,),设,D,=,为有向图,v,V,v,的出度,d,+,(,v,),:,v,作为边的始点次数之和,v,的入度,d,(,v,),:,v,作为边的终点次数之和,v,的度数,(,度,),d,(,v,),:,v,作为边的端点次数之和,d,(,v,)=,d,+,(,v,)+,d,-,(,v,),D,的最大出度,D,),=max,d,+,(,v,)|,v,V,最小出度,+,(,D,),=min,d,+,(,v,)|,v,V,最大入度,(,D,),=max,d,(,v,)|,v,V,最小入度,(,D,),=min,d,(,v,)|,v,V,最大度,(,D,),=max,d,(,v,)|,v,V,最小度,(,D,),=min,d,(,v,)|,v,V,11,例,例,d,+,(,a,)=4,d,-,(,a,)=1,d,(,a,)=5,d,+,(,b,)=0,d,-,(,b,)=3,d,(,b,)=3,+,(,D,)=4,+,(,D,)=0,(,D,)=3,(,D,)=1,(,D,)=5,(,D,)=3.,12,图论基本定理,握手定理,定理,任意无向图和有向图的所有顶点度数之和都等于边数的,2,倍,并且有向图的所有顶点入度之和等于出度之和等于边数,.,证,G,中每条边（包括环）均有两个端点，所以在计算,G,中各顶点度数之和时，每条边均提供,2,度，,m,条边共提供,2,m,度,.,有向图的每条边提供一个入度和一个出度,故所有顶点入度之和等于出度之和等于边数,.,推论,任意无向图和有向图的奇度顶点个数必为偶数,.,13,图的度数列,设无向图,G,的顶点集,V,=,v,1,v,2,v,n,G,的度数列,:,d,(,v,1,),d,(,v,2,),d,(,v,n,),如右图度数列,:4,4,2,1,3,设有向图,D,的顶点集,V,=,v,1,v,2,v,n,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,),如右图度数列,:5,3,3,3,出度列,:4,0,2,1,入度列,:1,3,1,2,14,握手定理的应用,例,1(3,3,3,4),(2,3,4,6,8),能成为图的度数列吗,?,解 不可能,.,它们都有奇数个奇数,.,例,2,已知图,G,有,10,条边,4,个,3,度顶点,其余顶点的度数均小于等于,2,问,G,至少有多少个顶点,?,解,设,G,有,n,个顶点,.,由握手定理,4,3+2(,n,-4)210,解得,n,8,15,握手定理的应用,(,续,),例,3,证明不存在具有奇数个面且每个面都具有奇数条棱的多面体,.,证 用反证法,.,假设存在这样的多面体,作无向图,G,=,其中,V,=,v,|,v,为多面体的面,E,=(,u,v,)|,u,v,V,u,与,v,有公共的棱,u,v,.,根据假设,|,V,|,为奇数且,v,V,d,(,v,),为奇数,.,这与握,手定理的推论矛盾,.,16,多重图与简单图,定义,(1),在无向图中,如果有,2,条或,2,条以上的边关联同一对顶点,则称这些边为,平行边,平行边的条数称为,重数,.,(2),在有向图中,如果有,2,条或,2,条以上的边具有相同的始点和终点,则称这些边为,有向平行边,简称,平行边,平行边的条数称为,重数,.,(3),含平行边的图称为,多重图,.,(4),既无平行边也无环的图称为,简单图,.,注意,:,简单图是极其重要的概念,17,实例,e,5,和,e,6,是平行边,重数为,2,不是简单图,e,2,和,e,3,是平行边,重数为,2,e,6,和,e,7,不是平行边,不是简单图,18,图的同构,定义,设,G,1,=,G,2,=,为两个无向图,(,有,向图,),若存在双射函数,f,:,V,1,V,2,使得对于任意的,v,i,v,j,V,1,(,v,i,v,j,),E,1,（,E,1,）当且仅当,(,f,(,v,i,),f,(,v,j,),E,2,（,E,2,），,并且,(,v,i,v,j,),（,）与,(,f,(,v,i,),f,(,v,j,),（,）,的重数相同，则称,G,1,与,G,2,是,同构,的，记作,G,1,G,2,.,同构实例,19,彼得森图,例,1,证明下述,2,对图是同构的,20,同构实例,(,续,),例,2,试画出,4,阶,3,条边的所有非同构的无向简单图,例,3,判断下述每一对图是否同构,:,(1),度数列不同,不同构,21,同构实例,(,续,),(2),(3),不同构,入,(,出,)度列不同,不同构,(,左边没有三角形,右边有三角形,),注意,:,度数列相同,(1)(2),22,图的同构,(,续,),几点说明：,图之间的同构关系具有自反性、对称性和传递性,.,能找到多条同构的必要条件,但它们都不是充分条件,:,边数相同，顶点数相同,度数列相同,(,不计度数的顺序,),对应顶点的关联集及邻域的元素个数相同，等等,若破坏必要条件，则两图不同构,至今没有找到判断两个图同构的多项式时间算法,23,完全图,n,阶无向完全图,K,n,:,每个顶点都与其余顶点相邻的,n,阶无向简单图,.,简单性质,:,边数,m,=,n,(,n,-1)/2,=,=,n,-1,n,阶有向完全图,:,每对顶点之间均有两条方向相反的有向边的,n,阶有向简单图,.,简单性质,:,边数,m,=,n,(,n,-1),=,=2(,n,-1),+,=,+,=,-,=,-,=,n,-1,K,5,3,阶有向完全图,24,子图,定义,设,G,=,G,=,是两个图,(1),若,V,V,且,E,E,则称,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,为顶点集,以两端点都在,V,中的所有边为边集的,G,的子图称作,V,的导,出子图,，记作,G,V,(5),设,E,E,且,E,以,E,为边集,以,E,中边关联的,所有顶点为顶点集的,G,的子图称作,E,的导出子,图,记作,G,E,25,生成子图实例,K,4,的所有非同构的生成子图,导出子图实例,26,G,D,G,v,1,v,2,G,e,1,e,3,e,4,D,e,1,e,3,D,v,1,v,2,27,补图,定义,设,G,=,为,n,阶无向简单图，以,V,为顶点集,所有使,G,成为完全图,K,n,的添加边组成的集合为边集的图，称为,G,的,补图,，记作,.,若,G,则称,G,是,自补图,.,例 对,K,4,的所有非同构子图,指出互为补图的每一对子图,并指出哪些是自补图,.,