离散数学课件第八章(第1讲).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论的应用,图论是一门应用性很强的学科。,20,世纪,60,年代以来，它在许多领域，如,物理学、生物学、计算机科学、信息论、运筹学,以及,语言学、社会科学,等有着广泛的应用。,图论在计算机科学中的应用：,最短通路、最小生成树、最大匹配、中国邮递员问题和旅行售货员等问题,的算法和计算机实现。,第八章 图,8.1,图的基本概念,8.2,路与图的连通性,8.3,图的矩阵表示,8.4,赋权图及最短路径,8.5,特殊的图,8.1,图的基本概念,离散数学所研究的图是不同于几何图形、机械图形的另一种数学结构,不关心图中,顶点的位置、边的长短和形状,只关心,顶点与边的联结关系。,如下图（,a,）和（,b,）可以认为是同一个图形。,a,b,c,d,e,1,e,2,e,6,e,4,e,3,e,5,（,a,）,a,b,c,d,e,1,e,6,e,2,e,4,e,3,e,5,（,b,）,a,b,c,d,e,1,e,2,e,6,e,4,e,3,e,5,（,1,）,图的定义,:,一个图,G,可用一个二元组,表示,其中,V(G),为顶点集合,E(G),是边的集合。,讨论定义：,(a)V(G)=V,1,，,V,2,，,，,V,n,为有限非空集合,V,i,称为顶点。,(b)E(G)=e,1,，,，,e,m,为有限的边集合,e,i,称为边,。,可用,e,或,e,(v,i,v,j,),来表示图的边。,（,2,）,无向图，有向图,每一条边都是无向边的图称无向图。,每一条边都是有向边的图称有向图。,b,c,d,a,b,c,d,a,例：将右图用二元组表示为：,，,其中,a,，,b,，,c,，,d,则：,，,=,a,，,b,，,c,，,d,，,（,3,）,邻接点，孤立结点,邻接点：,在一个图中，若两个结点有一条有向边或者一条无向边关联,则这两个结点称为邻接点。,孤立结点：,在一个图中不与任何结点相邻接的结点，称为孤立结点。如下图中结点,v,5,。,v,1,v,2,v,3,v,4,v,5,（,4,）,零图，平凡图,零图：,仅由孤立结点构成的图称为零图。如图,(a),平凡图：,仅由一个孤立结点构成的图称为平凡图。如图,(b),(a),(b),（,5,）,邻接边：,关联于同一结点的两条边称为邻接边。,（,6,）,自回路（环）：,关联于同一结点的一条边称为自 回路。,如下图，,e,4,=,是自回路（环）。,e,3,e,4,（,7,）,度数：,在图,G=,中，与结点,v,（,v,V,）关 联的边数，称为该结点的度数，记作,deg,（,v,）。,约定：,每个环在其对应结点上的度数增加,2,。,A,B,C,E,D,最大度,记为：,(G),=max,d,(,v,)|,v,V,最小度,记为：,(G),=min,d,(,v,)|,v,V,定理,1,(,握手定理,),：,每个图中，结点度数的总和等于边数的两倍。即,证：每条边必关联两个结点，而一条边给于关联的每个结点的度数为,1,。,故上述定理成立。,例：,在一次,10,周年同学聚会上，想统计所有人握手的次数之和，应该如何建立该问题的图论模型？,解：将每个同学分别作为一个节点，如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。,例：,无向图,G,有,6,条边，各有一个,3,度和,5,度节点，其余均为,2,度节点，求,G,的阶数。,解,:,设图,G,有,x,个节点度数为,2,，则,G,的阶数为,x+1+1=x+2,。,根据握手定理有：,3+5+2x=12,于是,x=2,，所以,G,的阶数为,2+2=4,。,定理,2,：,在任何图中，度数为奇数的结点必定是偶数个。,例：,是否,存在一个无向图，其度数序列分别,为,：,(1)5,，,4,，,4,，,3,，,3,，,2,，,2,(2)4,，,4,，,3,，,3,，,2,，,2,，,2,，,2,例：,设无向图,G,有,10,条边，,3,度和,4,度节点各,2,个，其余节点的度数均小于,3,，则,G,至少有多少个节点？在最少节点的情况下，求出,G,的度数序列、最大度,和最小度,。,（,8,）,入度，出度：,在有向图中，射入一个结点的边数称为该结点的入度。由一个结点射出的边数称为该结点的出度。,结点的出度与入度,和,是该结点的度数。,B,C,D,A,Deg,+,（,A,）,=2,Deg,-,（,A,）,=3,Deg,+,（,B,）,=3,Deg,-,（,B,）,=2,Deg,+,（,C,）,=1,Deg,-,（,C,）,=1,Deg,+,（,D,）,=1,Deg,-,（,D,）,=1,例：,一个,3,阶有向图的度序列是,2,，,2,，,4,，入度序列是,2,，,0,，,2,，出度序列是,.,b,c,d,a,证：,因为每一条有向边必对应一个入度和出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以，有向图中各结点入度和等于边数，各结点出度和也是等于边数，因此，任何有向图中，入度之和等于出度和。,定理,3,：,在任何有向图中，所有结点的入度和等于所有结点的出度之和。,（,9,）,平行边，多重图，简单图,连接于同一对结点间的多条边称为是平行边。,含有平行边的任何一个图称为多重图。,不含有平行边和环的图称作简单图。,a,a,b,c,（,b,）,a,a,b,c,（,a,）,e1,e2,（,10,）,无向完全图：,简单图,G=,中，若每一对结点间都有无向边存在，则称该图为无向完全图。,定理,4,：,n,个结点的无向完全图的边数为：,证明：在有,n,个结点的无向完全图中，任意两点间都有边连接，,n,个结点中任意取两点的组合为：,故有,n,个结点的无向完全图的边数为,例：有,9,个结点的无向完全图,K,9,的边数为？,（,11,）,补图：,给定一个图,G,，由,G,中所有结点和所有能使,G,成为完全图的添加边组成的图，称为,G,相对于完全图的补图，或简称为,G,的补图。记作。,如下图，（,a,）和（,b,）互为补图。,（,a,）,v1,v2,v5,v3,v4,（,b,）,v1,v2,v3,v4,v5,例：,对于,n,阶简单无向图,G,，若其边数为,m,，试计算,G,的补图,的边数。,（,12,）,子图：,设图,G=,，如果有图,G,=,，且,E,E,，,V,V,，则称,G,为,G,的子图。,如下图，（,b,）、（,c,）都是（,a,）的子图。,（,a,）,b,c,d,h,g,a,f,e,（,b,）,b,c,d,h,g,f,e,（,c,）,b,c,d,h,g,a,f,（,13,）,生成子图：,如果,G,的子图包含,G,的所有结点，则称该子图为,G,的生成子图。,如下图，（,b,）、（,c,）都是（,a,）的生成子图。,（,a,）,（,c,）,（,b,）,v2,v4,v2,v3,v1,v1,v3,v4,v1,v4,v2,v3,例：设,G=,与,G1=,是两个图，若,_,则,G1,为,G,的生成子图。,（,14,）,图同构,设图,G=,及图,G,=,，如果存在一双射函数,g,：,v,i,vi,且,e=,（,v,i,，,v,j,）是,G,的一条边，当且仅当,e,=,（,g,（,v,i,），,g,（,v,j,）是,G,的一条边，则称,G,与,G,同构，记作,GG,。,两个图同构的充要条件是：两个图的结点和边分别存在着一一对应的关系，且保持关联关系。,d,b,e,a,（,a,）,u,3,u,4,u,2,u,1,（,b,）,例：存在着一双射函数,g,：,g(a)=u,3,，,g(b)=u,1,，,g(e)=u,4,，,g(d)=u,2,，,且有：,分别与,一一对应,所以图,(a),与图,(b),是同构的关系。,两图同构的一些,必要条件,：,（,1,）结点数目相同。,（,2,）边数相等。,（,3,）度数相同的结点数目相同,这几个条件不是两个图同构的充分条件。下列两图，满足上述三个条件，但并不同构。,例：,说明,以下两组图不同构。,（,1,）,（,2,）,例：画出,4,阶,3,条边的所有非同构的无向简单图,.,1,1,1,3,1,1,2,2,0,2,2,2,解 总度数为,6,分配给,4,个顶点,最大度为,3,且奇度顶点数为偶数,有下述,3,个度数列,:,(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.,