51-图的基本术语

1. 端点和邻接点

图1-无向图

在一个无向图中，若存在一条边(i，j)，称顶点i和顶点j为此边的两个端点，比如在（1，2）之间有一条这样的边，那么1和2就是这条边的端点，且顶点1和顶点2之间互为邻接点。

图2-有向图

在一个有向图中，因为是有方向的，若存在一条边< i，j>，称顶点i是一条出边（因为是从i出发的），而顶点j是一条入边。另外，顶点i为此边的起始端点（简称为起点），顶点j为终止端点（简称终点），顶点i 和顶点j 互为邻接点。

2. 顶点的度，入度和出度

如图1所示，在无向图中，顶点所具有的边的数目称为该顶点的度，比如上图中顶点1就有3条边，因为跟顶点1相关的边有3条，顶点3则有4条相关的边。

如图2所示，在有向图中，是有方向的：
以顶点i为终点的入边的数目，称为该顶点的入度。

以顶点i为始点的出边的数目，称为该顶点的出度。

举个例子：比如以顶点3为终点的边的个数就有4条，所以顶点3的入度为4；但是以顶点3为起点的边的个数为0，那么顶点3的出度为0，顶点3的度则为出度和入度的和，即为4。

那么我们可以这样总结，如果一个图有n个顶点和e条边，每个顶点的度为 $d_{i} （ 1 \leq i \leq n ）$ ，这里我们要注意图中的每条边算过2次，所以要乘以二分之一，则公式为：

e = \frac{1}{2} \sum_{i = 1}^{n} d_{i}

3. 完全图

图3

若无向图中的每两个顶点之间都存在着一条边，则称此图为完全图，在完全无向图中包含有n ( n - 1 ) / 2条边，如在图3中，有4个顶点的完全无向图，共有6条边。

图4

有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。比如对于顶点1和顶点2来说，有从顶点1到顶点2的边，也有从顶点2到顶点1的边，而且这两条边的方向是相反的。对于顶点2和顶点3之间也是如此。在完全有向图中包含有n(n-1)条边。

4. 稠密图、稀疏图

图5

当一个图接近完全图时，则称为稠密图。相反，当一个图含有较少的边数，远远小于完全图的边数（即当 e < n(n-1)）时，则称为稀疏图。

5. 子图

有两个图G=(V，E)和G’=(V’，E’)

若V’是V的子集，即V’⊆ V，且E’是E的子集，即E’⊆ E，则称G’是G的子图。

图6

例如：图G1，G2，G3都是有向图，因为图G1中的边的集合E包括了图G2中的边的集合E，所以图G2是图G1的子图；

由于图G3中的有一条边<0，4>，但是在图G1中并没有包括<0，4>这样的一条边，而<4，0>和<0,4>是方向不同的两条边，所以图G3不是图G1的子图。

6. 路径和路径长度

图7

在一个图G=(V，E)中，从顶点i到顶点j的一条路径是一个顶点序列 $(i, i_{1}, i_{2}, \dots, i_{m}, j)$ 。

若此图G是无向图，则边 $(i, i_{1}) ， (i_{1}, i_{2}) ， \dots ， (i_{m - 1}, i_{m}) ， (i_{m}, j)$ 属于E(G) 。

若此图是有向图，则 $< i, i_{1} > ， < i_{1}, i_{2} > ， \dots ， < i_{m - 1}, i_{m} > ， < i_{m}, j >$ 属于E(G)。

路径长度是指一条路径上经过的边的数目。

若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。

比如：(0，2，1)是一条简单路径，且路径长度为2 。

比如：（0，2，3，2，1）不是一条简单路径，因为除了开始点和结束点外，其他的顶点2出现了相同，所以这不是一条简单路径。

7. 回路或环

图8

若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。

开始点与结束点相同的简单路径被称为简单回路或简单环。

比如在上图中，(0，2，1，0)就是一条简单回路（红色箭头线路），因为开始点和结束点相同，路径长度为3。

8. 连通、连通图和连通分量

图9

在无向图G中，若从顶点i到顶点j有路径，则称顶点i和j是连通的。比如在图G1中，顶点1到顶点3之间是有路径的，那么顶点1到顶点3之间是连通的。又比如在图G2中，顶点1到顶点3之间没有路径，那么顶点1到顶点3之间是非连通的。

若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。在图G1中，任意两个顶点之间都能连通，所以图G1是连通图，而在图G2中顶点3和顶点2是非连通的，顶点4和顶点0也是非连通的，图G2是非连通图。

图10

无向图G中的极大连通子图称为G的连通分量，连通子图本身是一个连通图（任意两个顶点都连通），但是在这个连通子图中增加一个顶点3之后，就不再连通了，因此我们把（0，1，2）形成的连通图称之为极大连通子图，也称为连通分量。

另外，任何连通图的连通分量只有一个，即本身。而对于非连通图可以有多个连通分量，比如由顶点1，顶点2，顶点3组成的连通图是一个极大连通子图。由顶点3和顶点4组成的连通图也是一个极大连通子图。

9. 强连通图和强连通分量

图11

强连通图和强连通分量是针对有向图而言的，在有向图G中，若从顶点i到顶点j有路径，则称从顶点i到j是连通的。

若图G中的任意两个顶点i和j都连通，则称图G是强连通图。比如在图G1中顶点1到顶点3，顶点0到顶点3之间都能连通，因此图G1可以称为强连通图；而对于图G2来说，因为是有向图，顶点0到顶点3之间无法连通，因此图G2也称为非强连通图。

有向图G中的极大强连通子图称为G的强连通分量，强连通图只有一个强连通分量，即本身；非强连通图有多个强连通分量。

10. 权和网

图12

图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为权，权可以表示从一个顶点到另一个顶点的距离或花费的代价。比如顶点1到顶点2之间的边附有的数值8就称为权。

边上带有权的图称为带权图，也称作网。