剑客
关注科技互联网

图的基本定义

这是《大话数据结构》第七章图的基本知识总结,首先是总结图的基本定义和相关的术语,包括有向图,无向图,连通图等术语的定义。

图(Graph)是由顶点的有穷非空集合和顶点之间的集合组成,通常表示为: G(V, E) ,其中 G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中边的集合。

对于上述图的定义,需要注意的是:

  • 线性表中的数据元素被称为元素,树中将数据元素称为结点,而图中数据元素被称为 顶点
  • 线性表可以没有数据元素,称为空表;树也可以没有结点,称为空树。但是图的定义中强调了顶点集合 V 是有穷非空的集合,所以图结构中不能没有顶点。
  • 线性表中,相邻的数据元素之间具有线性关系;树结构中,相邻两层的结点具有层次关系。而 图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

各种图定义

接下来会介绍各自图的定义,包括无向图与有向图,有向完全图和无向完全图,稀疏与稠密图等。

无向边: 若顶点$v_i$ 到$v_j$之间的边没有方向,则称这条边为 无向边(Edge) ,用无序偶对$(v_i, v_j)$来表示。

如果图中任意两个顶点之间的边都是无向边,则称该图是 无向图

如下图左边的图就是一个无向图$G_1$,$G_1 = (V_1,{E_1})$,其中顶点集合 $V_1 = {A,B,C,D}$,边集合是$E_1 = {(A, B), (B, C), (C, D), (D, A), (A, C)}$。

有向边: 若顶点$v_i$ 到$v_j$之间的边有方向,则称这条边为 有向边,也称为弧(Arc) 。用有序偶$

$来表示,$v_i$称为弧尾,$v_j$称为弧头。

如果图中任意两个顶点之间的边都是有向边,则称该图是 有向图

如下图右边的图就是一个有向图 $G_2$,$G_2 =(V_2, {E_2}) $,其中顶点集合 $V_2 = {A,B,C,D}$,边集合是$E_2 = {

图的基本定义

这里需要注意有向图中有向边的表示是不能随意乱写的,必须是按照定义中$

$,弧尾在前,弧头在后的写法。

图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图是简单图。

如下图所示都不是简单图,而我们主要讨论的都是简单图。

图的基本定义

无向完全图是指在无向图中,任意两个顶点之间都存在边。

含有$n$个顶点的无向完全图有$/frac{n/times (n-1)}{2}$条边。

有向完全图是指在有向图中,任意两个顶点之间都存在方向互为相反的两条弧。

含有$n$个顶点的有向完全图有$n/times (n-1)$条边。

由此可以得到一个结论:

对于具有$n$个顶点和$e$条边数的图,无向图有$0 /le e /le /frac{n/times (n-1)}{2}$, 有向图有$0 /le e /le n /times (n-1)$。

有很少边或弧的图称为稀疏图,反之称为稠密图。

这里的稀疏与稠密都是相对而言的。

与图的边或弧相关的数值称为 权(Weight) ,它可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为 网(Network)

下图就是一个带权的图的例子。

图的基本定义

假设有两个图 $G = (V,{E})$,和 $G^/prime = (V^/prime, {E^/prime}) $,如果$V^/prime /subseteq V$, 且 $E^/prime /subseteq E$,则称$G^/prime$是$G$的子图。

下面展示了无向图和有向图与其子图。

图的基本定义

图的顶点与边的关系

在无向图 $G=(V,{E})$,如果边 $(v, v^/prime) /in E$,则称顶点$v和v^/prime$互为 邻接点(Adjacent) ,即$v 和 v^/prime$相邻接。边$(v, v^/prime)$依附(incident)于顶点$v 和 v^/prime$,或者说$(v,v^/prime)$与顶点$v 和 v^/prime$相关联。 顶点$v$的度(Degree)是和$v$相关联的边的数目,记为TD($v$)。

例如对于上图中上方的无向图,顶点A与B互为邻接点,边(A, B)依附于顶点A与B上,顶点A的度为3。通过计算,可以知道, 无向图的边数是各顶点度数和的一半,即$e = /frac{1}{2} /sum_{i=1}^n TD(v_i)$。

有向图 $G=(V,{E})$,如果弧$

/in E$, 则称顶点$v$邻接到顶点$v^/prime$,顶点$v^/prime$邻接自顶点$v$。弧$

$和顶点$v,v^/prime$相关联。
以顶点$v$为头的弧的数目称为$v$的入度(InDegree),记为$ID(v)$;以顶点$v$为尾的弧的数目称为$v$的出度(OutDegree),记为$OD(v)$,因此顶点$v$的度为$TD(v) = ID(v) + OD(v)$。

例如对上图中下方的有向图,顶点A的入度是2(从B到A的弧,C到A的弧),出度是1(从A到D的弧),所以顶点A的度是3。同样通过计算,可以得到$e =/sum_{i=1}^n ID(v i) = /sum {i=1}^n OD(v_i) $。

在无向图 $G=(V,{E})$中从顶点$v$到$v^/prime$的 路径(Path) 是一个顶点序列$(v=v {i,0},v {i,1},/cdots,v {i,m}=v^/prime),其中(v {i,j-1},v_{i,j}) /in E, 1 /le j /le m$。

下图就展示了顶点B到顶点D的四种不同路径。

图的基本定义

如果$G$是有向图,则路径也是有向的,顶点序列应满足$

图的基本定义

路径的长度是路径上的边或弧的数目。

如上图有向图中,左侧的路径长度是2,经过两条弧,而右侧的路径长度是3,经过3条弧。

第一个顶点到最后一个顶点相同的路径称为 回路或环(Cycle) 。序列中顶点不重复出现的路径称为 简单路径 。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为 简单回路或简单环

下图中,两个图都是一个环,但左侧的图是一个简单环,而右侧图中顶点C重复出现,因此它不是一个简单环。

图的基本定义

连通图相关术语

接下来会介绍有关连通图的定义和相关术语。

无向图$G$中,如果从顶点$v$到$v^/prime$有路径,则称$v$和$v^/prime$是 连通的。 如果对于图中 任意两个顶点$v_i、v_j /in V$,$v_i$和$v_j$都是连通的,则称$G$是连通图。

无向图中的极大连通子图称为连通分量。这个连通分量的前提条件有:

  • 是子图;
  • 子图是要连通的;
  • 连通子图要有极大顶点数;
  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

有向图$G$中,如果对于每一对$v_i,v_j /in V, v_i /neq v_j$,从$v_i$到$v_j$和从$v_j$到$v_i$都存在路径,则称$G$是 强连通图 。有向图中的 极大强连通子图 称做有向图的 强连通分量

如下图所示,图1并不是强连通图,因为顶点A到顶点D存在路径,但不存在从顶点D到顶点A的路径。图2就是强连通图,而且显然图2是图1的极大强连通子图,即是它的强连通分量。

图的基本定义

接下来是连通图的生成树定义:

一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的 n-1 条边。

如下图所示,图1是一个普通图,但是显然它不是生成树,当去掉两条构成环的边后,如图2或图3,就满足生成树的条件了,即n个顶点和n-1条边且连通的定义,它们都是一棵生成树。由此可以得知, 如果一个图有n个顶点和小于n-1条边,则是非连通图;如果它多于n-1条边,则必定构成一个环。 但有n-1条边也不一定是生成树,如图4。

图的基本定义

接下来是有向树的定义:

如果一个有向图中 恰有一个顶点的入度为0,其余顶点的入度均为1 ,则是一棵有向树。

这里入度为0的顶点就相当于树的根结点,而其余顶点的入度都是1,是因为树的非根结点的双亲只有1个。

一个有向图的生成森林由 若干棵有向树组成,含有图中全部顶点 ,但 只有足以构成若干棵不相交的有向树的弧。

如下图所示,图1是一个有向图,再去掉一些弧后,得到图2和图3,也就是分解成两棵有向树,即图2和图3,而这两棵有向树也是图1有向图的生成森林。

图的基本定义

小结

图的基本定义就简单总结到这里,图的术语还是不比树的少,需要多看几遍,同时多使用,接下来会继续总结图的存储结构、遍历等知识点。

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址