North China Electric Power University I 第六章图 ★基本术语 ★图的存储结构 ★图的遍历 ★最小生成树和最短路径问题 ★A0V网与拓扑排序 ★AOE网与关键路径
第六章 图 ★ 基本术语 ★ 图的存储结构 ★ 图的遍历 North China Electric Power University ★ 最小生成树和最短路径问题 ★ AOV网与拓扑排序 ★ AOE网与关键路径
North China Electric Power University I ★基本术语 图的定义 图是由顶点的非空有穷集合与顶点之间关系 (边或弧)的集合构成的结构,通常表示为 G=(V,E) 其中,V为顶点集合,E为关系(边或弧)的集合 华电计算机系
★基本术语 North China Electric Power University 图是由顶点的非空有穷集合与顶点之间关系 (边或弧)的集合构成的结构, 通常表示为 G = ( V, E) 其中, V 为顶点集合, E 为关系(边或弧)的集合. 一 .图的定义 华电计算机系
North China Electric Power University I 关于一条边或弧的表示方法 (1).用图形: )③③ (2).用符号: (3)用语言: (a).顶点v;与v;是这条边的两个邻接点 b).这条边依附于顶点v和v 华电计算机系
North China Electric Power University (b). 这条边依附于顶点vi 和vj。 (vi , vj ) vi vj vi vj vj vi vj vi 关于一条边或弧的表示方法: (a). 顶点vi 与vj 是这条边的两个邻接点。 (1). 用图形: (2). 用符号: (3). 用语言: 华电计算机系
North China Electric Power University I G1=(V1,E1) G2=(V2E2) 其中 其中 3v4 2 V 1V2,V3,V4 E1={(v1,v2),(v1,v3), 2={, (v1,4),(V2,v3) v2,v3>, V3.V 华电计算机系
North China Electric Power University 华电计算机系 v1 v2 v3 v4 其中 V1 = { v1, v2, v3, v4 } E1 = { (v1,v2), (v1,v3), (v1,v4), (v2,v3), (v2,v4), (v3,v4) } G1=(V1 , E1 ) v1 v2 v3 v4 其中 V2 = { v1, v2, v3, v4 } E2 = { , , , } G2=(V2 , E2 )
North China Electric Power University I 图的分类 无向图:对手(vW)EE必有(yWE,并且偶对中顶 点的前后顺序无关。 有向图:若<vy∈E是顶点的有序偶对。 网络):与边有关的数据称为权边上带权的图称为网络。 10 华电计算机系
North China Electric Power University 无向图： 有向图： 与边有关的数据称为权,边上带权的图称为网络。 二.图的分类 对于（vi ,vj)E,必有（vj ,vi )E，并且偶对中顶 点的前后顺序无关。 若E是顶点的有序偶对。 华电计算机系 网(络)： v1 v2 v3 v4 v1 v2 v3 v4 v1 v2 v3 v4 10 4 17 8
North China Electric Power University I 名词术语 1.顶点的度 依附于顶点v的边的数目记为TDG) 对于有向图而言,有: 顶点的出度: 以顶点v为出发点的边的数目记为OD(v) 顶点的入度 以顶点v为终止点的边的数目记为ID(v) TD(Vi=OD(Vi+ D(vi 华电计算机系
North China Electric Power University 1.顶点的度 对于有向图而言, 有: 顶点的出度: 以顶点vi 为出发点的边的数目,记为OD(vi). 顶点的入度: 以顶点vi 为终止点的边的数目,记为ID(vi). TD(vi) = OD(vi) + ID(vi) 三.名词术语 依附于顶点vi的边的数目,记为TD(vi ). 华电计算机系 v1 v3 v4 v1 v2 v3 v4 v2
North China Electric Power University I 结论 对于具有n个顶点c条边的圈有 2e=∑TD 具有n个顶点的无向图最多有m(n-1)2条边 具有n个顶点的有向图最多有m(n-1)条边 边的数目达到最大的图称为完全图边的数目达到 或接近最大的图称为稠密图否则称为稀疏图 华电计算机系
North China Electric Power University 边的数目达到最大的图称为完全图. 边的数目达到 或接近最大的图称为稠密图,否则,称为稀疏图. 具有n个顶点的有向图最多有n(n-1) 条边. 具有n个顶点的无向图最多有n(n-1)/2 条边. 对于具有n个顶点,e条边的图,有 2e = TD(vi ) n i=1 结论1 结论2 结论3 华电计算机系
North China Electric Power University I 2.路径 顶点v到v之间有路径P(,v的充分必要条件为:存在 顶点序列v,vn,v2,…,Vmy,并且序列中相邻两个顶点构 造的顶点偶对分别为图中的一条边。 P(A, E): A, B, E A. C.D.E 1出发点与终止点相同的路径称为回路或环:顶点序列中1 顶点不重复出现的路径称为简单路径。不带权的图的路径长 度是指路径上所经过的边的数目,带权的图的路径长度是指 路径上经过的边上的权值之和。 华电计算机系
North China Electric Power University 2. 路径 C D E B A P(A, E): A, B, E A, C, D, E 出发点与终止点相同的路径称为回路或环；顶点序列中 顶点不重复出现的路径称为简单路径。不带权的图的路径长 度是指路径上所经过的边的数目，带权的图的路径长度是指 路径上经过的边上的权值之和。 顶点vx到vy之间有路径P(vx, vy)的充分必要条件为: 存在 顶点序列 vx, vi1, vi2, …, vim, vy, 并且序列中相邻两个顶点构 造的顶点偶对分别为图中的一条边。 华电计算机系
North China Electric Power University I 3子图 对于图G=(V,E)与G′=(V,E"),若有VV,E'E, 则称G为G的一个子图 /华电计算机系
North China Electric Power University 3.子图 v1 v 2 v3 v4 对于图G=(V,E) 与 G´=(V´,E´), 若有V´ V, E´ E, 则称G´为G的一个子图. 华电计算机系 v1 v 2 v3 v4 v1 v 2
North China Electric Power University I 4图的连通 (1)无向图的连通 无向图中顶点v到v有路径则称顶点v与v是连通的。 若无向图中任意两个顶点都连通,则称该无向图是连 通的。 (2)有向图的连通 若有向图中顶点v到v有路径并且顶点v到v也有路 径则称顶点v与v是连通的。 若有向图中任意两个顶点都连通则称该有向图是强 连通的。 华电计算机系
North China Electric Power University 4.图的连通 无向图中顶点vi 到vj 有路径,则称顶点vi 与vj 是连通的。 若无向图中任意两个顶点都连通, 则称该无向图是连 通的。 若有向图中顶点vi 到vj 有路径,并且顶点vj 到vi 也有路 径,则称顶点vi 与vj 是连通的。 若有向图中任意两个顶点都连通,则称该有向图是强 连通的。 (1).无向图的连通 (2).有向图的连通 华电计算机系