【数据结构/图】图的定义和术语

落日映苍穹つ 2023-01-19 07:11 9阅读 0赞

# 图的定义 #

图（G）是由两个集合V和E组成，记为G=（V,E），其中V是**顶点**的有穷非空集合，E是V中**顶点偶对**的有穷集合，这些顶点偶对称为**边**。

所以也可以说，图是顶点集合以及顶点间的关系集合组成的一种数据结构。

## 有向图 ##

定义：边集E（G）为有向边的集合。（图中的顶点之间的连线是有方向的，这样的图称为有向图（directedgraph）。）

![在这里插入图片描述][20210508141210194.png_pic_center]  
对于如上有向图来说，G=(V,E) ， 其中顶点集合V=\{A,B,C,D\}；弧集合E=\{<A,D>,<B,A>,<C,A>,<B,C>\}

<u , v>表示从顶点u到顶点v的一条弧或边，并称u为弧尾或起始点，称v为弧头或终止点。

## 无向图 ##

定义：边集E（G）为无向边的集合。  
![在这里插入图片描述][20210509085633336.png_pic_center]  
对于如上无向图来说，G=(V,\{E\}) 其中顶点集合V=\{A,B,C,D\}；边集合E=\{(A,B),(B,C),(C,D),(D,A),(A,C)\}

**此时，E（G）用括号来表示**

注意！

（1）对于有向图来说，<V2，V6>表示从顶点V2到顶点V6，而<V6，V2>表示顶点V6到顶点V2。

（2）对于无向图来说，连接顶点A与D的边，可以表示为无序对(A,D)，也可以写成(D,A)。

（3）E（G）可以为空集，若为空集，则图G只有顶点没有边。

# 图的术语 #

n表示顶点数目，e表示边的数目。

## 度 ##

度=入度+出度，记为TD（v）  
入度：有多少个箭头指向顶点叫入度（以V为终点的有向边的数目），记为ID（v）  
出度：从顶点飚出去的箭头的数目叫出度，反正就是和入度相反啦（以V为起点的有向边的数目），记为OD（v）

## 有向完全图 ##

有向完全图：有向完全图是指图中各边都有方向，且每两个顶点之间都有两条方向相反的边连接的图，最大边数是**n（n-1）**，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]

## 无向完全图 ##

无向完全图：该图中每条边都是无方向的。n个顶点的无向图的最大边数是**n（n-1）/2**（因为无向图中的边没有方向，所以除2便是无向图的最大边数。）无向完全图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]

## 权和网 ##

权：也就是边上面上注明的数字也就是权。  
网：带权的图叫做网。

## 邻接点 ##

对于**无向图**G = ( V , E )，如果边(u , v) ∈E，则称顶点u 与顶点v 互为邻接点，即u和v相邻接。边（u,v）依附于顶点u和v，或者说边（u,v）与顶点u和v相关联。

## 路径、路径长度、回路等 ##

对无向图G=(V，E)，若从顶点v经过若干条边能到达w，称顶点v和w是连通的，又称顶点v到w有路径(Path) 。

对有向图G=(V，E)，从顶点v到w有有向路径，指的是从顶点v经过若干条有向边(弧)能到达w。

路径的长度：路径上的边或有向边(弧)的数目。

简单路径：在一条路径中，没有重复相同的顶点；

回路(环)：第一个顶点和最后一个顶点相同的路径；

简单回路(简单环)：在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现。

## 连通、连通图、连通分量 ##

在无向图中，如果从一个顶点vi到另一个顶点vj (i≠j)有路径，则称顶点vi 和vj 是连通的。

如果图中**任意**两顶点vi 、vj ∈V，vi 和vj 都是连通的，则称该图是连通图（connected graph）。

所谓连通分量（connected component），是指无向图的极大连通子图。显然任何连通图的连通分量只有一个，即本身。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 2]

那如果是非连通图，连通分量就是每个连通部分。

## 强连通图、强连通分量 ##

强连通图：强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都**存在路径**（可以经过多个点到达），则称G是强连通图。

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

## 连通图的生成树（无向图） ##

生成树：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的**n-1**条边（不能再去掉任何一条边），称为图的生成树。

关于无向图的生成树的几个结论：

> 一棵有n个顶点的生成树有且仅有n-1条边；  
> 如果一个图有n个顶点和小于n-1条边，则是非连通图；  
> 如果多于n-1条边，则一定有环  
> （因为加上的边使得它依附的那两个顶点之间有了第二条路径）；  
> 有n-1条边的图不一定是生成树。

## 有向树和生成森林 ##

有向树：只有**一个顶点的入度为0 ，其余顶点的入度均为1**的有向图。

生成森林：一个**有向图**的生成森林是由**若干棵有向树**组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 3]

[20210508141210194.png_pic_center]: /images/20221021/0f5e177643114e47a72aa86a4a0c3c7b.png
[20210509085633336.png_pic_center]: /images/20221021/7e32ea66fe2544fda9750953182add61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/df672685c47b4b329ea98a232402ea56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/9383cf38758041a7981c73e02b92296e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/569a423957b542928d31e89fc0e2de5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221021/bf44bc5cc6584b16a199429941ea7a6b.png