6.有向图的顶点的出度、入度和度 在有向图中若<a,b>为图中的一条边则 称顶点a邻接到顶点b,顶点b邻接于顶点a, 边<a,b>与顶点a和b是相关联的。 邻接于a的顶点个数称为a顶点的出度;邻接 到b的顶点个数称为顶点b的入度;顶点a的出 度与入度之和称为顶点a的度。 简单地说:某个顶点的入度就是进入该顶点的 边的条数前驱数)某个顶点的出度就是离开该 顶点的边的条数(后继数) 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 在有向图中,若<ａ,ｂ>为图中的一条边,则 称顶点ａ邻接到顶点ｂ,顶点ｂ邻接于顶点ａ， 边<ａ,ｂ>与顶点ａ和ｂ是相关联的。 邻接于ａ的顶点个数称为ａ顶点的出度；邻接 到ｂ的顶点个数称为顶点b的入度；顶点ａ的出 度与入度之和称为顶点ａ的度。 简单地说：某个顶点的入度就是进入该顶点的 边的条数(前驱数）某个顶点的出度就是离开该 顶点的边的条数（后继数） ６．有向图的顶点的出度、入度和度
例如图6-1(a)的有向图中各顶点的出度、入度和度为 顶点 出度 入度 度 BCcD 0 131 332 7.子图 设有两个图G=(vE和G1=(1E1)如果图 G中的所有边E1都包含在图G的边的集合E中,且 图G1中的所有顶点v1都包含在图G的顶点的集合 V中,则称图G1为图G的子图。图6-2中G为一个 图的逻辑结构,而图GLG2为G的子图,显然任何 一个图的子图可以子图可以有多个 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 顶点 出度 入度 度 A 3 1 4 B 2 1 3 C 0 3 3 D 1 1 2 例如图6－１（ａ）的有向图中各顶点的出度、入度和度为： ７．子图 设有两个图G=(V,E) 和G1=(V1 ,E1 ) 如果图 G1中的所有边E1都包含在图G的边的集合E中，且 图G1中的所有顶点V1都包含在图G的顶点的集合 V中，则称图G1为图 G的子图。图6-2中G为一个 图的逻辑结构，而图G1 ,G2为G的子图，显然任何 一个图的子图可以子图可以有多个
A A A D B D 图6-2(c)子图2 D B 图6-2a)无向图G图6-2(b)子图1 图62无向国的部分子图62(0)7图3 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 A D B C A D B 图6－２（ａ）无向图G 图6－２（ｂ）子图１ C 图6－２（ｃ）子图２ 图6－２无向图的部分子图 图6－２（ｄ）子图３ A D C
8.路径与路径长度 对于一个图来说,从图中的某一个顶点x到 任意一个顶点y的路径是一个顶点序列x,x1 X r··· y但对于无向图而言,该序列应满足: (X1X1)应包含在E集合中而对于有向图该 序列应满足: (X1-1,X;)应包含在E集合中。 在路径上的边的条数称为路径长度。路径 上的第一个顶点与最后一个顶点相同时,称为 该图有回路。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 ８．路径与路径长度 对于一个图来说，从图中的某一个顶点ｘ到 任意一个顶点ｙ的路径是一个顶点序列ｘ,ｘ1, ｘ２,….ｙ.但对于无向图而言，该序列应满足: （XI-1 ,XI）应包含在E集合中;而对于有向图,该 序列应满足： （ｘi－1，ｘｊ）应包含在E集合中。 在路径上的边的条数称为路径长度。路径 上的第一个顶点与最后一个顶点相同时，称为 该图有回路
9.连通图与连通分量 在无向图中若顶点x到顶点y有路径,则称 x与y是连通的;图中的任意两个顶点都是 连通的无向图称为连通图。在无向图中的最 大的连通子图称为无向图的连通分量。 如图6-3所示。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 ９．连通图与连通分量 在无向图中若顶点ｘ到顶点ｙ有路径，则称 ｘ与ｙ是连通的；图中的任意两个顶点都是 连通的无向图称为连通图。在无向图中的最 大的连通子图称为无向图的连通分量。 如图6-3 所示