7.1.2图的定义和术语（2）在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们继续讨论图的定义和术语

先介绍邻接点，在无向图中

如果边(v, v`)∈E，则称顶点v和 v`互为邻接点

边(v, v`)依附于顶点v和 v`

顶点v的度是和v相关联的边的数目

记为TD(V)

观察我们给出图，我们看到边(v1，v4)是边集中的一条边

那么，顶点v1和v4互为邻接点

v1和v2之间也有边，v1和v2也互为邻接点

那么，v1有两个邻接点v2和v4。v3的邻接点最多

有三个邻接点

无向图中，顶点的度是和该顶点相关联的边的数目

每条边又涉及一个邻接点

所以顶点的度和邻接点个数是一样的

v1的度为2，v3的度为3

上一节中，我们介绍过一个基本操作FirstAdjVex（G,v）

这个操作是在图G中，求顶点v的第一个邻接点

结合例子，我们看一下，从邻接点的定义看

v3有3个邻接点：v2, v4, v5

谁是v3的第1个邻接点呢？

请大家思考一下，我们后面会讨论

在有向图中，如果弧属于弧集A

则称顶点v 邻接到顶点v`，顶点v`称为顶点v的邻接点

弧和顶点v， v`相关联

以顶点v为头的弧的数目称为v的入度

记为ID (V); 以顶点v为尾的弧的数目称为v的出度

记为OD (V);顶点v的度TD(V)= ID (V)+ OD (V)

我们结合图例介绍一下相关概念

观察图中的弧

我们称v2邻接到v3，v3称为v2的邻接点

同学们应该注意到，有向图中，邻接也是有向的

v2没有到其它顶点弧

只有唯一的一个邻接点v3，v3有两个邻接点v1和v6

结合前面的知识，我们可以看到

顶点的邻接点实际就是顶点的后继

这里换了个说法而已

有向图中顶点的度分为入度和出度

两者相加作为顶点的度

入度是以顶点v为头的弧的数目

实际就是v的前驱个数

出度是顶点v为尾的弧的数目

实际就是v的后继的个数

例如顶点v4，有两个前驱v1和v5，入度为2

有两个后继v3和v6，出度也为2

顶点v4的度是二者相加，是4

n个顶点的图中

边和弧的数目等于图中所有顶点的度相加除÷2

这一点是很好理解的

无向图中一条边在它相关的两个顶点各产生一个度

共产生2个度

有向图中一条弧在弧尾顶点产生一个出度

在弧头顶点产生一个入度，也是2个度

所以，各顶点总的度数是边或弧的2倍

下一个概念是路径

无向图中从顶点v到顶点v`的路径是一个顶点序列（v=vi,0,vi,1,...vi,m= v`)

其中（vi,j-1,vi,j) ∈E, 1<=j<=m

顶点序列vi,0,vi,1,...vi,m中

i是路径编号，路径中有m+1个顶点

有一个出发点v是序列中第一个顶点vi,0

有一个终点v`是序列中最后一个顶点vi,m

路径的顶点序列中有一个约束

序列中相邻的两个顶点之间必须有边

以G2为例，有一个顶点序列v1,v2,v3,v4

出发点是v1，终点是v4，并且满足约束

就是在这个顶点序列中，前驱和后继之间都有边

所以，这是G2中的一条路径

简单的说就是，无向图中的路径呢要沿着边走

如果是有向图,则路径也是有向的

顶点序列满足 ∈A, j大于等于1小于等于m

也就是说序列中前后两个顶点之间要有弧

如图G1有这样的顶点序列v1,v3,v4

顶点序列的前驱和后继之间都有弧

是一条路径

直观的看，就是有向图中的路径

不但要沿着弧走，还必须按照箭头所指的方向走

回路或者叫环，第一个顶点和最后一个顶点相同的路径呢

称为回路或者环

比如G2中，v1v2v3v4回到v1

这是一条回路，G1中v1,v3,v4回到v1

也是一条回路

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

G2中，回路的路径长度是4

G1中，回路的路径长度是3

简单路径是指序列中顶点不重复的路径称为简单路径

就是简单路径中不应该包含环

联通图是对无向图而言的

有向图中讨论的是强连通图

无向图G中，如果从顶点v到顶点v`有路径

则称v和 v`是连通的

这是顶点之间连通的概念

如果对于图中任意两个顶点v, v`∈V

v和 v`都是连通的，则称G是连通图

无向图中的极大连通子图称为连通分量

我们一直做例子的无向图G2

图中任意两个顶点之间都有路径

G2是一个连通图

幻灯上给出的图的G3，就不是一个连通图

比如说，顶点C和D之间就没有路径

和连通图相关的一个概念是连通分量

我们把无向图中的极大连通子图称为连通分量

图G3中，有如图1，2，3所示的三个连通分量

连通分量，也就是极大连通子图的概念

可以分为三层来理解

第一， 它是原图的一个子图

第二， 这个子图是一个连通子图

第三， 它不但是连通子图

还是一个极大的连通子图

那么，极大又是什么意思呢？

观察一下图3，如果我们取G，H，K这三个顶点

以及它们之间的边，可以构成一个连通子图

但是它并不是极大，极大连通子图还包含I这个节点

极大的意思可以理解为

顶点之间之间有路径

那么，它们都必须属于同一个极大连通子图

也就是一个连通分量

换句话说，就是能连上的，就要连在一起

有向图中，我们讨论的是强连通图

有向图G中，如果对于每一对v, v`∈V，v≠v`

从v到 v`和从v`到 v都存在路径

则称G是强连通图

有向图中的极大强连通子图称为强连通分量

前面我们讨论过，有向图的路径呢

也是有方向的，要按照箭头的方向走

从v到v`有路径，并不意味着从v`到v也有路径

图G1就不是一个强连通图，观察G1中v2这个顶点

它没有后继，它到任何顶点都没有路径

G1不是强连通图

同样，我们也定义了

有向图中的极大强连通子图称为强连通分量

G1的G1有两个

如图1，2所示，图2中的强连通分量只有一个顶点v2

因为v2到任何顶点都没有路径

它单独构成一个强连通分量

图1当中的三个顶点之间形成一个环

这个环保证了任意两个顶点之间都有路径

所以，图1的三个顶点的构成了一个强连通分量

生成树，一个连通图的生成树是一个极小连通子图

它含有图中的所有顶点

但只有足以构成一棵树的n-1条边

对生成树的理解注意两个方面

一是，生成树是在无向的连通图上讨论的

二是，极小的含义，它的极小体现边的数目

含有图中的所有顶点，但只有足以构成一棵树的n-1条边

看一下图示，图的左边是一个包含7个顶点

8条边的连通图

图的右边是它的生成树

生成树中包含连通图的7个顶点

并且只包含了6条边

这6条边保证了生成树仍然是一个连通子图

如果少一条边，一定不能连通

如果多一条边，一定会形成一个回路

有向树，是和有向图相关的概念

如果一个有向图，恰有一个顶点的入度为0

其顶点的入度均为1，则是一棵有向树

一个有向图的生成森林由若干棵有向树组成

含有图中全部顶点

但只有足以构成若干棵互不相交的有向树的弧

一个有向图可以构造出包含多棵有向树的生成森林

结合图中的例子看一下

首先，取图中一个顶点，这里比如说取顶点A

作为第1棵有向树的树根

它的所有后继作为它的孩子

它有孩子B和F，继续考察，寻找B和F的后继

B没有后继，F有后继B和E，B已经是A的孩子

不考虑，F有孩子E，E有两个后继A和B

已经在树中，不考虑

生成森林中的第1棵树就构造完成了

在剩余的顶点当中，任取一个

比如说我们取D第2棵树的根

D有两个后继C和E，E在第一棵树中

不考虑，D只有一个孩子C

到此，所有顶点都已经在生成森林中了

生成森林中有两棵树

因为，构造过程中，图中顶点的可以任选

所以，一个有向图的生成森林并不是唯一的

好同学们，今天的课就到这儿

我们下次课再见