无论有向图还是无向图,图中的每条边均关联于两 个顶点,因此,顶点数n、边数e和度数之间有如下 关系: =∑D) (式8-1) 四、子图 给定两个图G和G1,其中G=(V,E),G= (M,E),若满足V,EcE,则称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的 子图
子图示例 4 (a)无向图G3的部分子图 V2)、~V3 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 且( 均属于E(G),则称该顶点序列为顶点到顶点u的 一条路径,相应地,顶点序列u、m'、Mn1 V是顶点u到顶点Ⅵ一条路径。 如果G是有向图,路径也是有向的,它由E(G) 中的有向边<V,V1>、<1’,V2 <vn,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>组 成。路径长度是该路径上边或弧的数目
如果一条路径上除了起点和终点相同外,其余 顶点均不相同,则称此路径为一条简单路径。起点和 终点相同(V=u)的简单路径称为简单回路或简单环。 连通图与强连通图 在无向图G中,若从页点到顶点v有路径,则 称与v是连通的。若∨(G)中任意两个不同的顶 点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到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