当前位置:鱼C工作室 >数据结构和算法 > 查看文章

图的定义与术语2 – 数据结构和算法55

图的定义与术语2

 

让编程改变世界

Change the world by program


 

图的顶点与边之间的关系

 

对于无向图G=(V,E),如果边(V1,V2)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接。

边(V1,V2)依附(incident)于顶点V1和V2,或者说边(V1,V2)与顶点V1和V2相关联。

 

顶点V的度(Degree)是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,边(A,B)依附于顶点A与B上,顶点A的度为3。

 

对于有向图G=(V,E),如果有<V1,V2>∈E,则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1。

以顶点V为头的弧的数目称为V的入度(InDegree),记为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为TD(V)=ID(V)+OD(V)。

 

下图顶点A的入度是2,出度是1,所以顶点A的度是3。

 

无向图G=(V,E)中从顶点V1到顶点V2的路径(Path)。

下图用红线列举了从顶点B到顶点D的四种不同路径:

 

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

下图用红线列举顶点B到顶点D的两种路径,而顶点A到顶点B就不存在路径啦:

 

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

第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。

 

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

下图左侧是简单环,右侧不是简单环:

 

连通图

 

在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图(ConnectedGraph)

下图左侧不是连通图,右侧是连通图:

 

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

注意以下概念:

  1. 首先要是子图,并且子图是要连通的;
  2. 连通子图含有极大顶点数;
  3. 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

 

在有向图G中,如果对于每一对Vi到Vj都存在路径,则称G是强连通图。

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

 

下图左侧并不是强连通图,右侧是。并且右侧是左侧的极大强连通子图,也是左侧的强连通分量。

 

最后我们再来看连通图的生成树定义。

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

 

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


为您推荐

报歉!评论已关闭.