路径、路径长度 无向图中从顶点V到V的路径是一个顶点序列 (V=V1,0,V11,Vm=v),其中(N1Y∈E(G)。 在有向 图中路径也是有向的，它是由若干条弧组成。路径上 边或弧的数目称为路径长度。 V1 V1 V3 4 回
◼ 路径、路径长度 V0 V3 V4 V1 V2 V0 V1 无 向 图中从顶点 v到 v`的 路径是一个顶点序 列 (v=vi,0 ,vi,1 ,…,vi,m=v`)，其中(vi,j-1 ,vi,j)∈E(G) 。在有向 图中路径也是有向的，它是由若干条弧组成。路径上 边或弧的数目称为路径长度
回路、简单路径、简单回路 起点和终点相同的路径称为回路或者环。序列中 顶点不重复出现的路径称为简单路径。除第一个顶 点与最后一个顶点之外，其他顶点不重复出现的回 路称为简单回路。 无向图G1 有向图G2
◼ 回路、简单路径、简单回路 V0 V3 V4 V1 V2 V0 V2 V3 V1 无向图G1 有向图G2 起点和终点相同的路径称为回路或者环。序列中 顶点不重复出现的路径称为简单路径。除第一个顶 点与最后一个顶点之外，其他顶点不重复出现的回 路称为简单回路
·子图 若有两个图G和G°，G=(Y,E),G=(V,E), 满足 如下条件：VSV,EsE,即V为V的子集，E为E的 子集，称图G为图G的子图。 例(b)、(c)是(a)的子图 /1 V1 4 V3 V3 a 6 (c) 回
◼ 子图 V0 V3 V4 V1 V2 V0 V3 V4 V1 V2 V0 V3 V1 (a) (b) (c) 若有两个图G和G`，G=(V,E),G`=(V`,E` )， 满足 如下条件：V`V,E`E，即V`为V的子集, E`为E的 子集，称图G`为图G的子图。 例 (b)、(c) 是 (a) 的子图
连通图、连通分量 在无向图G中，如果从顶点v到顶点v有路径，则 称V和V是连通的。若图中任意两个顶点都是连通的， 则称G为连通图 无向图中的极大连通子图称该图的连通分量。 G2的两个 连通分量 /5 连通图G1 非连通图G2
◼ 连通图、连通分量 V0 V3 V4 V1 V2 V0 V3 V2 V1 V5 V4 连通图G1 非连通图G2 G2的两个 连通分量 在无向图G中，如果从顶点v到顶点v`有路径，则 称v和v`是连通的。若图中任意两个顶点都是连通的， 则称G为连通图。 无向图中的极大连通子图称该图的连通分量
强连通图、强连通分量 在有向图G中，如果对于任意一对顶点vj和vi均有 从一个顶点v到另一个顶点vi有路径，也有从vi到vj 的路径，则称该有向图是强连通图 有向图的极大强连通子图称为强连通分量。 V1 强连通图G1 非强连通图G2 G2的两个强 连通分量
◼ 强连通图、强连通分量 V0 V1 V2 V3 V0 V1 V2 V3 强连通图G1 非强连通图G2 V1 V0 V2 V3 G2的两个强 连通分量 在有向图G中，如果对于任意一对顶点vj和vi 均有 从一个顶点vj到另一个顶点vi有路径，也有从vi到 vj 的路径，则称该有向图是强连通图。 有向图的极大强连通子图称为强连通分量