第一章 基本概念

图的概念

相关定义与性质

• 二元组 $(V(G),E(G))$ 称为图。其中 $V(G)$ 是非空集合，称为结点集，$E(G)$ 是 $V(G)$ 诸结点之间边的集合。常用 $G=(V,E)$ 表示图。
• 图可以分为有限图与无限图两类。
• 本书只讨论有限图，即 $V$ 和 $E$ 都是有限集。
• 图 $G$ 的边可以是有方向的，也可以是无方向的。它们分称为有向边（或弧）和无向边，用 $e_{k}=\left(v_{i},v_{j}\right)$ 表示。这时我们说 $v_{i}$ 与 $v_{j}$ 是相邻结点；$e_{k}$ 分别与 $v_{i}$，$v_{j}$ 相关联。
• 如果 $e_{k}$ 是有向边，称 $v_{i}$ 是 $e_{k}$ 的始点，$v_{j}$ 是 $e_{k}$ 的终点；并称 $v_{i}$ 是 $v_{j}$ 的直接前趋，$v_{j}$ 是 $v_{i}$ 的直接后继。
• 如果 $e_{k}$ 是无向边，则称 $v_{i}$，$v_{j}$ 是 $e_{k}$ 的两个端点。
• 全部由有向边构成的图叫有向图；只由无向边组成的图叫无向图；既有有向边又有无向边构成的图称为混合图。
• 只与一个结点相关联的边称为自环，在同一对结点之间可以存在多条边，称之为重边。含有重边的图叫多重图。
• $G=(V,E)$ 的某结点 $v$ 所关联的边数称为该结点的度，用 $d(v)$ 表示。如果 $v$ 带有自环，则自环对 $d(v)$ 的贡献为 $2$。
• 关联于同一对结点的多条边（有向边应同向）称为平行边
• 平行边的条数称为边的重数
• 不含平行边（任意两结点间最多只有一条边）和自环的无向图或有向图称为简单图
• 没有任何边的简单图叫空图，用 $N_{n}$ 表示
• 只含一个结点的空图称为平凡图
• 任何两结点间都有边的简单图称为完全图，用 $K_{n}$ 表示。$K_{n}$ 中每个结点的度都是 $n-1$。
• $K_{n}$ 的边数是 $\frac{1}{2} n(n-1)$
• 一个简单有向图，其中每一对不同的顶点都只有一对边相连，称为完全有向图
• 每个结点的度都相同的图，若其度均为 $k$，则称为 k-正则图。完全图是(n-1)-正则图
• 有向图中由于各边都是有向边，因此每个结点 $v$ 还有其正度 $\left(d^{+}(v)\right)$ 和负度 $\left(d^{-}(v)\right)$。$d^{+}(v)$ 的值是以 $v$ 为始点的边的数目，$d^{-}(v)$ 是以 $v$ 为终点的边的数目。显然有 $d^{+}(v)+d^{-}(v)=d(v)$。
• 握手定理：设 $G=(V,E)$ 有 $n$ 个结点，$m$ 条边，则 $$\sum_{v \in V(G)} d(v)=2 m$$
• $G$ 中度为奇数的结点必为偶数个
• 有向图 $G$ 中正度之和等于负度之和。
• 非空简单无向图中一定存在度相同的结点。
• 如果图 $G=(V,E)$ 的每条边 $e_{k}=\left(v_{i},v_{j}\right)$ 都赋以一个实数 $w_{k}$ 作为该边的权，则称 $G$ 是赋权图。特别地，如果这些权都是正实数，就称 $G$ 是正权图。
• 给定 $G=(V,E)$，如果存在另一个图 $G^{\prime}=\left(V^{\prime},E^{\prime}\right)$，满足 $V^{\prime} \subseteq V$，$E^{\prime} \subseteq E$，则称 $G^{\prime}$ 是 $G$ 的一个子图。
  • 如果 $V^{\prime}=V$，就称 $G^{\prime}$ 是 $G$ 的支撑子图或生成子图（只能删除边，结点不变）
  • 如果 $V^{\prime} \subseteq V$，且 $E^{\prime}$ 包含了 $G$ 在结点子集 $V^{\prime}$ 之间的所有边，则称 $G^{\prime}$ 是 $G$ 的导出子图。（删除结点及其关联的边）
  • 如果 $V^{\prime}=V$，$E^{\prime}=E$ 或者 $E^{\prime}=\varnothing$，则称为平凡子图。
• 给定两个图 $G_{1}=\left(V_{1},E_{1}\right)$，$G_{2}=\left(V_{2},E_{2}\right)$。
  • $G_{1}$ 和 $G_{2}$ 的并 $G_{1} \cup G_{2}=(V,E)$，其中 $V=V_{1} \cup V_{2}$，$E=E_{1} \cup E_{2}$
  • $G_{1}$ 和 $G_{2}$ 的交 $G_{1} \cap G_{2}=(V,E)$，其中 $V=V_{1} \cap V_{\cdot 2}$，$E=E_{1} \cap E_{2}$
  • $G_{1}$ 和 $G_{2}$ 的对称差 $G_{1} \oplus G_{2}= (V,E)$，其中 $V=V_{1} \cup V_{2}$，$E=E_{1} \oplus E_{2}$
• 在 $G$ 中删去一个子图 $H$，指删掉 $H$ 中的各条边，记作 $G-H$
  • 特别地，对于简单图 $G$，称 $K_{n}-G$ 为 $G$ 的补图，记作 $\bar{G}$。
• 从 $G$ 中删去某个结点 $v$ 及其关联的边所得的图记作 $G-v$
  • $G-v$ 是 $G$ 的导出子图
• 从 $G$ 中删去某特定的边 $e = (u, v)$ 所得的图记作 $G-e$
  • $G-e$ 是 $G$ 的支撑子图
• 在 $G$ 中增加某条边 $e_{i j}$，可记作 $G+e_{i j}$
• 如果 $G$ 是无向图，则 $\Gamma(v)={u \mid (v,u) \in E}$ 称为 $v$ 的邻点集
• 设 $v$ 是有向图 $G$ 的一个结点，则 $$\Gamma^{+}(v)=\{u \mid(v,u) \in E\}$$ 称为 $v$ 的直接后继集或外邻集 $$\Gamma^{-}(v)=\{u \mid(u,v) \in E\}$$ 称为 $v$ 的直接前趋集或内邻集
• 两个图 $G_{1}=\left(V_{1},E_{1}\right)$，$G_{2}=\left(V_{2},E_{2}\right)$，如果 $V_{1}$ 和 $V_{2}$ 存在双射函数 $\mathrm{f}$，且 $(u,v) \in E_{1}$，当且仅当 $(f(u),f(v)) \in E_{2}$ 时，并且这两条边的重数相同，称 $G_{1}$ 和 $G_{2}$ 同构，记作： $\boldsymbol{G}_{\mathbf{1}} \cong \boldsymbol{G}_{\mathbf{2}}$
• $G_{1} \cong G_{2}$ 的必要条件：
  • $\left|V\left(G_{1}\right)\right|=\left|V\left(G_{2}\right)\right|$，$\left|E\left(G_{1}\right)\right|=\left|E\left(G_{2}\right)\right|$
  • $G_{1}$ 和 $G_{2}$ 结点度的非增序列相同
  • 存在同构的导出子图

度序列可图性判断

图的代数表示

邻接矩阵

• 邻接矩阵表示了结点之间的邻接关系。
• 有向图的邻接矩阵 $\boldsymbol{A}$ 是一个 $n$ 阶方阵，其元素为 $$a_{i j}=\left\{ \begin{array}{ll} 1,& \left(v_{i},v_{j}\right) \in E \\ 0,& \text { 其他 } \end{array} \right.$$
• 邻接矩阵 $\boldsymbol{A}$ 第 $i$ 行非零元的数目恰是 $v_i$ 的正度，第 $j$ 列非零元的数目是 $v_j$ 的负度。
• 邻接矩阵可以表示自环，但无法表示重边。
• 无向图的邻接矩阵，是一个对称矩阵

权矩阵

• 赋权图常用权矩阵 $\boldsymbol{A}$ 进行表示。其元素 $$a_{i j}= \left\{ \begin{array}{ll} w_{i j},& \left(v_{i},v_{j}\right) \in E \\ 0,& \text { 其他 } \end{array}\right.$$
• 权矩阵实际即为带权值的邻接矩阵
• 无向图的权矩阵，是一个对称矩阵

关联矩阵

• 关联矩阵表示结点与边之间的关联关系。
• 有向图 $\boldsymbol{G}$ 的关联矩阵 $\boldsymbol{B}$ 是 $n \times m$ 的矩阵，当给定结点和边的编号之后，其元素 $$b_{i j}=\left\{\begin{aligned} 1,& e_{j}=\left(v_{i},v_{k}\right) \in E \\ -1,& e_{j}=\left(v_{k},v_{i}\right) \in Es\ \\ 0, & \text { 其他 } \end{aligned}\right.$$
• 每列两个非零元：-1，1
• 可以表示重边，但无法表示自环
• 第 $i$ 行非零元的数目恰是结点 $v_{i}$ 的度，其中 $1$ 元的数目是 $d^{+}\left(v_{i}\right)$，$-1$ 元的数目是 $d^{-}\left(v_{i}\right)$。
• 类似地，无向图也有其关联矩阵 $\boldsymbol{B}$，但其中不含 $-1$ 元素。

邻接表

（Todo）

第二章 道路与回路

有向图 $G=(V,E)$ 中，若边序列 $P=\left(e_{i 1},e_{i 2},\cdots,e_{i q}\right)$，其中 $e_{i k}=\left(v_{l},v_{j}\right)$ 满足 $v_{l}$ 是 $e_{i k-1}$ 的终点，$v_{j}$ 是 $e_{i k+1}$ 的始点，就称 $P$ 是 $G$ 的一条有向道路。如果 $e_{i q}$ 的终点也是 $e_{i 1}$ 的始点，则称 $P$ 是 $G$ 的一条有向回路。边的数目 $q$ 是道路（回路）的长度。

• 如果 $P$ 中的边没有重复出现，则分别称为简单有向道路和简单有向回路。
• 如果在 $P$ 中结点也不重复出现，又分别称它们是初级有向道路和初级有向回路，简称为路和回路。
• 显然，初级有向道路（回路）一定是简单有向道路（回路）。
• 需要注意的是回路中的结点除始点和终点外不重复出现

无向图 $G=(V,E)$ 中，若点边交替序列 $P=\left(v_{i 1},e_{i 1},v_{i 2},e_{i 2},\cdots,e_{i q-1},v_{i q}\right)$ 满足 $v_{i k},v_{i k+1}$ 是 $e_{i k}$ 的两个端点，则称 $P$ 是 $G$ 中的一条链，或道路。如果 $v_{i q}=v_{i 1}$，则称 $P$ 是 $G$ 中的一个圈，或回路。边的数目 $q$ 称为道路（回路）的长度。

• 如果 $P$ 中没有重复出现的边，称之为简单道路或简单回路
• 若其中结点也不重复，又称之为初级道路或初级回路

• 需要注意的是回路中是的结点是除始点和终点外不重复出现

• 设连通图 $G=(V,E)$ 有 $k$ 个度为奇数的结点，则 $E(G)$ 可以划分为 $k/2$ 条简单道路。

弦

设 $C$ 是简单图 $G$ 中含结点数大于 $3$ 的一个初级回路，如果结点 $v_{i}$ 和 $v_{j}$ 在 $\mathrm{C}$ 中不相邻，而边 $\left(v_{i},v_{j}\right) \in \mathrm{E}(\mathrm{G})$，则称 $\left(v_{i},v_{j}\right)$ 是 $\mathrm{C}$ 的一条弦。

• 若对于每一个 $v_{k} \in \mathrm{V}(\mathrm{G})$，都有 $\mathrm{d}\left(v_{k}\right) \geq 3$，则 $\mathrm{G}$ 中必含带弦的回路。
• 在简单图中，若 $n\ge 4$ 且 $m\ge 2n-3$，则 $G$ 中含有带弦的回路。

极长初级道路

在简单图 $\mathrm{G}=(\mathrm{V},\mathrm{E})$ 中，$\mathrm{E} \neq \varnothing$，设 $P=\left(v_{0},v_{1},\cdots,v_{l}\right)$ 为 $\mathrm{G}$ 中一条初级道路，若路径的始点和终点两个端点 $v_{0}$ 和 $v_{l}$ 不与初级道路本身结点集以外的任何结点相邻，这样的初级道路称为极长初级道路

• 有向图中，初级道路始点的直接前驱集（内邻集），终点的直接后继集（外邻集），都在初级道路本身上。
• 任何一条初级道路，如果不是极长初级道路，则至少有一个端点与初级道路本身以外的结点相邻，则将该结点及其相关联的边扩到新的初级道路中来，得到更新的初级道路。继续上述过程，直到变成极长初级道路为止。
  • 由一条道路扩大的极长道路不一定唯一
  • 极长初级道路不一定是图中的最长初级道路

二分图

$\mathrm{G}=(\mathrm{V},\mathrm{E})$ 是无向图，如果 $\mathrm{V}(\mathrm{G})$ 可以划分为子集 $X$ 和 $Y$，使得所有 $e=(u,v) \in E(G)$，$u$ 和 $v$ 分属于 $\mathrm{X}$ 和 $\mathrm{Y}$，则称 $\mathrm{G}$ 为二分图。

• 二分图的子集 $X$，$Y$ 可能不唯一。
• 如果二分图 $G$ 中存在回路，则它们是由偶数条边组成的。
• $\mathrm{G}=(\mathrm{V},\mathrm{E})$ 是二分图，$\mathrm{V}(\mathrm{G})$ 划分为子集 $X$ 和 $Y$，$X$ 中任一结点与 $Y$ 中每一个结点有且只有唯一一条边相连，则称 $G$ 为完全二分图（完全偶图），记作 $\boldsymbol{K}_{m,n}$，$m=|X|$，$n=|Y|$。
• 含 $K_{3}$ 子图的图一定不是二分图
• $K_{n}$ 不是二分图（$n \geq 3$）

图的连通性

设 $G$ 是无向图，若 $G$ 的任意两结点之间都存在道路，就称 $G$ 是连通图，否则称为非连通图。
如果 $G$ 是有向图，不考虑其边的方向，即视之为无向图，若它是连通的，则称 $G$ 是 （弱）连通图。
若连通子图 $H$ 不是 $G$ 的任何连通子图的真子图，则称 $H$ 是 $G$ 的极大连通子图，或称连通支。

• 显然 $G$ 的每个连通支都是它的导出子图。
• 任何非连通图都是 $2$ 个以上连通支的并集
• 设 $G$ 是简单无向图，当 $m>\frac{1}{2}(n−1)(n−2)$ 时 $G$ 是连通图。
• $G=(V, E)$ 是连通图，则 $m\ge n-1$

两点距离

若 $G$ 的任意两结点 $u,v$ 之间连通，则称 $u,v$ 之间的最短道路为短程线，该短程线的长度称为 $u,v$ 之间的距离，记作 $d(u,v)$。若 $u,v$ 之间不连通，则 $d(u,v)=\infty$

割点和割边

$G$ 图中，一结点 $u$，$G$ 减去 $u$ 后，图的连通分支数上升，则称 $u$ 为图 $G$ 的割点。
$G$ 图中，一边 $e$，$G$ 减去 $e$ 后，图的连通分支数上升，则称 $e$ 为图 $G$ 的割边/桥。

树

在连通图 $G$ 中，若其不含回路，且在任意两结点之间都只有唯一的一条初级道路，就称 $G$ 为树。

• 树是含边数最少的连通图（极小连通子图）。

欧拉道路与回路

无向连通图 $G=(V,E)$ 中的一条经过所有边的简单回路（道路）称为 $G$ 的欧拉回路（道路）。

• 具有欧拉回路的图称为欧拉图
• 无向连通图 $G$ 存在欧拉回路的充要条件是 $G$ 中各结点的度都是偶数。
• 若无向连通图 $G$ 中只有 $2$ 个度为奇的结点，则 $G$ 存在欧拉道路。
• 若有向连通图 $G$ 中各结点的正、负度相等，则 $G$ 存在有向欧拉回路。
• $K_{n, m}$ 中含有欧拉道路当且仅当 $n, m$ 均为偶数

哈密顿道路与回路

无向图的一条过全部结点的初级回路（道路）称为 $G$ 的哈密顿回路（道路），简记为 $H$ 回路（道路）。

• 具有哈密顿回路的图也称为哈密顿图
• 约定：平凡图是哈密顿图
• 哈密顿通路是经过所有结点中长度最短的通路
• 哈密顿回路是经过所有结点中长度最短的回路
• 如果简单图 $G$ 的任意两结点 $v_{i},v_{j}$ 之间恒有 $d\left(v_{i}\right)+d\left(v_{j}\right) \geqslant n-1$，则 $G$ 中存在哈密顿道路。
• 若简单图 $G$ 的任意两结点 $v_{i}$ 和 $v_{j}$ 之间恒有 $d\left(v_{i}\right)+d\left(v_{j}\right) \geqslant n$，则 $G$ 中存在哈密顿回路。
• 若简单图 $G$ 每个结点的度都大于等于 $\frac{n}{2}$，则 $G$ 有 $H$ 回路。
• 设 $G$ 是简单图，$v_{i},v_{j}$ 是不相邻结点，且满足 $d\left(v_{i}\right)+d\left(v_{j}\right) \geqslant n_{\circ}$ 则 $G$ 存在 $H$ 回路的充要条件是 $G+\left(v_{i},v_{j}\right)$ 有 $H$ 回路。
• 如无向图 $G=(V,E)$ 是 $H$ 图，$V_{1}$ 是 $V$ 的任意非空子集，则 $p\left(G-V_{1}\right) \leq\left|V_{1}\right|$，其中 $p\left(G-V_{1}\right)$ 是从 $\mathrm{G}$ 中删除 $V_{1}$ 后的连通支的数目。
• 如无向图 $G=(V,E)$ 存在 $\mathrm{H}$ 道路，$V_{1}$ 是 $V$ 的任意非空子集，则 $p\left(G-V_{1}\right) \leq\left|V_{1}\right|+1$。
• 有割点的图一定不是 $H$ 图
• 如无向图 $G=(V,E)$ 是二分图，
  • 两边结点数不相同，则 $G$ 不存在 $H$ 回路
  • 两边结点数不相同也不相差 $1$，则 $G$ 不存在 $H$ 道路
• $K_{n, m}$ 中含有哈密顿道路当且仅当 $|n-m| \leq 1$
• $K_{n, m}$ 中含有哈密顿回路当且仅当 $n=m$

闭合图

若 $v_{i}$ 和 $v_{j}$ 是简单图 $G$ 的不相邻结点，且满足 $d\left(v_{i}\right)+d\left(v_{j}\right) \geqslant n$，则令 $G^{\prime}=G+\left(v_{i},v_{j}\right)$，对 $G^{\prime}$ 重复上述过程，直至不再有这样的结点对为止。最终得到的图称为 $G$ 的闭合图，记作 $C(G)$。

• 简单图 $G$ 的闭合图 $C(G)$ 是唯一的。
• 简单图 $G$ 存在哈密顿回路的充要条件是其闭合图存在哈密顿回路。
• 设 $G(n \geqslant 3)$ 是简单图，若 $C(G)$ 是完全图，则 $G$ 有 $H$ 回路。

第三章 树

• 给定一个图 $G=(V,E)$，如果它不含任何回路，我们就叫它是（树）林
• 如果 $G$ 又是连通的，即这个林只有一个连通支，就称它是树。
• 一个不含任何回路的连通图称为树，用 $T$ 表示。$T$ 中的边称为树枝，度为 $1$ 的结点称为树叶。
• 树的每条边都不会属于任何回路。这样的边叫割边。
• 设 $e$ 是 $G$ 的一条边，若 $G^{\prime}=G-e$ 比 $G$ 的连通支数增加，则称 $e$ 是 $G$ 的一条割边。
• $e=(u,v)$ 是割边，当且仅当 $e$ 不属于 $G$ 的任何回路。
• 设 $T$ 是结点数为 $n \geqslant 2$ 的树，则下列性质等价：
  • $T$ 连通且无回路。
  • $T$ 连通且每条边都是割边。
  • $T$ 连通且有 $n-1$ 条边。
  • $T$ 有 $n-1$ 条边且无回路。
  • $T$ 的任意两结点间有唯一道路。
  • $T$ 无回路，但在任两结点间加上一条边后恰有一个回路。
• 树 $T$ 中一定存在树叶结点。

生成树

• 如果 $T$ 是图 $G$ 的支撑子图，而且又是一棵树，则称 $T$ 是 $G$ 的一棵支撑树，或称生成树，又简称为 $G$ 的树。
• 任何无向连通图 $G$ 都含有生成树。
• 在赋权连通图 $G$ 中，其总长最小和最大的生成树，就被称为最短树和最长树，亦或称为最小生成树和最大生成树。

Kruskal算法

略

Prime算法

略

二叉树

• 除叶子结点外，其余结点的正度最多为 $2$ 的外向树称为二叉树；
• 二叉树的结点集是有限集合，它或者为空，或者由根结点及两棵互不相交的左右子树的结点集构成，该左右子树也均为二叉树
• 左子树为根结点左侧分叉的子树，右子树为根结点右侧分叉的子树，其严格区分，即使只有一棵子树也要说明是左子树还是右子树；左右子树交换位置，得到一棵新的二叉树
• 若设二叉树的深度为 $h$，除第 $h$ 层外，其它各层 $1~h-1$ 的结点数都达到最大个数，第 $h$ 层所有的结点都连续集中在最左边，这就是完全二叉树。
• 一棵高度（即结点层数）为 $k$，并具有 $2^k−1$ 个结点的二叉树，称为满二叉树
• 如果二叉树 $T$ 的每个叶子结点 $v_i$ 都赋予一个正实数 $w_i$，则称 $T$ 为赋权二叉树
• 给定叶子结点数目以及每个叶子结点对应的权值，可以构造许多不同的赋权二叉树。在这些二叉树中，带权路径总长最小的二叉树，称为最优二叉树

Huffman算法

略