图的基本概念

图的本质

图（Graph） 是一个有序二元组，记为 $G = \langle V, E \rangle$，其中

1. $V(G)$ 是有限非空集，$V$ 中元素称为 $G$ 的 顶点或结点，$V$ 称为 $G$ 的 顶点集；
2. $E(G)$ 是 $V(G)$ 中各个顶点之间边或弧的集合，$E$ 称为 $G$ 的 边集。

可以使用 $G$ 泛指图（无论是无向图还是有向图）。

无向图

无向图 $G = \langle V, E \rangle$，其中

1. $V \neq \varnothing$，$V = \{ v_1, v_2, \cdots, v_N \}$ 为 顶点集，元素 $v_i$ 称为 顶点（node）;
2. $E$ 为 $V \& V$ 的多重子集，称为 边集，其元素称为 无向边（undirected edge），简称 边（edge）。

有向图

有向图 $D = \langle V, E \rangle$，其中

1. $V \neq \varnothing$，$V = \{ v_1, v_2, \cdots, v_N \}$ 为 顶点集，元素 $v_i$ 称为 顶点（node）；
2. $E$ 为 $V \times V$ 的多重子集，称为 边集，其元素称为 有向边（directed edge），简称 边（edge）。

图的分类

按边分类

• 简单图：既不含平行边，也不含环的图。
• 多重图：含平行边的图。这里，平行边的条数称为重数。
• 线图：不含平行边的图。

是否标定

• 标定图：每一个顶点和每一条边都指定符号的图。
• 非标定图：并非每一个顶点和每一条边都指定符号的图。

特殊形态

• 零图：边集为空集的图。（$n$ 阶零图 即有 $n$ 个顶点的零图）
• 平凡图：只有一个顶点，没有边的图。
• 空图：顶点集为空集的图。
• 基图：有向图的各条有向边都改成无向边得到的图。

点与线的关系

关联（Incidence）

对于

$$
e_k = (v_i, v_j) \in E,
$$

称 $e_k$ 与顶点 $v_i, v_j$ 相关联，$v_i$ 称为始点，$v_j$ 称为终点。若 $v_i \neq v_j$，则称 $e_k$ 与顶点 $v_i, v_j$ 的关联次数为 $1$。若 $v_i = v_j$，则 $e_k$ 与顶点 $v_i$ 的关联次数为 $2$，并称 $e_k$ 为环。

相邻（Adjacency）

若两个顶点之间有边相连，则称两个顶点相邻，或称为 邻接点；若两条边至少有一个公共顶点，则称两条边相邻，或称为 邻接边。不与任何顶点相邻的顶点称为 孤立点。

邻域（Neighborhood）与关联集（Association Set）

对于 $v \in V(G)$（$G$ 为无向图）

1. $v$ 的邻域：$N(v) = \{ u | u \in V(G) \wedge (u, v) \in E(G) \wedge u \neq v \}$
2. $v$ 的闭邻域：$\overline{N} = N(v) \cup \{v\}$
3. $v$ 的关联集：$I(v) = \{ e | e \in E(G) \wedge e \sim v \}$

对于 $v \in V(D)$（$D$ 为有向图）

1. $v$ 的后继元集：$\Gamma^+_D(v) = \{ u | u \in V(D) \wedge \langle v, u \rangle \in E(D) \wedge u \neq v \}$
2. $v$ 的前驱元集：$\Gamma^-_D(v) = \{ u | u \in V(D) \wedge \langle u, v \rangle \in E(D) \wedge u \neq v \}$
3. $v$ 的邻域：$N_D(v) = \Gamma^+_D(v) \cup \Gamma^-_D(v)$
4. $v$ 的闭邻域：$\overline{N}_D(v) = N_D(v) \cup \{v\}$

度数

定义

对无向图 $G = \langle V, E \rangle$，$\forall v \in V$，与 $v$ 关联的边数称为 $v$ 的度数，简称度，记为 $\deg(v)$，简写为 $\mathrm{d}(v)$。环与顶点关联 $2$ 次，贡献的度数为 $2$。

对有向图 $D = \langle V, E \rangle$，$\forall v \in V$，$\deg^+(v)$ 是 $v$ 的出度，表示以 $v$ 为始点的边数，简写为 $\mathrm{d}^+(v)$；$\deg^-(v)$ 是 $v$ 的入度，表示以 $v$ 为终点的边数，简写为 $\mathrm{d}^-(v)$；$\deg(v)$ 是 $v$ 的度，表示与 $v$ 关联的边数，简写为 $\mathrm{d}(v)$。这里，有 $\mathrm{d}(v) = \mathrm{d}^+(v) + \mathrm{d}^-(v)$。

奇度顶点 指度数为奇数的顶点，偶度顶点 指度数为偶数的顶点。

握手定理

在任意无向图中 所有顶点的度数之和等于边数的 $2$ 倍。即，设 $G = \langle V, E \rangle$ 为任意无向图，$V =\{ v_1, v_2, \cdots, v_n \}$，$|E| = m$，则

$$
\sum_{i=1}^{n} \mathrm{d}(v_i) = 2m.
$$

在任意有向图中 所有顶点的入度之和，等于所有顶点的出度之和，都等于边数。所有顶点的度数之和等于边数的 $2$ 倍。即，设 $D = \langle V, E \rangle$ 为任意有向图，$V = \{ v_1, v_2, \cdots, v_n \}$，$|E| = m$，则

$$
\sum_{i = 1}^{n} \mathrm{d}(v_i) = 2m, \quad \sum_{i = 1}^n \mathrm{d}^+(v_i) = \sum_{i = 1}^n \mathrm{d}^-(v_i) = m.
$$

度数列

记 $V = \{v_1, v_2, \dots, v_n\}$ 为无向图 $G$ 的顶点集，则称 $d(v_1), d(v_2), \dots, d(v_n)$ 为 $G$ 的度数列。令最大度 $\Delta(G) = \max\{d(v) \mid v \in V\}$，最小度 $\delta(G) = \min\{d(v) \mid v \in V\}$；

记 $V = \{v_1, v_2, \dots, v_n\}$ 为有向图 $D$ 的顶点集，则有

• $D$ 的 度数列：$d(v_1), d(v_2), \dots, d(v_n)$；
• $D$ 的 入度列：$d^-(v_1), d^-(v_2), \dots, d^-(v_n)$；
• $D$ 的 出度列：$d^+(v_1), d^+(v_2), \dots, d^+(v_n)$。

令最大入度 $\Delta^-(D) = \max\{d^-(v) \mid v \in V\}$，最小入度 $\delta^-(D) = \min\{d^-(v) \mid v \in V\}$。

令最大出度 $\Delta^+(D) = \max\{d^+(v) \mid v \in V\}$，最小出度 $\delta^+(D) = \min\{d^+(v) \mid v \in V\}$。

可图化

任意非负整数列 $d = (d_1, d_2, \dots, d_n)$，若 $\sum_{i=1}^{n} d_i$ 为偶数，则是可图化的。

简单图的最大度

设 $G$ 为任意 $n$ 阶无向简单图，则 $\Delta(G) \leq n - 1$。

同构（Isomorphism）

设 $G_1 = \langle V_1, E_1 \rangle$ 和 $G_2 = \langle V_2, E_2 \rangle$ 为两个无向图（两个有向图），若存在双射函数 $f: V_1 \to V_2$，使得 $\forall v_i, v_j \in V_1$，

$$
(v_i, v_j) \in E_1 \text{ if and only if } (f(v_i), f(v_j)) \in E_2
$$

$$
(\langle v_i, v_j \rangle \in E_1 \text{ if and only if } \langle f(v_i), f(v_j) \rangle \in E_2)
$$

并且，$(v_i, v_j)$（$\langle v_i, v_j \rangle$）与 $(f(v_i), f(v_j))$（$\langle f(v_i), f(v_j) \rangle$）的重数相同，则称 $G_1$ 与 $G_2$ 是 同构的，记作 $G_1 \cong G_2$。

由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构，还要求保持边的方向。

常见的图

无向简单图

$n (n \geq 1)$ 阶无向简单图是每个顶点与其余顶点均相邻的无向简单图，记作 $K_n$。有

$$
m = \frac{n(n-1)}{2},\quad \Delta = \delta = n - 1.
$$

有向完全图

$n (n \geq 1)$ 阶有向完全图，是每对顶点之间均有两条方向相反的有向边，每个顶点有自环的有向完全图，记作 $D_n$。有

$$
m = n^2, \quad \Delta = \delta = 2n, \quad \Delta^+ = \delta^+ = n.
$$

竞赛图

$n (n \geq 1)$ 阶竞赛图是基图为 $K_n$ 的有向简单图。有

$$
m = \frac{n(n-1)}{2}, \quad \Delta = \delta = n - 1.
$$

正则图

$n$ 阶 $k$ 正则图是 $\Delta = \delta = k$ 的无向简单图。有

$$
m = \frac{nk}{2}.
$$

事实上，$n$ 阶完全图就是 $n - 1$ 正则图。