第7章--图.ppt

2000年1月25日 北京理工大学 / 7.1 图的定义与术语 一、图的定义 1、图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对。 图的分类 有向图 无向图 7.1 图的定义与术语 2、有向图——有向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头。 7.1 图的定义与术语 例如： G1 = V1,E1 V1 = { A, B, C, D, E } E1 = {A,B, A,E, B,C, C,D, D,B, D,A, E,C } 7.1 图的定义与术语 3、无向图——无向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是边的有限集合，边是顶点的无序对，记为 (v,w) 或 (w,v)，并且(v,w)=(w,v)。 7.1 图的定义与术语 例如： G2 = V2,E2 V2 = { v0 ,v1,v2,v3,v4 } E2 = { (v0,v1), (v0,v3), (v1,v2), (v1,v4),  (v2,v3), (v2,v4) } 7.1 图的定义与术语 例如： G2 = V2,E2 V2 = { v0，v1，v2，v3 } E2 = { v0,v1 , v0,v2 , v2,v3 , v3,v0 } 7.1 图的定义与术语 图的应用举例 例1、交通图（公路、铁路） 顶点：地点 边：连接地点的路 例2、电路图 顶点：元件 边：连接元件之间的线路 例3、通讯线路图 顶点：地点 边：地点间的连线 例4、各种流程图 如产品的生产流程图。 顶点：工序 边：各道工序之间的顺序关系 7.1 图的定义与术语 二、图的基本术语 1、邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关联边e 2、顶点的度、入度、出度 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点V的出度 = 以V为起点有向边数 顶点V的入度 = 以V为终点有向边数 顶点V的度 = V的出度+V的入度 设图G 的顶点数为 n，边数为 e 图的所有顶点的度数和 = 2*e （每条边对图的所有顶点的度数和“贡献”2度） 7.1 图的定义与术语 3、路径、回路 无向图 G =（V，E）中的顶点序列v1, v2, …, vk，若 (vi, vi+1)?E ( i=1, 2, …, k-1)，v=v1, u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。 7.1 图的定义与术语 3、路径、回路 有向图 D =（V，E）中的顶点序列 v1, v2, …, vk，若 vi, vi+1?E (i=1, 2, …, k-1)，v=v1，u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。 7.1 图的定义与术语 4、连通图（强连通图） 在无（有）向图 G= V, E 中，若对任何两个顶点 v、u 都存在从 v 到 u 的路径，则称G是连通图（强连通图） 7.1 图的定义与术语 5、子图 设有两个图 G=（V，E），G1=（V1，E1），若V1? V，E1 ? E，而且E1关联的顶点都在 V1 中，则称 G1 是 G 的子图； 7.1 图的定义与术语 6、连通分量（强连通分量）：无（有）向图的极大（强）连通子图。 极大（强）连通子图：该子图是（强）连通子图，若再将G的任何不在该子图中的顶点加入，子图就不再（强）连通。 7.1 图的定义与术语 7.1 图的定义与术语 7、生成树 包含无向图 G 所有顶点的极小连通子图称为G生成树。 极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。 7.2 图的存储结构 一、数组表示法（邻接矩阵表示） 邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵： 7.2 图的存储结构 二、邻接表：图的链式存储结构 1、无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中； 关联