无论有向图还是无向图,图中的每条边均关联于两 个顶点,因此,顶点数、边数e和度数之间有如下 关系 ∑D(v) (式8-1) i=1 四、子图 给定两个图G和G1,其中G=(V,E),G= (Y,E),若满定V≌,Ec与,则称G是G的 子图
无论有向图还是无向图，图中的每条边均关联于两 个顶点，因此，顶点数n、边数e和度数之间有如下 关系： = n i i D v 1 ( ) 2 1 e= ……….（式8-1） 四、子图 给定两个图Gi和Gj，其中Gi=（Vi，Ei），Gj= （Vj，Ej），若满足ViVj，EiEj，则称Gi是Gj的 子图
子图示例 2 (a)无向图G3的部分子图 v2∨3 (b)有向图G的部分子图
v1 v2 v4 v2 v3 v4 v1 v2 v3 v4 v1 v4 v2 v3 v4 v1 v1 v2 v3 v4 子图示例 （a）无向图G3的部分子图 （b）有向图G4的部分子图
五、路径 无向图G中若存在着一个顶点序列v、V 且( V u 均属于E(G),则称该顶点序列为顶点到顶点u的 条路径,相应地,顶点序列u、n、1 V是顶点u倒到顶点Ⅵ的一条路径。 如果G是有向图,路径也是有向的,它由E(G) 中的有向边<V,V1 v, V2 ,U>组 成。路径长度是该路径上边或弧的数目
五、路径 无向图G中若存在着一个顶点序列v、v1 ’ 、v2 ’ 、…、 vm ’ 、u，且（v，v1 ’）、（v1 ’ ，v2 ’）、…、（vm ’ ，u） 均属于E（G），则称该顶点序列为顶点v到顶点u的 一条路径，相应地，顶点序列u、vm ’ 、vm-1 ’ 、…、v1 ’ 、 v是顶点u到顶点v的一条路径。 如果G是有向图，路径也是有向的，它由E（G） 中的有向边<v，v1 ’> 、<v1 ’ ，v2 ’> 、…、<vm ’ ，u>组 成。路径长度是该路径上边或弧的数目
如果一条路径上除了起点Ⅶ和终点u相同外,其余 顶点均不相同,则称此路径为一条简单路径。起点和 终点相同(v=u)的简单路径称为简单回路或简单环。 连通图与强连通图 在无向图G中,若从页点到顶点v有路径,则 称与v是连通的。若∨(G)中任意两个不同的顶 点v和v都连通(即有路径),则称G为连通图。例 如,图81(b)所示的无向图G2、图8.2(a)所示 的无向图G3是都是连通图。 无向图G的极大连通子图称为G的连通分量。 根据连通分量的定义,可知任何连通图的连通分量 是其自身,非连通的无向图有多个连通分量
如果一条路径上除了起点v和终点u相同外，其余 顶点均不相同，则称此路径为一条简单路径。起点和 终点相同（v=u）的简单路径称为简单回路或简单环。 六、连通图与强连通图 在无向图G中，若从顶点vi到顶点vj有路径，则 称vi与vj是连通的。若V（G）中任意两个不同的顶 点vi和vj都连通（即有路径），则称G为连通图。例 如，图8.1（b）所示的无向图G2、图8.2（a）所示 的无向图G3是都是连通图。 无向图G的极大连通子图称为G的连通分量。 根据连通分量的定义，可知任何连通图的连通分量 是其自身，非连通的无向图有多个连通分量
例:非连通图及其连通分量示例 (a)非连通图Gs (b)G5的两个连通分量H和H2 在有向图G中,若对于V(G)中任意两个不同的 顶点V和v,都存在从到v以及从v到v的路径,则称 G是强连通图
例：非连通图及其连通分量示例 （a）非连通图G5 （b）G5的两个连通分量H1和H2 在有向图G中，若对于V（G）中任意两个不同的 顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称 G是强连通图。 V1 V2 V4 V5 V3 V1 V2 V4 V5 V3