第七章 图的定义和术语 1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,7,章 图,线性结构,：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。,树结构,：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下,(,层,),可以有,0,个或多个元素相联系，对上,(,层,),只有唯一的一个元素相关，,数据元素之间有明显的层次关系。,图,(,Graph,),是一种比线性表和树更为复杂的数据结构。,图,结构,：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能,相关。,7.1,图的,定义,和术语,V,1,V3,V2,V4,V1,V2,V5,V4,V3,图,7.1,图的示例,(a),有向图,G1(b),无向图,G2,(a),(b),7.1.1,图的定义和术语,顶点,（,Vertex),：在图中的数据元素通常称为顶点（,Vertex),。约定,V,表示顶点的有穷非空集合，,VR,表示两个顶点之间的关系的集合。,弧,（,Arc,）,：表示两个顶点v,和,w,之间存在一个关系，用,表示,顶点v,到,w,的一条弧,。,且称,v,为,弧尾,（,Tail,）或初始点，称,w,为,弧头,（,Head,）或终端点。此时的图称为,有向图,Digraph,）。其中，,顶点偶对,的,v,和,w,之间是,有序,的,。,无向图,(Undigraph),：若图关系集合中，顶点偶对,的,v,和,w,之间是,无序,的,，称图,G,是无向图,。,若,属于,VR,，必有,属于,VR,，即,VR,是对称的。,那么用（,v,w,）代替这两个有序对，表示,v,和,w,的一条,边,（,Edge,）。,如图7.1,：设有向图,G1,和无向图,G2,，形式化定义分别是：,G1=(V1,，,A,1),V1=,v1,v2,v3,v4,A,1=,G2=(V2,，,E2),V2=,v1,v2,v3,v4,v5,E2=(,v1,v2,),(,v1,v4,),(,v2,v3,),(,v2,v5,),(,v3,v1,),(,v3,v5,),V,1,V3,V2,V4,V1,V2,V5,V4,V3,图,7.1,图的示例,(a),有向图,G1(b),无向图,G2,(a),(b),完全无向图,：对于无向图，若图中顶点数为,n,，用,e,表示边的数目，则,e,0,，,n(n-1)/2,。具有,n(n-1)/2,条边的无向图称为完全无向图。,完全无向图另外的定义是：,对于无向图,G=(V,，,E),，若,v,i,，,v,j,V,，当,v,i,v,j,时，有,(v,i,v,j,),E,，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。,完全有向图对于有向图，若图中顶点数为,n,，用,e,表示弧的数目，则,e,0,，,n(n-1),。具有,n(n-1),条边的有向图称为完全有向图。,完全有向图另外的定义是：,对于有向图,G=(V,，,E),，若,v,i,，,v,j,V,，当,v,i,v,j,时，有,E,并且,E,，即图中任意两个不同的顶点间都有一条弧，这样的有向图称为,完全有向图,。,有很少边或弧的图（,enn,）的图称为,稀疏图,，反之称为,稠密图,。,权,(,Weight,),：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。,这种,带权的图称为,网,。,子图和生成子图,：,设有图,G=(V,，,E),和,GV,，,E),，若,V,V,且,E,E,，则称图,G,是,G,的,子图,；若,V,=,V,且,E,E,，则称图,G,是,G,的一个,生成子图,。,P7.2,对于无向图,G=(V,，,E),，若边,(v,w),E,，则称顶点,v,和,w,互为,邻接点,，即,v,和,w,相邻接。边,(v,w),依附,(,incident,),于,顶点v,和,w,，或者说,(v,w),和顶点,v,和,w,相关联,。,图,G,中,和,v,相关联,的边的数目称为顶点v,的,度,(,degree,),，记为,TD(v),。,例如,无向图,G2,。,TD(V1),，,TD(V2),，,TD(V3),，,TD(V4),，TD(V5),V1,V2,V5,V4,V3,G2,对于有向图,G=(V,，,E),，若有向弧,E,，则称顶点,v,“,邻接到,”顶点,w,，顶点,w“,邻接自,”顶点,v,，弧,与顶点,v,和,w,“,相关联,”。,对有向图,G=(V,，,E),，若,v,i,V,，图,G,中,以,顶点,v,作为尾或初始,的有向边,(,弧,),的数目称为顶点,v,的,出度,(,Outdegree,),，记为,OD(v),；,以,v,作为头或终点,的有向边,(,弧,),的数目称为顶点,v,的,入度,(,Indegree,),，记为,ID(v),。顶点,v,的,出度,与,入度,之和称为,v,的,度,，记为,TD(v),。即,TD(v)=OD(v)+ID(v),例如图,7.1,所示的无向图。,OD(v,1,),，,ID(,1,),，,TD(v,1,),；,OD(v,3,),，,ID(,3,),，,TD(v,1,),V,1,V3,V2,V4,(G1),一般地,，,如果顶点,v,i,在的度记为,TD(v,i,),，那么一个有,n,个顶点，,e,条边或弧的图，满足：,TD(v,i,)=2e,路径,(Path),：,对无向图,G=(V,，,E),，若从顶点,v,i,经过若干条边能到达,v,j,，称顶点,v,i,和,v,j,是,连通,的，又称顶点,v,i,到,v,j,有,路径,。,对有向图,G=(V,，,E),，从顶点,v,i,到,v,j,有,有向路径,，指的是从顶点,v,i,经过若干条有向边,(,弧,),能到达,v,j,。,路径的长度,：,路径上边或有向边(,弧,),的数目称为该路径的长度。,在一条路径中，若没有重复相同的顶点，该路径称为,简单路径,；第一个顶点和最后一个顶点相同的路径称为,回路,(,环,),；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为,简单回路,(,简单环,),。,连通图、图的连通分量,：对无向图,G=(V,，,E),，若,v,i,，,v,j,V,，又称顶点,v,i,到,v,j,有,路径,，,即,v,i,和,v,j,是连通的，则称图,G,是,连通图,，否则称为,非连通图,。若,G,是非连通图，则极大的连通子图称为,G,的,连通分量,。,例如,图,7.1(b),中的,G2,就是一个连通图。再例如图,7.3,所示。,P159,V1,V2,V5,V4,V3,G2,对有向图,G=(V,，,E),，若,v,i,，,v,j,V,，都有以,v,i,为起点，,v,j,为终点以及以,v,j,为起点，,v,i,为终点的有向路径，称图,G,是,强连通图,，否则称为,非强连通图,。若,G,是非强连通图，则极大的强连通子图称为,G,的,强连通分量,。,“,极大,”的含义：指的是对子图再增加图,G,中的其它顶点，子图就不再连通。,例如,图,7.1(a),。,V,1,V3V2,V4,(G1),V,1,V3,V2,V4,强连通分量,生成树、生成森林,：一个连通图,(,无向图,),的生成树是一个极小连通子图，它,含有图中全部,n,个顶点,和只有足以构成一棵树的,n-1,条边,，称为图的,生成树,。,如图,7.5,所示。,v1,v3,v2,v4,图,7-,5,生成树,关于无向图的生成树的几个结论：,一棵有,n,个顶点的生成树有且仅有,n-1,条边；,如果一个图有,n,个顶点和小于,n-1,条边，则是非连通图,；,如果多于,n-1,条边，则一定有环；,有,n-1,条边的图不一定是生成树。,v1,v3,v2,v4,图,7-,5,生成树,如果一个有向图恰有一个顶点的入度为,0,，其余顶点的入度均为,1,，则是一棵有向树，如图,7-3,所示。有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。,网：每个边,(,或弧,),都附加一个权值的图，称为带权图。带权的连通图,(,包括弱连通的有向图,),称为网或网络。如图,7-4,所示。,图,7-3,有向图及其生成森林,a,b,c,d,e,d,c,e,(a),有向图,(b),生成森林,a,c,b,c,b,3,5,4,1,2,6,a,b,c,d,e,3,图,7-4,带权有向图,7.1.2,图的抽象数据类型定义,图的抽象数据类型定义如下：,ADT Graph,数据对象,V,：具有相同特性的数据元素的集合，称为顶点集。,数据关系,R,：,R=VR,VR=|v,w,V,且,P(v,w,),，,表示 从,v,到,w,的弧，,P(v,w),定义了弧,的信息,基本操作,P,：,CreateGraph,(&G,V,VR),：图的创建操作。,初始条件：无。,操作结果：按,V,和,VR,的定义构造树,G,。,GetVex(G,v),：求图中的顶点,v,的值。,初始条件：图,G,存在，,v,是图中的一个顶点。,操作结果：返回,v,的值。,LocateVex(G,u);,初始条件：图,G,存在，,u,和,G,中顶点有相同特征。,操作结果：若,G,中存在顶点,u,，则返回该顶点在,图中“位置”；否则返回其它信息,PutVex(,初始条件：图,G,存在，,v,是,G,中某个顶点。,操作结果：,对,v,赋值,value,。,ADT Graph,详见,p156157,。,习 题 七,分析并回答下列问题：,图中顶点的度之和与边数之和的关系,?,有向图中顶点的入度之和与出度之和的关系,?,具有,n,个顶点的无向图，至少应有多少条边才能确保是一个连通图,?,具有,n,个顶点的有向图，至少应有多少条弧才能确保是强连通图的,?,为什么,?,设一有向图,G=(V,E),，其中,V=a,b,c,d,e,，,E=,请画出该有向图，并求各顶点的入度和出度。,