(6)稠密图、稀疏图。若一个图接近完全图,称为稠密图; 4称边数很少的图为稀疏图。 (7)顶点的度、入度、出度。顶点的度( degree)是指依附 于某顶点v的边数,通常记为TD(V)。在有向图中,要区别 顶点的入度与出度的概念。顶点v的入度是指以顶点为终点 的弧的数目。记为D(y;顶点v出度是指以顶点v为始点的 弧的数目,记为OD()。有TD(yD(y)+OD(V) 可以证明,对于具有n个顶点、e条边的图,顶点ⅵ的度TD (ⅵ)与顶点的个数以及边的数目满足关系: 2e= 2 tD(vi) 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 ⑹稠密图、稀疏图。若一个图接近完全图，称为稠密图； 称边数很少的图为稀疏图。 ⑺顶点的度、入度、出度。顶点的度（degree）是指依附 于某顶点v的边数，通常记为TD (v)。在有向图中，要区别 顶点的入度与出度的概念。顶点v的入度是指以顶点 为终点 的弧的数目。记为ID (v)；顶点v出度是指以顶点v为始点的 弧的数目，记为OD (v)。有TD (v)=ID (v)＋OD (v)。 • 可以证明，对于具有n个顶点、e条边的图，顶点vi的度TD (vi)与顶点的个数以及边的数目满足关系： 2e =
(8)边的权、网图。与边有关的数据信息称为权( weight )。在实际应用中,权值可以有某种含义。比如,在一个 反映城市交通线路的图中,边上的权值可以表示该条线路 的长度或者等级;对于一个电子线路图,边上的权值可以 表示两个端点之间的电阻、电流或电压值:对于反映工程 进度的图而言,边上的权值可以表示从前一个工程到后 个工程所需要的时间等等。边上带权的图称为网图或网络 ( network)。如果边是有方向的带权图,则就是一个有向 网图。 (⑨路径、路径长度。顶点v到顶点v之间的路径(path) 是指顶点序列vnV1V2, 。其中,(vnv1), (V12V2),…,yvmn)分别为图中的边。路径上边的数目称为 路径长度。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 ⑻边的权、网图。与边有关的数据信息称为权（weight ）。在实际应用中，权值可以有某种含义。比如，在一个 反映城市交通线路的图中，边上的权值可以表示该条线路 的长度或者等级；对于一个电子线路图，边上的权值可以 表示两个端点之间的电阻、电流或电压值；对于反映工程 进度的图而言，边上的权值可以表示从前一个工程到后一 个工程所需要的时间等等。边上带权的图称为网图或网络 （network）。如果边是有方向的带权图，则就是一个有向 网图。 ⑼路径、路径长度。顶点vp到顶点vq之间的路径（path） 是指顶点序列vp ,vi1,vi2, …, vim,vq。其中，（vp ,vi1）， (vi1,vi2)，…,(vim,vq )分别为图中的边。路径上边的数目称为 路径长度
⑩回路、简单路径、简单回路。称ⅵ的路径为回路或 者环( cycle)。序列中顶点不重复出现的路径称为简单 「路径。除第一个顶点与最后一个顶点之外,其他顶点不 重复出现的回路称为简单回路,或者简单环。 D子图。对于图G=(V,E),G=(V,E),若存 在V是V的子集,E是E的子集,则称图G是G的一个子 图。下图示出了G2和G1的两个子图G和G”。 (a)G (b)G 图G2和G1的两个子图示意 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 ⑽回路、简单路径、简单回路。称vi的路径为回路或 者环（cycle）。序列中顶点不重复出现的路径称为简单 路径。除第一个顶点与最后一个顶点之外，其他顶点不 重复出现的回路称为简单回路，或者简单环。 ⑾子图。对于图G=（V，E），G’=（V’，E’），若存 在V’是V的子集 ，E’是E的子集 ，则称图G’是G的一个子 图。下图示出了G2和G1的两个子图G’和G’’
①②连通的、连通图、连通分量。在无向图中,如果从 十个顶点v到另一个顶点ⅶ有)有路径,则称顶点ⅵ和是连 通的。如果图中任意两顶点都是连通的,则称该图是连通 图。无向图的极大连通子图称为连通分量。下图(a)中有 两个连通分量,如图(b)所示。 A B③(B (a)无向图G3 (b)G3的两个连通分量 无向图及连通分量示意 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 ⑿连通的、连通图、连通分量。在无向图中，如果从一 个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连 通的。如果图中任意两顶点都是连通的，则称该图是连通 图。无向图的极大连通子图称为连通分量。下图 (a)中有 两个连通分量，如图 (b)所示
3强连通图、强连通分量。对于有向图来说,若图中任意 对顶点ⅵ和v()均有从一个顶点v到另一个顶点y有路 径,也有从ⅵ到ⅵ的路径,则称该有向图是强连通图。有向 图的极大强连通子图称为强连通分量。 左下图中有两个强连通分量,分别是{ 是{V12 2v3}和{4}, 如右下图所示。 ] v34 有向图G2 有向图G2的两个强连通分量示意 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 ⒀强连通图、强连通分量。对于有向图来说，若图中任意 一对顶点vi 和vj(i≠j)均有从一个顶点vi到另一个顶点vj有路 径，也有从vj到vi的路径，则称该有向图是强连通图。有向 图的极大强连通子图称为强连通分量。 左下图中有两个强连通分量，分别是{v1,v2,v3}和{v4}， 如右下图所示