71图的定义和术语 A A B A A B B C B D (a)无向完全图 (b)有向完全图 图73完全图 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 A B C A C B D A B C A C B D （a）无向完全图 （b）有向完全图 图7.3 完全图
71图的定义和术语 设G=<V,E>是一个图,若E'是E的子集,V是ⅴ的子集 ,且E'中的边仅与V中顶点相关联,则图G′=(V,E)称 为图G的子图( (subgraph) (a)无向图G (b)有向图G2 (a)无向图G的若干子图 b)有向图G2的若千子图 图74图72的若于子图 “十一五”国家级规划教材。张铭,王胳蚊,赵嗨￡,《数捃豬构与算法》,高教社,20〗.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 设G = <V,E>是一个图，若E′是E的子集，V′是V的子集 ，且E′中的边仅与V′中顶点相关联，则图G′= (V′,E′)称 为图G的子图(subgraph)。 v0 v0 v2 v3 v1 v4 v0 v2 v3 v0 v1 v3 （a）无向图 G1的若干子图 （b）有向图 G2的若干子图 图7.4 图7.2的若干子图 v0 v2 v3 v1 v4 v0 v2 v1 v3 (a) 无向图G1 (b) 有向图G2
71图的定义和术语 无向图G=<V,E>中从顶点vp到顶点vq的路径(path)是 个顶点序列(vp=vm,vn,v2,…,vm=v),其中(v1 ,v;)∈E,1≤j≤m。若G是有向图,则路径也是有向的 ,顶点序列应满足1,v>∈E,1≤j≤m 路径长度( length)定义为路径上的边(或弧)的数目 第一个顶点和最后一个顶点相同的路径称为回路或环 (cycle) 序列中顶点不重复出现的路径称为简单路径( simple path) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 无向图G = <V,E>中从顶点vp到顶点vq的路径(path)是一 个顶点序列(vp = vi0，vi1，vi2，…，vim = vq )，其中(vij-1 ，vij)∈E，1 ≤ j ≤ m。若G是有向图，则路径也是有向的 ，顶点序列应满足<vij-1，vij>∈E，1 ≤ j ≤ m ◼ 路径长度(length)定义为路径上的边（或弧）的数目 ◼ 第一个顶点和最后一个顶点相同的路径称为回路或环 (cycle) ◼ 序列中顶点不重复出现的路径称为简单路径(simple path)
71图的定义和术语 除了第一个顶点和最后一个顶点外,其余顶点不重复 的回路,称为简单回路( simple cycle) 不带回路的图称为无环图 acyclic graph) 不带回路的有向图称为有向无环图( directed acyclic graph,简记为DAG) 一个有向图中,若存在一个顶点v,从此顶点有路径 可以到达图中其他所有顶点,则称此有向图为有根的 图,v称作图的根 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 除了第一个顶点和最后一个顶点外，其余顶点不重复 的回路，称为简单回路(simple cycle) ◼ 不带回路的图称为无环图(acyclic graph) ◼ 不带回路的有向图称为有向无环图(directed acyclic graph，简记为DAG) ◼ 一个有向图中，若存在一个顶点v0，从此顶点有路径 可以到达图中其他所有顶点，则称此有向图为有根的 图，v0称作图的根
71图的定义和术语 在无向图中,如果从顶点v到顶点v;有路径,则称v和v是连通的 (connected) 如果对于图中的任意两个顶点vnv∈V,v和v都是连通的,则称无向 图G为连通图。 连通分量( connected component)定义为无向图中的极大连通子图。 (a)非连通的无向图G3 (b)非连通无向图G3的连通分量 图75非连通无向图的连通分量示意图 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj是连通的 (connected)。 ◼ 如果对于图中的任意两个顶点vi ,vj∈V，vi和vj都是连通的，则称无向 图G 为连通图。 ◼ 连通分量(connected component)定义为无向图中的极大连通子图。 v0 v2 v1 v3 v5 v6 v7 v8 v4 v0 v2 v1 v3 v5 v6 v7 v8 v4 (a) 非连通的无向图G3 （b） 非连通无向图G3的连通分量 图7.5 非连通无向图的连通分量示意图