图的基本概念

图

基本概念

无向图

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

• $V \neq \varnothing$ 是顶点集，元素称为顶点。
• $E$ 为 $V \And V$ 的多重子集，其元素称为无向边，简称边。
  • 其中 $\And$ 表示无序积，即 $A \And B = \lbrace (a, b) \ | \ a \in A \land b \in B \rbrace$ 实例：$V = \lbrace v_1, v_2, v_3, v_4, v_5 \rbrace$，$E = \lbrace (v_1, v_2), (v_1, v_3), (v_2, v_3), (v_3, v_4), (v_4, v_5) \rbrace$

则 $G = \langle V, E \rangle$ 为一无向图。

有向图

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

• $V \neq \varnothing$ 是顶点集，元素称为顶点。
• $E$ 为 $V \times V$ 的多重子集，其元素称为有向边。

实例：$V = \lbrace v_1, v_2, v_3, v_4, v_5 \rbrace$，$E = \lbrace \langle v_1, v_2 \rangle, \langle v_1, v_3 \rangle, \langle v_2, v_3 \rangle, \langle v_3, v_4 \rangle, \langle v_4, v_5 \rangle \rbrace$

相关概念

• 图
  • 可用 $G$ 泛指图（无向图或有向图）
  • $V(G)$，$E(G)$ 分别表示图 $G$ 的顶点集和边集
  • 用 $e_k$ 表示无向边或有向边
  • 用图形表示图时，如果给每一个顶点和每一条边指定一个符号，则称为标定图，否则称为非标定图。
• $n$ 阶图：$|V(G)| = n$
• $n$ 阶零图：$n$ 个顶点，无边
• 平凡图：即 $1$ 阶零图，只有一个顶点且无边
• 空图：$V(G) = \varnothing$

顶点与边的关联关系

• 无向图：

  • 设 $G = \langle V, E \rangle$，$e_k = (v_i, v_j)$，则称 $e_k$ 与 $v_i$ 和 $v_j$ 相关联，$v_i$ 和 $v_j$ 称为 $e_k$ 的端点。

  • 若 $v_i \neq v_j$，则称 $e_k$ 与 $v_i$ 和 $v_j$ 的关联次数为 $1$。

  • 若 $v_i = v_j$，则称 $e_k$ 与 $v_i$ 的关联次数为 $2$。并称 $e_k$ 为环。

  • 若 $e_k$ 不与 $v_i$ 相关联，则称 $e_k$ 与 $v_i$ 的关联次数为 $0$。

  • 若 $v_i$ 与 $v_j$ 由边 $e_k$ 相关联，则称 $v_i$ 与 $v_j$ 相邻。

  • 若 $e_i$ 与 $e_j$ 有至少一个公共顶点，则称 $e_i$ 与 $e_j$ 相邻。

• 有向图：
  • 设 $D = \langle V, E \rangle$，$e_k = \langle v_i, v_j \rangle$，则称 $e_k$ 与 $v_i$ 和 $v_j$ 相关联。$v_i$ 和 $v_j$ 为 $e_k$ 的端点，$v_i$ 为始点，$v_j$ 为终点。
  • 若 $v_i = v_j$，则称 $e_k$ 为 $D$ 中的环。
  • 若 $v_i$ 和 $v_j$ 由边 $e_k$ 相关联，则称 $v_i$ 与 $v_j$ 相邻。
  • 若 $e_i$ 的终点与 $e_j$ 的始点相同，则称 $e_i$ 与 $e_j$ 相邻。
• 图中没有关联的顶点称为孤立点。

顶点的邻域

• 无向图：
  • 邻域：$N_G(v) = \lbrace u \ | \ u \in V(G) \land \exists e_k = (v, u) \in E(G) \land u \neq v \rbrace$
  • 闭邻域：$\overline{N}_G(v) = N_G(v) \cup \lbrace v \rbrace$
  • 关联集：$I_G(v) = \lbrace e_k \ | \ e_k = (v, u) \in E(G) \rbrace$
• 有向图：
  • 后继元集：$\Gamma_D^+(v) = \lbrace u \ | \ u \in V(D) \land \exists e_k = \langle v, u \rangle \in E(D) \land u \neq v \rbrace$
  • 先驱元集：$\Gamma_D^-(v) = \lbrace u \ | \ u \in V(D) \land \exists e_k = \langle u, v \rangle \in E(D) \land u \neq v \rbrace$
  • 邻域：$N_D = \Gamma_D^+(v) \cup \Gamma_D^-(v)$
  • 闭邻域：$\overline{N}_D(v) = N_D(v) \cup \lbrace v \rbrace$

多重图与简单图

• 平行边：若存在 $e_k = e_0$，则称 $e_k$ 是 平行边。平行边的个数称为重数。
• 多重图：存在平行边的图。
• 简单图：无平行边和环的图。

顶点的度

• 度：$d(v) = |\lbrace e_k \ | \ e_k = (v, u) \in E(G) \lor e_k = \langle v, u \rangle \in E(D) \lor e_k = \langle u, v \rangle \in E(D) \rbrace|$

• 入度：$d^-(v) = |\lbrace e_k \ | \ e_k = \langle u, v \rangle \in E(D) \rbrace|$

• 出度：$d^+(v) = |\lbrace e_k \ | \ e_k = \langle v, u \rangle \in E(D) \rbrace|$

• $d(v) = d^-(v) + d^+(v)$

• $\Delta(G) = max\lbrace d(v) \ | \ v \in V(G) \rbrace$ 称为图 $G$ 的最大度

• $\delta(G) = min\lbrace d(v) \ | \ v \in V(G) \rbrace$ 称为图 $G$ 的最小度

  • 类似的可以定义
  • $\Delta(D)$ 和 $\delta(D)$
  • $\Delta^+(D)$ 和 $\delta^+(D)$
  • $\Delta^-(D)$ 和 $\delta^-(D)$

握手定理

• 无向图 $G = \langle V, E \rangle$，则
  • $\sum_{v \in V} d(v) = 2|E| = 2m$
• 有向图 $D = \langle V, E \rangle$，则
  • $\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = |E| = m$
  • $\sum_{v \in V} d(v) = \sum_{v \in V} (d^+(v) + d^-(v)) = 2m$

推论：奇度顶点的个数为偶数。

度数列

$V = \lbrace v_1, v_2, \cdots, v_n \rbrace$，为无向图 $G$ 的顶点集，称：

• $d(v_1), d(v_2), \cdots, d(v_n)$ 为图 $G$ 的度数列

$V = \lbrace v_1, v_2, \cdots, v_n \rbrace$，为有向图 $D$ 的顶点集，称：

• $d^+(v_1), d^+(v_2), \cdots, d^+(v_n)$ 为图 $D$ 的出度数列
• $d^-(v_1), d^-(v_2), \cdots, d^-(v_n)$ 为图 $D$ 的入度数列
• $d(v_1), d(v_2), \cdots, d(v_n)$ 为图 $D$ 的度数列

对于给定的度数列 $d_1, d_2, \cdots, d_n$，若存在一个 $n$ 阶无向图 $G$，使得 $d(v_1), d(v_2), \cdots, d(v_n)$ 为 $G$ 的度数列，则称 $d$ 是可图化的。

非负整数序列 $d_1, d_2, \cdots, d_n$ 是可图化的当且仅当： $$\sum_{i=1}^{n} d_i = 2 是偶数$$

对任意 $n$ 阶无向简单图 $G$，满足 $\Delta(G) \leq n - 1$ 和 $\delta(G) \geq 0$。

图的同构

若存在双射函数 $f: V_1 \to V_2$，使得对于 $v_i, v_j \in V_1$， $$\begin{aligned} (v_i, v_j) \in E_1 &\Leftrightarrow (f(v_i), f(v_j)) \in E_2 \newline \langle v_i, v_j \rangle \in E_1 &\Leftrightarrow \langle f(v_i), f(v_j) \rangle \in E_2 \end{aligned}$$ 且 $(v_i, v_j)$ 与 $(f(v_i), f(v_j))$ 的重数相同，则称 $G_1$ 与 $G_2$ 同构。 （$\langle v_i, v_j \rangle$ 与 $\langle f(v_i), f(v_j) \rangle$ 的重数相同） 记作 $G_1 \cong G_2$。

图之间的同构关系具有 自反性、对称性和传递性 。 能找到多条同构的必要条件，但它们全不是充分条件；

• 边数相同；
• 顶点数相同；
• 度数列相同；
  判断两个图同构是个难题

图的分类

完全图与竞赛图

• $n$ 阶无向完全图：$K_n = \langle V, E \rangle$，其中 $V = \lbrace v_1, v_2, \cdots, v_n \rbrace$，$E = \lbrace (v_i, v_j) \ | \ 1 \leq i < j \leq n \rbrace$
  • $\displaystyle m = \frac{n(n-1)}{2}$
  • $\Delta = \delta = n - 1$
• $n$ 阶有向完全图：$K_n^d = \langle V, E \rangle$，其中 $V = \lbrace v_1, v_2, \cdots, v_n \rbrace$，$E = \lbrace \langle v_i, v_j \rangle \ | \ 1 \leq i \neq j \leq n \rbrace$
  • $m = n(n-1)$
  • $\Delta = \delta = 2(n-1)$
  • $\Delta^+ = \delta^+ = n - 1$
  • $\Delta^- = \delta^- = n - 1$
• $n$ 阶无向竞赛图：基图为 $K_n$ 的有向简单图。
  • $\displaystyle m = \frac{n(n-1)}{2}$
  • $\Delta = \delta = n - 1$

正则图

设 $G$ 为 $n$ 阶无向简单图，若 $\forall v \in V(G), d(v) = k$，则称 $G$ 为 $k$ - 正则图。 $$m = \frac{kn}{2}$$

子图

$G = \langle V, E \rangle$，$G’ = \langle V’, E’ \rangle$

• 子图：$G’ \subseteq G$，当且仅当 $V’ \subseteq V$ 且 $E’ \subseteq E$，称 $G’$ 为 $G$ 的子图，$G$ 为 $G’$ 的母图。
• 生成子图：$G’ \subseteq G$ 且 $V’ = V$，称 $G’$ 为 $G$ 的生成子图。
• 真子图：$V’ \varsubsetneqq V$ 或 $E’ \varsubsetneqq E$，称 $G’$ 为 $G$ 的真子图。
• 导出子图：
  • $V’ \varsubsetneqq V$ 且 $V’ \neq \varnothing$，以 $G$ 中两个端点都在 $V’$ 中的边组成边集 $E’$，称 $G’ = \langle V’, E’ \rangle$ 为 $G$ 的 $V’$ 导出的子图。记作 $G[V’]$。
  • $E’ \varsubsetneqq E$ 且 $E’ \neq \varnothing$，以 $G$ 中两个端点都在 $E’$ 中的顶点组成顶点集 $V’$，称 $G’ = \langle V’, E’ \rangle$ 为 $G$ 的 $E’$ 导出的子图。记作 $G[E’]$。

补图

$G = \langle V, E \rangle$，$G’ = \langle V, E’ \rangle$，其中 $E’ = \lbrace (v_i, v_j) \ | \ v_i, v_j \in V \land (v_i, v_j) \notin E \land i \neq j \rbrace$，称 $G’$ 为 $G$ 的补图。记作 $\overline{G}$。 即添加上 $G$ 中不在 $K_n$ 中的边。

若 $G \cong \overline{G}$，则称 $G$ 为自补图。

删除与增加边与顶点

• 删除边：$G - e_k = \langle V, E - \lbrace e_k \rbrace \rangle$
• 删除顶点：$G - v_i = \langle V - \lbrace v_i \rbrace, E - \lbrace e_k \ | \ e_k = (v_i, v_j) \in E \lor e_k = \langle v_j, v_i \rangle \in E \rbrace \rangle$
• 边的收缩：从 $G$ 中删除 $e$ 后，将 $e$ 的两个端点合并为一个顶点，得到的图称为 $G$ 的边的收缩。记作 $G \backslash e$。
• 新加边：$G + e_k = \langle V, E \cup \lbrace e_k \rbrace \rangle$

在收缩边和新加边的过程可能会产生平行边和环。

通路与回路

设 $\varGamma$ 为 $G$ 中顶点与边的交替序列，即 $\varGamma = v_0 e_1 v_1 e_2 \cdots e_l v_l$ 称 $\varGamma$ 为 $G$ 中的通路，$v_0, v_l$ 分别称为 $\varGamma$ 的始点和终点，$l$ 称为 $\varGamma$ 的长度。

• 通路与回路：
  • 若 $v_0 = v_l$，则称 $\varGamma$ 为回路。
• 简单通路与简单回路：
  • 所有边互不相同的通路称为简单通路。
  • 所有边互不相同的回路称为简单回路。
• 初级通路（路径）与初级回路（圈）：
  • 顶点互不相同的简单通路称为初级通路。也称为路径。
  • 顶点互不相同的简单回路称为初级回路。也称为圈。
  • 若存在 $v_i$ 到 $v_j$ 的通路，则必定存在长度小于或等于 $n - 1$ 的初级通路。
  • 若存在 $v_i$ 回到自身的回路，则必定存在长度小于或等于 $n$ 的初级回路。
• 复杂通路与复杂回路：
  • 有重复边的通路称为复杂通路。
  • 有重复边的回路称为复杂回路。

环 是长度为 $1$ 的圈。

图的连通性

无向图

• 顶点之间的连通关系：$G = \langle V, E \rangle$ 为无向图
  • 若 $v_i$ 到 $v_j$ 有通路，则 $v_i \sim v_j$
  • $\sim$ 是 $V$ 上的等价关系
  • 定义 $v_i$ 与自身连通
• $G$ 的连通性与连通分支
  • 连通：若 $\forall u, v \in V$，$u \sim v$，则称 $G$ 连通
  • 连通分支：$V/R = {V_1, V_2, \cdots, V_k}$，$V_i$ 为 $G$ 的连通分支，$k = 1$ 时 $G$ 连通。连通分支的个数记为 $p(G)$。

短线程与距离

• 短线程：$v_i$ 到 $v_j$ 的短线程是 $v_i$ 到 $v_j$ 的最短通路
• 距离：$d(u, v)$ 是 $u$ 到 $v$ 的短线程的长度
  • $d(u, v) \ge 0$
  • $u \not\sim v \Rightarrow d(u, v) = \infty$
  • $u = v \Rightarrow d(u, v) = 0$
  • $d(u, v) = d(v, u)$
  • $d(u, v) \le d(u, w) + d(w, v)$

割点与割边

$G = \langle V, E \rangle$ 为无向图，若存在 $V’ \varsubsetneqq V$，使得 $p(G - V’) > p(G)$，且对于任意 $V’’ \varsubsetneqq V$，$p(G - V’’) = p(G)$，则称 $V’$ 为 $G$ 的点割集。 若 $V’ = \lbrace v \rbrace$，则称 $v$ 为 $G$ 的割点。

$G = \langle V, E \rangle$ 为无向图，若存在 $E’ \varsubsetneqq E$，使得 $p(G - E’) > p(G)$，且对于任意 $E’’ \varsubsetneqq E$，$p(G - E’’) = p(G)$，则称 $E’$ 为 $G$ 的边割集。 若 $E’ = \lbrace e \rbrace$，则称 $e$ 为 $G$ 的割边或桥。

连通度

设 $G$ 为无向连通图且不是完全图，则称 $$\kappa(G) = min\lbrace |V’| \ | \ V’ \text{ 是 } G \text{ 的割点集} \rbrace$$ 为 $G$ 的点连通度，简称连通度。简记为 $\kappa$。

• 完全图：$\kappa(K_n) = n - 1$
• 树：$\kappa(T) = 1$
• 非连通图：$\kappa(G) = 0$
• k-连通图：$\kappa(G) \textcolor{cyan}{\ge} k$
  • 删除任意 $k - 1$ 个顶点后，图仍然连通

称 $$\lambda(G) = min\lbrace |E’| \ | \ E’ \text{ 是 } G \text{ 的割边集} \rbrace$$ 为 $G$ 的边连通度。简记为 $\lambda$。

• 完全图：$\lambda(K_n) = n - 1$
• 树：$\lambda(T) = 1$
• 非连通图：$\lambda(G) = 0$
• r-边连通图：$\lambda(G) \textcolor{cyan}{\ge} r$
  • 删除任意 $r - 1$ 条边后，图仍然连通

$$\kappa \le \lambda \le \delta$$

有向图

• 顶点之间的可达关系：$D = \langle V, E \rangle$ 为有向图
  • 若 $v_i$ 到 $v_j$ 有通路，则 $v_i$ 可达 $v_j$，记作 $v_i \to v_j$
  • 若 $v_i \to v_j$ 且 $v_j \to v_i$，则称 $v_i$ 与 $v_j$ 相互可达，记作 $v_i \leftrightarrow v_j$
  • 定义 $v_i$ 可达自身
  • $\leftrightarrow$ 是 $V$ 上的等价关系

短线程与距离

距离记作 $d\langle u, v \rangle$，定义与无向图相同。 类似无向图的定义，只不过无对称性。

连通图

• 弱连通图：$D$ 的基图是连通图，则称 $D$ 为弱连通图，简称连通图。
• 单向连通图：$\forall u, v \in V$，$u \to v$ 或 $v \to u$，则称 $D$ 为单向连通图。
• 强连通图：$\forall u, v \in V$，$u \leftrightarrow v$，则称 $D$ 为强连通图。

强连通 $\Rightarrow$ 单向连通 $\Rightarrow$ 弱连通

• 判定定理：
  • $D$ 单向连通当且仅当 $D$ 中存在经过每个节点至少一次的通路。
  • $D$ 强连通当且仅当 $D$ 中存在经过每个节点至少一次的回路。

图的矩阵表示

关联矩阵

无向图

$(m_{ij})_{n \times m} = v_i \text{ 与 } e_j \text{ 相关联的次数}$ 记作 $M(G) = (m_{ij})_{n \times m}$

有向图

$(m_{ij})_{n \times m} =\begin{cases} 1, & \text{若 } v_i \text{ 为 } e_j \text{ 的始点} \newline -1, & \text{若 } v_i \text{ 为 } e_j \text{ 的终点} \newline 0, & \text{其他} \end{cases}$

邻接矩阵

$(a_{ij})_{n \times n} = v_i \text{ 到 } v_j \text{ 边的条数}$ 记作 $A(D) = (a_{ij})_{n \times n}$

$A^{l}_{ij}$ 表示 $v_i$ 到 $v_j$ 的长度为 $l$ 的通路的条数。

可达矩阵

$(p_{ij})_{n \times n} =\begin{cases} 1, & \text{若 } v_i \text{ 到 } v_j \text{ 可达} \newline 0, & \text{其他} \end{cases}$ 记作 $P(D) = (p_{ij})_{n \times n}$

图的运算

$G_1 = \langle V_1, E_1 \rangle$，$G_2 = \langle V_2, E_2 \rangle$

• 若 $V_1 \cap V_2 = \varnothing$，则称 $G_1$ 和 $G_2$ 是不交的。

• 若 $E_1 \cap E_2 = \varnothing$，则称 $G_1$ 和 $G_2$ 是边不交的或边不重的。

• 并图：

  • 边集：$E_1 \cup E_2$
  • 顶点集：$V_1 \cup V_2$
  • 记作 $G_1 \cup G_2$

• 交图：

  • 边集：$E_1 \cap E_2$
  • 顶点集：$V’ = \lbrace v \ | \ \exists u, (v, u) \in E_1 \cap E_2 \lor \exists u, (u, v) \in E_1 \cap E_2 \rbrace$
  • 记作 $G_1 \cap G_2$

• 差图：

  • 边集：$E_1 - E_2$
  • 顶点集：$V’ = \lbrace v \ | \ \exists u, (v, u) \in E_1 - E_2 \lor \exists u, (u, v) \in E_1 - E_2 \rbrace$
  • 记作 $G_1 - G_2$

• 环和图：

  • 边集：$E_1 \oplus E_2 = (E_1 - E_2) \cup (E_2 - E_1)$
  • 顶点集：$V’ = \lbrace v \ | \ \exists u, (v, u) \in E_1 \oplus E_2 \lor \exists u, (u, v) \in E_1 \oplus E_2 \rbrace$
  • 记作 $G_1 \oplus G_2$

扩大路径法

扩大路径法

$G = \langle V, E \rangle$ 为无向图，且 $E \neq \varnothing$，取一条初始路径 $\varGamma_l$，将该路径外与该路径的始点和终点相邻的顶点加入路径，得到新路径 $\varGamma_{l+1}$，重复该过程，直到无法再加入新的顶点为止。
最后得到的路径为 $\varGamma_{l + k}$，称为极大路径。
使用该方法证明问题的方法称为扩大路径法。

二部图

二部图

$G = \langle V, E \rangle$ 为无向图，若 $V$ 可分为两个互不相交的子集 $V_1$ 和 $V_2$，使得 $E$ 中的每条边的两个端点分别属于 $V_1$ 和 $V_2$，则称 $G$ 为二部图（也称二分图 或 偶图）。
称 $V_1$ 和 $V_2$ 为 $G$ 的互补顶点子集。
常将二部图记作 $G = \langle V_1, V_2, E \rangle$。

完全二部图

$\forall v_1 \in V_1, v_2 \in V_2$，$(v_1, v_2) \in E$，则称 $G$ 为完全二部图。 记为 $K_{r, s}$，其中 $r = |V_1|$，$s = |V_2|$。

二部图的判定

$G$ 为二部图当且仅当 $G$ 中不含奇圈。

欧拉图与哈密顿图

欧拉图

• 欧拉通路：经过图中每条边一次且仅一次的通路称为欧拉通路。
• 欧拉回路：经过图中每条边一次且仅一次的回路称为欧拉回路。
• 欧拉图：包含欧拉回路的图称为欧拉图。
• 半欧拉图：包含欧拉通路但不包含欧拉回路的图称为半欧拉图。

规定 平凡图 是欧拉图。 欧拉通路与欧拉回路是 简单通路与简单回路

判定定理

无向图

无向图 $G$ 是欧拉图的充要条件是 $G$ 是连通的且每个顶点的度数都是偶数。
无向图 $G$ 是半欧拉图的充要条件是 $G$ 是连通的且恰有两个顶点的度数是奇数。

有向图

有向图 $D$ 是欧拉图的充要条件是 $D$ 是强连通的且每个顶点的入度等于出度。
有向图 $D$ 是半欧拉图的充要条件是 $D$ 是强连通的且恰有两个顶点的度数是奇数。

欧拉图的性质

$G$ 是非平凡欧拉图当且仅当 $G$ 是连通的且为若干个边不重的圈的并。

非环非平凡欧拉图 $G$ 满足： $$\lambda(G) \geq 2$$ 即 $G$ 中没有桥。

哈密顿图

• 哈密顿通路：经过图中每个顶点一次且仅一次的通路称为哈密顿通路。
• 哈密顿回路：经过图中每个顶点一次且仅一次的回路称为哈密顿回路。
• 哈密顿图：包含哈密顿回路的图称为哈密顿图。
• 半哈密顿图：包含哈密顿通路但不包含哈密顿回路的图称为半哈密顿图。

规定 平凡图 是哈密顿图。 哈密顿通路与哈密顿回路是 初级通路与初级回路 。

必要条件

设 $G = \langle V, E \rangle$ 是一个哈密顿图，则对于任意 $V_1 \varsubsetneq V$，且 $V_1 \neq \varnothing$，有： $$p(G - V_1) \leq \left|V_1\right|$$ 其中 $p(G)$ 表示 $G$ 的 连通分支数 。

设 $G = \langle V, E \rangle$ 是一个半哈密顿图，则对于任意 $V_1 \varsubsetneq V$，且 $V_1 \neq \varnothing$，有： $$p(G - V_1) \leq \left|V_1\right| + 1$$

充分条件

设 $G$ 是 $n$ 阶无向简单图，若对于任意不相邻的顶点 $v_i, v_j$，有： $$d(v_i) + d(v_j) \geq n - 1$$ 则 $G$ 中存在哈密顿通路。

若： $$d(v_i) + d(v_j) \geq n$$ 则 $G$ 中存在哈密顿回路。

树

树

• 无向树：连通无回路的无向图，简称树。
• 平凡树：平凡图。
• 森林：有若干个不相交的树组成的图。
• 树叶：度为1的节点。
• 分支点：度大于1的节点。

无向树的等价定义

• $G$ 是树（连通无回路）。
• $G$ 中任意两个顶点之间存在惟一的路径。
• $G$ 中无回路且 $m=n-1$.。
• $G$ 是连通的且 $m=n-1$。
• $G$ 是连通的且 $G$ 中任何边均为桥。
• $G$ 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈.。

无向树的性质

设 $T$ 是 $n$ 阶非平凡的无向树，则 $T$ 中至少有两片树叶。

平面图

平面图的基本概念

• 平面图：若能将无向图 $G$ 无边相交地画在平面上，称 $G$ 为平面图或可平面图。
• 平面嵌入：画出的无边相交的平面图称为平面嵌入。
• 非平面图：不能画出无边相交的平面图的图称为非平面图。

面与次数

• 面：由 $G$ 的平面嵌入所分割出的区域称为面。
  • 无限面或外部面：无穷大的面。用 $R_0$ 表示。
  • 有限面或内部面：有限大的面。用 $R_1, R_2, \cdots$ 表示。
• 边界：面 $R_i$ 是包围它的边的组成的回路组。
• 次数：面 $R_i$ 的次数是与边界的长度，即边数，记作 $deg(R_i)$。

握手定理

在平面图中，各面的次数之和等于边数的两倍。 $$\sum_{i=1}^{n} deg(R_i) = 2m$$

极大平面图

极大平面图：在平面图 $G$ 中再加一条边，就会使 $G$ 变成非平面图的图称为极大平面图。

极大平面图的性质

极大平面图是连通的，且 $n(n \geq 3)$ 阶极大平面图中不可能有割点和桥。

$G$ 为 $n(n \geq 3)$ 阶极大平面图当且仅当 $G$ 是简单平面图，且 $G$ 的每个面的次数都为 $3$。

极小非平面图

极小非平面图：在非平面图 $G$ 中去掉一条边，就会使 $G$ 变成平面图的图称为极小非平面图。

极小非平面图必为 简单图 。

欧拉公式

设 $G$ 是一个 $n$ 阶 $m$ 条边 $r$ 个面的连通平面图，则 $$n - m + r = 2$$

欧拉公式的推论

若 $G$ 为 $k$ 个连通分支的平面图，则 $$n - m + r = k + 1$$

由 握手定理 可得，对于联通的平面图，有 $$m \leq \frac{l}{l-2}(n-2)$$ $$m \leq \frac{l}{l-2}(n-k-1)$$ 其中 $l = min\lbrace deg(R_i) \rbrace$。

证明： $$2m = \sum_{i=1}^{r} deg(R_i) \geq r \cdot l \geq (n - k - 1) \cdot l$$

根据 握手定理 和 极大平面图的性质 ，可得 设 $G$ 为 $n$ 阶 $m$ 条边的极大平面图，则 $$m = 3n - 6$$

若 $G$ 为 $n(n \geq 3)$ 阶 $m$ 条边的简单平面图，则 $$m \leq 3n - 6$$ 注意，此推论为简单平面图的必要条件，不是充分条件。

设 $G$ 为简单平面图，则 $$\delta(G) \leq 5$$ 用反证法证明。

平面图的判断

插入 $2$ 度顶点与消去 $2$ 度顶点

• 插入 $2$ 度顶点：设 $e = (u, v)$ 为 $G$ 的一条边，$u$ 与 $v$ 之间插入一个顶点 $w$，并将 $e$ 替换为 $(u, w)$ 和 $(w, v)$ 两条边，称作在 $G$ 中插入 $2$ 度顶点 $w$。
• 消去 $2$ 度顶点：设 $w$ 为 $G$ 的一个 $2$ 度顶点，$w$ 与 $u$ 和 $v$ 相连，将 $w$ 与 $u$ 和 $v$ 相连的两条边替换为一条边 $e = (u, v)$，并删除 $w$，称作在 $G$ 中消去 $2$ 度顶点 $w$。

同胚

若 $G_1$ 与 $G_2$ 在反复进行插入 $2$ 度顶点和消去 $2$ 度顶点的操作后 同构 ，则称 $G_1$ 与 $G_2$ 同胚。

平面图判定定理

1. $G$ 是平面图 $\Leftrightarrow$ $G$ 不含同胚于 $K_5$ 或 $K_{3,3}$ 的子图。
2. $G$ 是平面图 $\Leftrightarrow$ $G$ 中无 可 收缩 的 $K_5$ 或 $K_{3,3}$ 子图。

平面图的对偶图

设 $G$ 是某平面图的某个平面嵌入，构造 $G$ 的对偶图如下：

1. $G$ 的每个面 $R_i$ 对应 $G^*$ 的一个顶点 $v_i$。
2. $G$ 的每条边对应 $G^*$ 的一条边。即若 $e$ 是 $R_i$ 和 $R_j$ 的边界，则 $v_i$ 和 $v_j$ 之间有一条边。
   • 若 $e$ 是 $R_i$ 的边界且是桥，即 $e$ 只属于 $R_i$，则 $v_i$ 与自身有一条边。

对偶图的性质

$G^*$ 是 $G$ 的对偶图，则

1. $G^*$ 也是平面图，且是平面嵌入。
2. $G^{*}$ 是连通图。
3. 若 $G$ 是连通图，则 $\left(G^{*}\right)^* \cong G$。
4. $G$ 中的环对应 $G^*$ 中的桥，$G$ 中的桥对应 $G^*$ 中的环。
5. $n^* = r, m^* = m, r^* = n - k + 1$。
6. 设 $G^*$ 中的顶点 $v_i^*$ 位于 $G$ 的面 $R_i$ 的内部，则 $d(v_i^*) = deg(R_i)$。

若 $G^* \cong G$，则称 $G$ 是自对偶图。

轮图

轮图定义如下： 在 $C_{n-1}$（$n \geq 4$）边形内放置一个顶点，使得这个顶点与 $C_{n-1}$ 上的所有顶点均相邻。所得的 $n$ 阶简单图称为 n阶轮图，常记为 $W_n$。

• 当 $n$ 为奇数时，称为 奇阶轮图。
• 当 $n$ 为偶数时，称为 偶阶轮图。

轮图是自对偶图

着色

点着色

• 图的点着色
  图 $G$ 的一种点着色是指：给图 $G$ 的每个顶点涂上一种颜色，使得相邻的顶点具有不同的颜色。

• k着色
  对图 $G$ 进行 $k$ 着色（称 $G$ 是 $k$-可着色的），即能够用 $k$ 种颜色给 $G$ 的顶点着色。

• 图的色数
  图 $G$ 的色数 $\chi(G) = k$，意味着图 $G$ 是 $k$-可着色的，但不是 $(k-1)$-可着色的。即能给图着色的最少颜色数。

色数的上下界

$$\chi(G) \leq \Delta(G) + 1$$
$\chi(K_n) = n$，$\chi(K_{m,n}) = 2$。
$\chi(G) \leq \Delta(G)$，当且仅当 $G$ 不是完全图。（Brooks 定理）
偶圈的色数为 $2$，奇圈的色数为 $3$。
$\chi(W_n) = \begin{cases} 3 & n \text{ 为奇数} \newline 4 & n \text{ 为偶数} \end{cases}$

Welch-Powell 算法

1. 对图的顶点按度数从大到小排序。
2. 从度数最大的顶点开始，给每个顶点涂色，在序列中找到最近且不相邻的顶点的颜色，涂上该颜色。
3. 重复步骤 2，直到所有顶点都被涂色。

在许多实际情况下，Welch-Powell算法的表现非常好，但它不一定会得到图的最小着色数。

地图着色与平面图的点着色

• 地图：联通无桥平面图的平面嵌入与所有的面。
• 国家：地图的面。
• 相邻：两个国家至少有一条公共边。

地图的面着色

• 地图的面着色
  给地图的每个国家涂上一种颜色，使得相邻的国家具有不同的颜色。
• k-面可着色
  能够用 $k$ 种颜色给地图的国家着色。
• 地图的面着色数
  地图的面着色的最少颜色数。记作 $\chi^*(G)$。

地图的面着色转化为对偶图的点着色问题。
地图 $G$ 是 $k$-面可着色的当且仅当对偶图 $G^*$ 是 $k$-可着色的。

四色定理

地图的面着色数 $\chi^*(G) \leq 4$。

边着色

• 图的边着色
  图 $G$ 的一种边着色是指：给图 $G$ 的每条边涂上一种颜色，使得相邻的边具有不同的颜色。
• k-边可着色
  对图 $G$ 进行 $k$ 边着色（称 $G$ 是 $k$-边可着色的），即能够用 $k$ 种颜色给 $G$ 的边着色。
• 图的边着色数
  图 $G$ 的边着色数 $\chi’(G) = k$，意味着图 $G$ 是 $k$-边可着色的，但不是 $(k-1)$-边可着色的。即能给图边着色的最少颜色数。

边着色的上下界

Vizing 定理：对于任意无向简单图 $G$，有 $$\Delta(G) \leq \chi’(G) \leq \Delta(G) + 1$$
$\displaystyle \chi’(K_n) = \begin{cases} n & n \text{ 为奇数} \newline n - 1 & n \text{ 为偶数} \end{cases}$，$\chi’(K_{m,n}) = \Delta$。
$n \ge 4$ 时，$\chi’(W_n) = n - 1$。
偶圈的边着色数为 $2$，奇圈的边着色数为 $3$。