资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第8章图,8.1图的基本概念,8.2图的存储结构,8.3图的過历,8.4生成树和最小生成树,8.5最短路怪,8.6拓扑排序,8.7AOE网与关键路径,Valadon onry.,ch Asposeslides for NET 4o dient P,Evaluation only.,Created with Aspose Slides for NET 4.0 dient Profilo,71,Copyright 2019-2019Aspose Pty L,图的示例,顶点,弧,边,结点之间的关系:,多对多,任意两个结点之间都可能有关系存在,Valadon onry.,ch Asposeslides for NET 4o dient P,Evaluation only.,Created with Aspose Slides for NET 4.0 dient Profilo,71,Copyright 2019-2019Aspose Pty L,图的抽象数据类型,ADT Graphi,数据对象:D=alj-n,n0,a属 ElemType类型,数据关系:R=lai,jD,l,则称此边是顶点v的一条出,边同时也是顶点v的一条入边,称v和v分别为此边的起始端点,(简称为起点)和终止端点(简称终点);,(b),称v和v互为邻接点。,5,Valadon onry.,ch Asposeslides for NET 4o dient P,Evaluation only.,Created with Aspose Slides for NET 4.0 dient Profilo,71,Copyright 2019-2019Aspose Pty L,2顶点的度、入度和出度,在无向图中,顶点所具有的边的,数目称为该顶点的度。,在有向图中,以顶点v为终点的,入边的数目称为该顶点的入度,以顶点v为始点的出边的数目,称为该顶点的出度。,个顶点的入度与出度的和为该,顶点的度。,若一个图中有n个顶点和e条边,每个顶点的度为d(1m),则有:,d,2,Valadon onry.,ch Asposeslides for NET 4o dient P,Evaluation only.,Created with Aspose Slides for NET 4.0 dient Profilo,71,Copyright 2019-2019Aspose Pty L,3.完全图,若无向图中的每两个顶点之间,都存在着一条边,有向图中的每,两个顶点之间都存在着方向相反,(a),的两条边,则称此图为完全图。,完全无向图包含有n(m-1)/2条边,完全有向图包含有n(n-1)条边。,Valadon onry.,ch Asposeslides for NET 4o dient P,Evaluation only.,Created with Aspose Slides for NET 4.0 dient Profilo,71,Copyright 2019-2019Aspose Pty L,4.稠密图、稀疏图,当一个图接近完全图时,则称,为稠密图。相反,当一个图含有,较少的边数(即当en(n-1)时,则称为稀疏图。,5.子图,设有两个图G=(V,E)和,=(V,E),若V是V的子集,即,V,且E是E的子集,即,EcE,则称G是G的子图,例如图(b)是图(a)的子图,而图,(c)不是图a)的子图。,Valadon onry.,ch Asposeslides for NET 4o dient P,Evaluation only.,Created with Aspose Slides for NET 4.0 dient Profilo,71,Copyright 2019-2019Aspose Pty L,6.路径和路径长度(略),在一个图G=(E)中,从顶点v到顶点y的一条路径是。,个顶点序列(vm,V2x,Vmy);,若此图G是无向图,则边(v,V1,(V1,m),(Ymy)属于E(G),若此图是有向图,则,属于E(G)。,路径长度是指一条路径上经过的边的数目。,若一条路径上除开始点和结束点可以相同外,其余,顶点均不相同,则称此路径为简单路径。,例如,(vo,2,就是一条简单路径,其长度为2。,Valadon onry.,ch Asposeslides for NET 4o dient P,Evaluation only.,Created with Aspose Slides for NET 4.0 dient Profilo,71,Copyright 2019-2019Aspose Pty L,7.回路或环(略),若一条路径上的开始点与结束,点为同一个顶点,则此路径被称为,回路或环。,开始点与结束点相同的简单路,径被称为简单回路或简单环。,例如,(vnV2Y1,0)就是一条简,单回路,其长度为3。,10,Valadon onry.,ch Asposeslides for NET 4o dient P,Evaluation only.,Created with Aspose Slides for NET 4.0 dient Profilo,71,Copyright 2019-2019Aspose Pty L,
展开阅读全文