5.1 图的基本概念

1、完全图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向图有n(n-1)/2条边。

在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条有向边。

2、连通、连通图和连通分量

在无向图中，若从顶点v到顶点W有路径存在，则称v和w是连通的。

若图G中任意两个顶点都是连通的，则称图G为连通图。

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

如果一个图中有n个顶点，并且有小于n-1条边，则此图必是非连通图。

首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有边；

极小连通子图是既要保持图连通，又要使得边数最小的子图。

3、强连通图、强连通分量

在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。

若图中任何一对顶点都是强连通的，则称该图为强连通图。

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

注意：强连通图，强连通分量只是针对有向图而言。一般在无向图中讨论连通性，在有向图中考虑强连通性。

4、生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。对于生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

注意：包含有向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。

5、顶点的度、入度和出度

图中每个顶点的度定义为该顶点一个端点的边的数目。

对于无向图，顶点v的度是指衣服与该顶点的边的条目，记为TD(v).

在具有n个顶点e条边的无向图中，有连加TD(v)=2e。即无向图的全部顶点的度之和等于边数的两倍，这是因为每条边和两个顶点相互关联。

对于有向图，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，记为ID(v);而出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v).

在具有n个顶点e条边的有向图中，有连加ID(Vi)=OD(Vi)=e,即有向图的全部顶点的入度之和出度之和相等并且等于边数。这是因为每条有向边都有一个起点和终点。

6、路径、路径长度和回路

顶点Vp到顶点Vq之间的一条路径是指顶点序列Vp，Vi1，Vi2，……，Vim，Vq。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。如果一个图有n个顶点，并且有大于n-1条边，则此图一定有环。

7、简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为简单路径。

除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路。

8、距离

从顶点u出发到顶点v的最短路径若存在，则该路径的长度称为从u到v的距离，若从u到v根本不存在路径，则记该距离为无穷。

9、有向树

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

10、简单图

一个图G如果满足：

①不存在重复边。

②与存在顶点到自身的边，则称图G为简单图。