图的基本定义和概念（二）

完全图

对于一个具有 n 个顶点，e 条边的无向图，若边的总条数为 n*(n-1)/2,则称该图为完全图。

有向完全图

对于一个具有 n 个顶点，e 条边或弧的有向图，若边的总条数为 n*(n-1),则称该图为有向完全图。

权

有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数称作权。

网

这些权可以表示从一个个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

子图

可以理解为被包涵的一部分，一个大图里的一部分。

路径

在一个图中若从任一顶点 v 出发，沿着边能达到另一顶点 v'，则称这两顶点间存在路径。两顶点间不重重复边的条数称为路径的长度。

简单路径

在用一个顶点序列表示一条路径时，若序列中没有相同的顶点重复出现，则称其为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点均不相同的回路称为简单回路。

无向连通图

在无向图 G 中，如果从顶点 v 到顶点 v'有路径，则称 v 和 v'是连通的。如果对于无向图中任意两个顶片点 vi 和 vj(vi、vj ∈V)，都是连通的，则称 G 是连通图。

连通分量

无向图的极大连通子图。

有向连通图

在有向图 G 中，如果对于每一对顶点(vi，vj)(vi，vj ∈V)(vi≠vj)，从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 是强连通图。有向图 G 中的极大的强连通子图称为有向图的强连通分量，如图 7.5（1）所示。 图 7.5(2)为非强连通图与其三个强连通分量。

生成树

一个连通图的极小连通子图，称为其生成树。它含有图中的全部顶点 N，但只有足以构成一棵树的 N-1 条边。下图为生成树。图中共有 10 个顶点，所以生成树中有 9 条边。

一棵有 N 个顶点的生成树，有且仅有 N-1 条边。如果一个图有 N 个顶点和小于 N-1 条边，则该图为非连通图。

如果它有多于 n-1 条边，则图中一定有环。但有 n-1 条边的图不一定都是生成树。