图的定义和基本术语_第1页
图的定义和基本术语_第2页
图的定义和基本术语_第3页
图的定义和基本术语_第4页
图的定义和基本术语_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

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

文档简介

1、图的定义和基本术语数 据 结 构图图的定义和基本术语图：图G由V（G）和E（G）这两个集合所组成，记为G=（V，E），其中V（G）是顶点（Vertex）的非空集，每个顶点可以标以不同的字符或数字；E（G）是边（Edge）的集合，特殊情况下E（G）可以是空集。每个边由其所连接的两个顶点表示。无向图：对于一个图G，若边集合E（G）为无向边的集合，则称该图为无向图。有向图：对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。图图6.1 有向图与无向图无向图G1有向图G2图完全图：在一个有n个顶点的无向图中，若每个顶点到其它（n-1）个顶点都连有一条边，则图中共有n(n-1)/2条边，这种

2、图称为完全图（Complete graph，也称完备图）。左图所示就是n=4的完全图，它一共有六条边。 图权和网络：有些图， 对应每条边有一相应的数值，这个数值叫做该边的权(Weight)。边上带权的图称为带权图，也称为网络(Network)。子图：设有两个图G =(V,E)和G=(V,E)，若V(G)是V(G)的子集，且E(G)是E(G)的子集，则称G是G的子图(Subgraph)。例如图6.3所示的图是图6.1中G1的一些子图。 图图6.3 子图图顶点的度：图中与每个顶点相连的边数，叫该顶点的度(Degree)。例如图6.1的图G1中，顶点的度数为2，顶点的度数为3，。 入度、出度：对于有

3、向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。例如在图6.1的图G2中，顶点的入度为1，出度为2，而顶点的入度为1，出度为0，因为有一条边指向它，而没有边从它指出去。 图路径：在一个图中，若从某顶点Vp出发，沿一些边经过顶点V1,V2,Vm到达，Vq，则称顶点序列(Vp, V1,V2,Vm, Vq)为从Vp到Vq的路径(Path)。路径长度：对于无权的图，路径长度指的是沿此路径上边的数目；对于有权图，一般是取沿路径各边的权之和作为此路径的长度。若一条路径上各顶点均不重复，即路径经过每一顶点不超过一次，则此路径叫做简

4、单路径。如果从一个顶点出发又回到该顶点，即Vp与Vq相同，则此路径叫做环路（Cycle）。图连通、连通图：在无向图中，如果从顶点Vi到顶点Vj之间有路径，则称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图(Connected graph)。连通分量：例如图6.1中的图G1是连通图。图6.4中的图就是非连通图，非连通图的每一个极大连通子图叫连通分量(Connected Component)，此图包括二个连通分量。 图图6.4 非连通图G图强连通图和强连通分量：在有向图G中，如果从顶点Vi到顶点Vj和从顶点Vj到顶点Vi之间都有路径，则称这两个顶点是强连通的。如果图中任何一对顶点都是强连通的，则此图叫做强连通图。非强连通图的每一个极大强连通子图叫做强连通分

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

温馨提示

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

最新文档

评论

0/150

提交评论