4.稠密图、稀疏图 当一个图接近完全图时,则称为稠 密图。相反,当一个图含有较少的边 4 数即当e<n(n-1)时则称为稀疏图。 5.子图 3)(0)(b) 设有两个图G=(VE)和G=(V,E”), 若V是Ⅴ的子集,即VV,且E是E的 4 子集,即EE,则称G是G的子图。 例如图(b)是图(a)的子图而图()不 ① 是图(a)的子图
4. 稠密图、稀疏图 当一个图接近完全图时,则称为稠 密图。相反,当一个图含有较少的边 数(即当e<<n(n-1))时,则称为稀疏图。 5. 子图 设有两个图G=(V,E)和G’=(V’,E’), 若V’是V的子集,即V’V,且E’是E的 子集,即E’E,则称G’是G的子图。 例如图(b)是图(a)的子图,而图(c)不 是图(a)的子图。 1 2 3 0 4 (a) (b) 1 2 3 0 4 1 2 3 0 4 (c)
6.路径和路径长度 在一个图G=(VE)中,从顶点v到顶点v 的一条路径是一个顶点序列 (vpyn,y2…,imy)若此图G是无向图,则边 (vpn),(vn,ya),…,(vm1,ym)vm3y)属于E(G) 若此图是有向图则<v1,V1>,<Vny23,…,Vm nYm3vmy属于E(G) 路径长度是指一条路径上经过的边的 数目。若一条路径上除开始点和结束点可 以相同外,其余顶点均不相同,则称此路径为 简单路径。例如,有图中v21)就是一条 简单路径其长度为2
6. 路径和路径长度 在一个图G=(V,E)中,从顶点vi到顶点vj 的一条路径是一个顶点序列 (vi ,vi1 ,vi2 ,…,vim,vj ),若此图G是无向图,则边 (vi ,vi1 ),(vi1 ,vi2 ),…,(vim-1 ,vim),(vim,vj )属于E(G)； 若此图是有向图,则<vi ,vi1>,<vi1 ,vi2>,…,<vim- 1 ,vim>,<vim,vj>属于E(G)。 路径长度是指一条路径上经过的边的 数目。若一条路径上除开始点和结束点可 以相同外,其余顶点均不相同,则称此路径为 简单路径。例如,有图中,(v0 ,v2 ,v1 )就是一条 简单路径,其长度为2。 1 2 0 3
7.回路或环 若一条路径上的开始点与结束点为 同一个顶点则此路径被称为回路或环。 开始点与结束点相同的简单路径被称为 简单回路或简单环。 例如右图中,(vn2Y1,0)就是一条简 单回路,其长度为3
7. 回路或环 若一条路径上的开始点与结束点为 同一个顶点,则此路径被称为回路或环。 开始点与结束点相同的简单路径被称为 简单回路或简单环。 例如,右图中,(v0 ,v2 ,v1 ,v0 )就是一条简 单回路,其长度为3。 1 2 0 3
9连通、连通图和连通分量 在无向图G中若从顶点v到顶点v有路径则称v 和v是连通的。 若图G中任意两个顶点都连通则称G为连通图否 则称为非连通图。 无向图G中的极大连通子图称为G的连通分量。 显然任何连通图的连通分量只有一个,即本身而非连 通图有多个连通分量
9. 连通、连通图和连通分量 在无向图G中,若从顶点vi到顶点vj有路径,则称vi 和vj是连通的。 若图G中任意两个顶点都连通,则称G为连通图,否 则称为非连通图。 无向图G中的极大连通子图称为G的连通分量。 显然,任何连通图的连通分量只有一个,即本身,而非连 通图有多个连通分量
9.强连通图和强连通分量 在有向图G中若从页点v到顶点v 有路径则称从v到v是连通的。 若图G中的任意两个顶点v和v都 连通,即从v到v和从v到v都存在路径, 则称图G是强连通图。例如右边两个 图都是强连通图。 有向图G中的极大强连通子图称为 G的强连通分量。显然强连通图只有 一个强连通分量,即本身非强连通图有 (b) 多个强连通分量
9. 强连通图和强连通分量 在有向图G中,若从顶点vi到顶点vj 有路径,则称从vi到vj是连通的。 若图G中的任意两个顶点vi和vj都 连通,即从vi到vj和从vj到vi都存在路径, 则称图G是强连通图。例如,右边两个 图都是强连通图。 有向图G中的极大强连通子图称为 G的强连通分量。显然,强连通图只有 一个强连通分量,即本身,非强连通图有 多个强连通分量。 1 2 0 3 （a） 1 2 0 （b）