数据结构-基于C++语言（微课版） 课件 2-图的术语_第1页
数据结构-基于C++语言（微课版） 课件 2-图的术语_第2页
数据结构-基于C++语言（微课版） 课件 2-图的术语_第3页
数据结构-基于C++语言（微课版） 课件 2-图的术语_第4页
数据结构-基于C++语言（微课版） 课件 2-图的术语_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

完全图、权、子图顶点的度、出度、入度本节目录：本节内容：图的术语图的基本概念路径、路径长度、简单路径连通图与连通分量完全无向图：在有n个顶点的无向图中，有n(n-1)/2条边。完全有向图：在有n个顶点的有向图中，有n(n-1)条弧。图的术语AG1完全无向图G2完全有向图ABC权：在某些图中，边或弧上有与它相关的数，称为权，权用于表示从一个顶点到另一个顶点距离、所需的时间或耗费。网络：带权的图称为网络。图的术语北京上海南京济南徐州280500320180160600260200青岛大连200子图：如果图G(V,E)和图G'(V',E')，满足V'

V，E'

E，则称G'为G的子图。图的术语1203子图356245136(a)(b)(c)103(d)1203(e)203(f)顶点的度：无向图中，顶点v的度是与顶点v相连的边数，记作TD(v)有向图中，顶点v的度分成入度与出度入度：以顶点v为终点的有向边的条数，记作ID(v)出度：以顶点v为始点的有向边的条数，记作OD(v)顶点v的度等于该顶点入度和出度之和，即：TD(v)=ID(v)+OD(v)图的术语图的术语245136G2顶点1入度：1，出度：1顶点2入度：1，出度：3顶点3入度：2，出度：1顶点4入度：1，出度：0顶点5入度：1，出度：1顶点6入度：1，出度：1157324G16顶点1的度：2顶点2的度：4顶点3的度：2顶点4的度：1顶点5的度：3顶点6的度：1顶点7的度：1一般的，若图G中有n个顶点、e条边，则有如下关系：e=(TD(v1)+TD(v2)+...+TD(vn))/2图的术语路径：从顶点vi出发，经过一些顶点vp1,vp2,...,vpk，到达顶点vj所经过的顶点序列。该序列(vi,vp1,vp2,...,vpk,vj)称为从顶点vi到顶点vj的路径。路径长度：路径上边的数目或路径上各边的权值之和。简单路径：路径上各顶点均不相同的路径。回路(环)：路径上第一个顶点和最后一个顶点相同的路径。路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1245136G11573246路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1图的术语图的术语连通：在无向图中，若从顶点v到顶点w有路径，则称顶点v和w是连通的。连通图：无向图中任意两个顶点都是连通的。连通分量：非连通图的极大连通的子图。67813245(a)非连通图13245(b)连通分量678图的术语强连通：在有向图中，若对于顶点v和w，存在一条从v到w和从w到v的路径，则称顶点v和w是强连通。强连通图：有向图中任意两个顶点都是强连通的。强连通分量：非强连通图的极大强连通的子图。G1强连通图123G2非强连通图24

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论