【数据结构第 6 章 ① 】- 图的定义和基本术语

2023-12-15 14:35:40

目录

一、图的定义

二、图的基本术语


图是一种比线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素之间有着明显的层次关系,并且每一层的数据元素可能和下一层中的多个元素(即孩子结点)相关,但只能和上一层中一个元素(即双亲结点相关);而在图结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关


一、图的定义

图(Graph)G 由两个集合 V 和 E 组成,记为 G = (V, E),其中 V 是顶点(Vertex)有穷非空集合顶点即图中的数据元素;E 是 V 中两个顶点之间的关系的有穷集合,两个顶点之间的关系称做边(Edge)。V(G) 和 E(G) 通常分别表示图 G 的顶点集和边集,E(G) 可以为空集,若 E(G) 为空集,则图 G 只有顶点而没有边

对于图 G,若边集 E(G) 为有向边的集合,则称该图为有向图;若边集 E(G) 为无向边的集合,则称该图为无向图

在有向图中,顶点 <x, y> 是有序的,它称为从顶点 x 到顶点 y 的一条有向边,因此 <x, y> 与 <y, x> 是不同的两条边。顶点对用一条尖括号括起来,x 是有向边的始点,y 是有向边的终点。<x, y> 也称作一条弧,则 x 为弧尾,y 为弧头

在无向图中,顶点 (x, y) 是无序的,它称为与顶点 x 和顶点 y 相关联的一条边,这条边没有特定的方向,(x, y) 与 (y, x) 是同一条边。为了有别于有向图,无向图的顶点对用一对圆括号括起来。

图一分别给出了有向图和无向图的示例。


二、图的基本术语

用 n 表示图中顶点数目,用 e 表示边的数目,下面介绍图结构中的一些基本术语。

  1. 子图:假设有两个图 G = (V, E) 和 G' = (V', E'),如果 V' \subseteq V 且 E' \subseteq E,则称 G' 为 G 的子图。例如,图二所示为图一中 G1 和 G2 子图的一些例子。

  2. 无向完全图和有向完全图:对于无向图,若具有 C_n^2 = \dfrac{n(n - 1)}{2} 条边(即图中任意两个顶点之间都存在一条边),则称为无向完全图;对于有向图,若具有 A_n^2 = n(n - 1) 条弧(即图中任意两个顶点之间都存在两条方向相反的弧),则称为有向完全图。

  3. 稀疏图和稠密图:在有很少条边或弧(如 e < nlog_2^n)的图称为稀疏图,反之称为稠密图。

  4. 权和网:在实际应用中,每条边可以标上具有某种含义的数值,该数值称为该边上的权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网

  5. 邻接点:对于无向图 G,如果图的边 (v, v') \in E,则称顶点 v 和 v' 互为邻接点,即 v 和 v' 相邻接。边 (v, v') 依附于顶点 v 和 v',或者说边 (v, v') 与顶点 v 和 v' 相关联。

  6. 度、入度和出度:顶点 v 的度是指和 v 相关联的边的数目,记为 TD(v)。例如,图一 (b) 中 G2 的顶点 v3 的度是 3。对于有向图,顶点 v 的度分为入度和出度。入度是以顶点 v 为头的弧的数目,记为 ID(v);出度是以顶点 v 为尾的弧的数目,记为 OD(v),顶点 v 的度为 TD(v) = ID(v) + OD(v)。例如,图一 (a) 中 G1 的顶点 v1 的入度 ID(v1) = 1,出度 OD(v1) = 2,度 TD(v1) = ID(v1) + OD(v1) = 3。

    如果顶点 vi 的度为 TD(vi),那么一个有 n 个顶点,e 条边的图(包括无向图和有向图),满足如下关系:e = \frac{1}{2}\sum_{i=1}^{n}TD(v_i)

    如果为有向图,还满足如下关系:e = \sum_{i}^{n}ID(v_i) = \sum_{i}^{n}OD(v_i)

  7. 路径和路径长度:在无向图 G 中,从顶点 v 到顶点 v' 是一个顶点序列(v = v_{i, 0}, v_{i, 1}, ..., v_{i, m} = v'),其中 (v_{i, j-1}, v_{i, j}) \in E, 1 \le j \le m。如果 G 是有向图,则路径也是有向的,顶点序列应满足 <v_{i, j-1}, v_{i, j}> \in E, 1 \le j \le m。路径长度是一条路径上经过的边或弧的数目。

  8. 简单路径、简单回路或简单环:序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。

  9. 连通、连通图和连通分量:在无向图 G 中,如果从顶点 v 到顶点 v' 有路径,则称 v 和 v' 是连通的。如果对于图中任意两个顶点 v_i,v_j \in Ev_iv_j 都是连通的,则称 G 是连通图。图一 (b) 中的 G2 就是一个连通图,而图三 (a) 中的 G3 则是非连通图,但 G3 有 3 个连通分量,如图三 (b) 所示。所谓连通分量,指的是无向图中的极大连通子图(尽可能包含更多的顶点和边的连通子图)

    对于 n 个顶点的无向图 G,若 G 是连通图,则最少有 n - 1 条边;若 G 是非连通图,则最多有 条边,即只有一个顶点是孤立的,其余顶点中任意两个顶点都存在一条边

  10. 强连通、强连通图和强连通分量:在有向图 G 中,如果从顶点 v 到顶点 v' 和从顶点 v' 到 v 之间都有路径,则称 v 和 v' 是强连通的。如果图中任意两个顶点都是强连通的,则称 G 是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。例如图一 (a) 中的 G1 不是强连通图,但它有两个强连通分量,如图四所示。

    对于 n 个顶点的有向图,若 G 是强连通图,则最少有 n 条弧(形成回路)

  11. 连通图的生成树一个极小连通子图,它包含图中全部顶点,但只有足以构成一棵树的 n - 1 条边,这样的连通子图称为连通图的生成树。图五所示为 G3 中最大连通分量的一棵生成树。如果在一棵生成树上添加一条边,必定构成一个环,因为这条边使得它依附的那两个顶点之间有了第二条路径

  12. 有向树:有一个顶点的入度为 0,其余顶点的入度均为 1 的有向图称为有向树。

文章来源:https://blog.csdn.net/melonyzzZ/article/details/134890214
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。