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).有向图的连通 华电计算机系