图的基本概念

图的定义

图（Graph）是由一个非空的顶点集 $V$ 和一个边集 $E$ 组成的，记作 $G = (V, E)$ 。其中 $∣ V ∣$ 表示顶点数目， $∣ E ∣$ 表示边的数目。

有向图（Directed Graph）：如果边集每条边都是顶点的有序对，则图为有向图。 $(v, w)$ 为一条有向边（弧）， $v$ 为弧尾（tail）， $w$ 为弧头（head）。
无向图（Undirected Graph）：如果边集每条边都是顶点的无序对，则图为无向图。

子图

如果一个图的顶点集和边集都是另一个图顶点集和边集的子集，则称为另一个图的子图（Subgraph）。

完全图

完全图（Complete Graph）简单来说就是任意一个顶点都与其他所有顶点有边。

假设图中有 $n$ 个顶点， $e$ 条边，则含有 $e = n (n - 1) /2$ 条边的无向图称作完全图。
含有 $e = n (n - 1)$ 条弧的有向图称作有向完全图。
稀疏图（Sparse Graph）和稠密图（Dense Graph）：若边或弧的个数 $e < n lo g_{2} n$ ，则称作稀疏图，否则称作稠密图。

度

度（Degree）简单来说就是有关一个顶点的边的数量关系。

对无向图来说，假若顶点 $v$ 和顶点 $w$ 之间存在一条边，则称顶点 $v$ 和 $w$ 互为邻接点（Adjacent Vertex），边 $(v, w)$ 和顶点 $v$ 和 $w$ 相关联。和顶点关联的边的数目定义为边的度。
对有向图来说，以顶点为弧尾的弧的数目定义为顶点的出度（Out-degree, OD）；以顶点为弧头的弧的数目定义为顶点的入度（In-degree, ID）。度 $T D = O D + I D$ 。

路径

**路径（Path）**即指从一个顶点到另一个顶点的顶点序列，长度即是中途经过的边的数目（对于有权图，带权路径长度则是路径上边权之和）。

设图 $G = (V, E)$ 中的一个顶点序列 $u = v_{i_{0}}, v_{i_{1}}, \dots, v_{i_{m}} = w$ ，其中 $(v_{i_{j - 1}}, v_{i_{j}}) \in E$ , $1 \leq j \leq m$ ，则称从顶点 $u$ 到顶点 $w$ 之间存在一条路径。

路径长度（Path Length）：路径上边的数目。
简单路径（Simple Path）：若序列中的顶点不重复出现，则称作简单路径。
简单回路（Simple Circuit）：若 $u = w$ ，则称这条路径为回路或简单回路。

连通图

连通图（Connected Graph）（强连通图）简单来说就是从一个顶点经过若干顶点可以到任意一个顶点。

若图 $G$ 中任意两个顶点之间都有路径相通，则称作此图为连通图。
若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量（Connected Component）。
对有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图（Strongly Connected Graph）；否则，其各个强连通子图称作它的强连通分量（Strongly Connected Component）。