图论 复习笔记

前言

本文章是根据法国国立高等电力技术、电子学、计算机、水力学与电信学校 (E.N.S.E.E.I.H.T.) 第七学期课程*“Graph Theory”* 总结而来的课程笔记。碍于本人学识有限，部分叙述难免存在纰漏，请读者注意甄别。

第一部分：基本概念及定义

无向图

图

一个有限图 $G = (V,E)$ 由非空(non vide) 有限(fini) 顶点集 (sommets / vertex) $V$

$V = \{ v_0, v_1,...,v_{n-1}\}$

和有限边集(Arête / Edge) $E$ 组成。

$E = \{ e_0, e_1,...,e_{n-1}\}$

其中，每个边由一对顶点 $\{ v_i, v_j\}$ 构成。顶点数又被称为图的阶数(ordre)。

相关概念：

• 如果 $n = nb(V)$，那么我们称该图 $G = (V,E)$ 是一个 $n阶图$ (ordre);
• 如果 $e = \{v_i, v_j\}$，我们说边 $e$ 与顶点 $v_i$ 和 $v_j$ 相关 (incidente);
• 如果 $e = \{v_i,v_j\}$，我们说 $v_i$ 和 $v_j$ 是邻接的 (adjacents);
• 两条边是相邻的当且仅当它们有一个共同的顶点;
• $e = \{v_i, v_i\}$ 是一个环 (boucle);
• 两个节点之间可能有多条边的图称为多重图 (multigraphe)。
• 一个图是简单的 (simple)，当且仅当
  • 没有环 (boucle)，
  • 两个顶点之间最多有一条边 (无重边);
• 一个顶点在图中的度 (degree) $δ(v_i)$ 为 与这个顶点 $v_i$ 相连接的边的数目;
• 如果每个顶点彼此相邻，即每两个顶点间都有边相连，则称该图是**完全(complet)**图;

Q1 : n阶简单完全图的边数是多少？

$\# E(n阶简单完全图) = \tfrac{n(n-1)}{2}$

• 无向图中，所有顶点度数之和 $∑deg(v)=2|E|$，即奇数度的顶点数必是偶数。

思考：一种“从无到有”的推广假设

1. 连接两个偶度顶点，这个时候奇度顶点的数量增加2；
2. 连接两个奇度顶点，这个时候奇度顶点的数量减少2；
3. 连接一个奇度顶点和一个偶度顶点，奇度顶点的数量不变。

• **$k$-正则图 (k-regulier)**是指所有顶点的度都为 $k$ 的图;

有向图

如果一个图 $G = (V,E)$ 的点对(或边)是有序的，那么图 $G$ 就是有向的(orienté)。

相关概念：

• 在一个有向弧 $e =(i,j)$ 中，$i$ 被称为 $e$ 的起点(l’origine), $j$ 是 $e$ 的终点( l’arrivée);
• 对于顶点$v$，出度 $δ^+(v)$ 是以 $v$ 为起点的弧的数量;
• 入度 $δ^−(v)$ 是以 $v$ 为终点的弧的数量;
• 总度数 $δ(v) = δ^+(v) + δ^−(v)$ , $∑_{v \in V} δ(v) = 2 \times nb(E)$。

子图（sous-graphe）

由图 $G = (V,E)$ 的顶点 $V$的子集 $V ' ⊂ V$ 生成的 $G' = (V' , E' )$ 是 $G$ 的子图。其中 $E'$ 表示 $E$ 的两个端点都在 $V'$ 中的所有边。

$G=(V,E) \quad \stackrel{V'⊂V} \longrightarrow \quad G'=(V',E')$

• 子图：点和边都能在原图中找到
• 母图：原图
• 真子图：不等于母图的子图
• 生成子图：包含所有顶点的子图
• 基础简单图：从一个图中去掉所有重边及环后所得的剩余图称为基础简单图
• 点导出子图：顶点是原图顶点的子集且加入两端都在子集中的边构成的图
• 边导出子图：由原图边集的子集及其所有端点构成的图

完全子图

$IF(子图 \; is\; 完全图)\quad THEN(完全子图)$

团（clique）

$G$ 的完全子图是 $G$ 的团，当且仅当 $G'$ 不包含在 $G$ 的更大的完全子图中，也就是说 $G'$ 是 $G$ 的极大完全子图。

由上图所示，1 和 2 就是原图的两个团。其中 1 是最大团。

最大团

$G$ 的最大团是指 $G$ 的所有团中，含顶点数最大的团，比如说 1 就是最大团。

部分图（graphe partiel）

由 $E' ⊂ E$ 生成的 $G = (V,E)$ 的部分图是图 $G'= (V,E')$。

$G=(V,E) \quad \stackrel{E'⊂E} \longrightarrow \quad G'=(V,E')$

关联矩阵（matrice d’incidence）

设任意图 $G=(V,E)$，其中顶点集 $V=v_1,v_2,...,v_n$，边集 $E=e_1,e_2,...,e_ε$。用 $m_{ij}$ 表示顶点 $v_i$ 与边 $e_j$ 关联的次数，可能取值为 $0,1,2,…$，称所得矩阵 $\mathcal{M}(G)=(m_{ij})_{n×ε}$ 为图G的关联矩阵

类似地，有向图 $D$ 的关联矩阵 $\mathcal{M}(D)=(m_{ij})_{n×ε}$的元素 $m_{i×j}$定义为：

$m_{ij}=\begin{cases} 1 \qquad v_i是有向边a_j的始点\\ -1 \qquad v_i是有向边a_j的终点\\ 0 \qquad v_i是有向边a_j的不关联点 \end{cases}$

邻接矩阵（matrice d’adjacence）

设无向图 $G=(V,E)$ ，其中顶点集$V=v_1,v_2,...,v_n$，边集 $E=e_1,e_2,...,e_ε$。用 $a_{ij}$ 表示顶点 $v_i$ 与顶点 $v_j$ 之间的边数，可能取值为 $0,1,2,…$，称所得矩阵 $A=A(G)=(a_{ij})_{n×n}$ 为图$G$ 的邻接矩阵

若干性质：

• $\mathcal{A}(G)$ 为对称矩阵
• 若 $G$ 为无环图，则 $\mathcal{A}(G)$ 中第 $i$ 行（列）的元素之和等于顶点 $v_i$ 的度
• 两图 $G$ 和 $H$ 同构的充要条件是存在置换矩阵 $\mathcal{P}$ 使得 $\mathcal{A}(G) = \mathcal{P}^T\mathcal{A}(H) \mathcal{P}$

类似地，有向图 $D$ 的邻接矩阵$=\mathcal{A}(D)(a_{ij})_{n×n}$， $a_{ij}$ 表示从始点 $v_i$ 到终点 $v_j$ 的有向边的条数，其中 $v_i$ 和 $v_j$ 为 $D$ 的顶点。

示例，求图中有向图的邻接矩阵和关联矩阵（图中边上的数字为边的编号，而非权重）：

邻接矩阵为：

$\begin{bmatrix} 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 \end{bmatrix}$

关联矩阵为：

$\begin{bmatrix} 1 & 0 & 0 & -1 & 1 & 0\\ -1 & 1 & 0 & 0 & 0 & -1\\ 0 & 0 & -1 & 1 & 0 & 1\\ 0 & -1 & 1 & 0 & -1 & 0 \end{bmatrix}$

加权图（graphe pondéré）

如果每条弧与正的实际权重 (poids) 相关联，则对图进行加权。

第二部分：连通

链（Chaîne）

长度为 $q ∈ N$ 的链 $(e_1, ..., e_q)$ 是 $q$ 个连续相邻边的序列。 因此存在一个顶点序列 $(v_1,...,v_{q+1})$，使得 $v_i$ 是 $e_{i-1}$ 和 $e_i$ 的端点。

相关概念：

• 该链被称为连接 顶点 $v_1$ 和 $v_{q+1}$ 的链；

• 简单链 (simple)：在边的序列中各边互不相同

  • 简单链也可称其为 迹 (trace)

• 基本链 (élémentaire)：在顶点的序列中各顶点互不相同

  • 基本简单链可以称其为 路 (chemin)：序列中的边和顶点都不相同

• 如果 $v_1 = v_{q+1}$，则链是**闭合 (fermée)**的；

• $q$ 是链的长度。

环（Cycle）

• 环是一个**闭合 (fermée)**的单链；

• 两个顶点间的距离 (Distance) 是两个顶点间最短链的长度；

• 图的直径 (Diamètre) 是图的两个顶点之间的最大距离。 如果有未连接的顶点，则为 $+∞$（连接性的定义在后面）。

• 无环图 $G$ 最多有 $n-1$ 条边

  proof：

  $\# E_{一般无环图} \le \# E_{无环连通图} = n-1$

• 如果遍历的顶点除了第一个和最后一个之外是互不相同的，则环是基本的 (élémentaire)。

​ 例1：在下图的无向图中，

1. 链 $(1,2,5,1,3,5,1)$ 是一条非基本 (non-élémentaire) 闭合 (fermée) 链
2. 链 $(1,2,5,1,3,)$ 是一条非基本 (non-élémentaire) 非闭合 (non-fermée) 链
3. 基本环（基本闭合链）：$(1,2,5,1)$
4. 非基本环（非基本闭合链）：$(1,2,5,1,3,5,4,1)$

例2 ：在下图的有向图中，

1. 基本路径 (chemin: non-fermée) ：$(1,4,2,3)$
2. 非基本路径：$(1,3,1,4)$
3. 基本环 (circuit)：$(1,4,2,3,1)$
4. 非基本环 (circuit)：$(1,3,1,4,2,1)$

割点及割边

割点

【定义】设连通图 $G=(V,E)$ 中有 $v_i \in V$，如果 $G - v_i$ 的分支数大于 $G$ 的分支数，即在图 $G$ 中删去 $v_i$ 点后 $G$ 不再连通，则我们称 $v_i$ 是 $G$ 的一个割点。

• 每个非平凡图至少有两个顶点不是割点

  证明：

  由于 $G$ 是无环非平凡连通图，所以存在非平凡生成树．非平凡生成树至少两片树叶，它们不能为生成树的割点．显然，它们也不能为 $G$ 的割点．

  注：非平凡树一定有割边，不一定有割点 ($K_2$).

• 有割点的图不是哈密顿图

【性质】设连通图 $G=(V,E)$ 中有 $v_i \in V$ ，则下列命题等价

• $v_i$ 是 $G$ 的一个割点
• $∃ v_x,v_y \in V， v_x \ne v_y， v_x 与 v_y 间所有的路均通过 v_i$
• （上一条的普遍推广）$∃ \; V \setminus \{v_i\} 的划分\{U,W\}(U \cap W = \emptyset)，使得\forall u \in U, \forall w \in W: u,w间的路均通过v_i$

割边（桥）

设图 $G=(V,E)$ 中有 $e_i \in E$，如果 $G - e_i$ 的分支数大于 $G$ 的分支数，即在图 $G$ 中删去 $e_i$ 点后 $G$ 不再连通，则我们称 $e_i$ 是 $G$ 的一个割边，也称做桥。

【性质】设连通图 $G=(V,E)$ 中有 $e_i \in E$ ，则下列命题等价

• $e_i$ 是 $G$ 的一个割边
• $∃ e_x,e_y \in E， e_x \ne e_y， e_x 与 e_y 间所有的路均"通过" e_i$
• （上一条的普遍推广）$∃ \; E \setminus \{e_i\} 的划分\{U_E,W_E\}(U_E \cap W_E = \emptyset)，使得\forall u_e \in U, \forall w_e \in W: u_e,w_e间的路均"通过"e_i$
• $e_i$ 不在 $G$ 的任何圈中

连通度

• 点连通度可描述为“使图不连通或成为平凡图，最少需要删去的点数”，记作 $\kappa (G)$

• 边连通度可描述为“使图不连通或成为平凡图，最少需要删去的边数”，记作 $\lambda (G)$

【性质】

1. 对于不连通或平凡图 $G$ ：$\kappa (G) = \lambda (G) = 0$
2. 对于树 $T$：$\kappa (G) = \lambda (G) = 1$
3. 对于有割点的图 $G$ ：$\kappa (G) = 1$
4. 对于有割边（桥）的图 $G$ ：$\lambda (G) = 1$
5. 对于完全图 $K_p$ ：$\kappa (G) = \lambda (G) = p-1$
6. $图G连通 \Leftrightarrow \kappa (G) \ge 1$
7. 对于一个环（圈）$C_n, n ≥ 3$：$κ(C_n) = 2$

除了 $\kappa (G)$ 和 $\lambda (G)$ 以外，图的最小度 $\delta (G)$ 也可以用来描述图 $G$ 的连通程度。即

$设 G 是 n 阶简单图，若 δ(G) ≥ ⌊\frac{n}{2}⌋，则 G 必连通，且 λ(G) = δ(G)．$

证明：

若 $G$ 不连通，则 $G$ 至少有两个连通分支，从而必有一个分支 H 满足

$|V(H)| ≤ ⌊\frac{n}{2}⌋$

因 $G$ 是简单图，从而

$∆(H) ≤ ⌊\frac{n}{2}⌋ − 1 < ⌊\frac{n}{2}⌋$

于是

$δ(G) ≤ δ(H) ≤ ∆(H) < ⌊\frac{n}{2}⌋$

这与已知矛盾，所以 $G$ 必连通．

【定理】对任意的图 $G=(V,E)$，有

$κ(G) ≤ λ(G) ≤ δ(G)$

连通图（Graphe connexe）

• 在一个无向图 $G$ 中，若从顶点 ${ v_{i}}$ 到顶点 $v_{j}$ 有路径相连（当然从 $v_{j}$ 到 $ v_{i}$也一定有路径），则称$ v_{i}$ 和 $v_{j}$ 是**连通 (connexe)**的。

  • 如果 $G$ 是有向图，那么连接 $v_{i}$ 和 $v_{j}$ 的路径中所有的边都必须同向。

• 如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。连通度是指为了让图分解成孤立的子图所要删除的顶点数的最小值。

• 设连通图 $G$ 有 $n$ 个顶点，则该图 $G$ 至少有 $n-1$ 条边

  Proof:

  A graph with $n$ vertices and no edge has $n$ components. Adding an edge reduces the number of components by at most one. So beginning with a graph with no edge, adding one edge at a time till the graph has $k$ edges results in reducing the number of components by at most $k$. Thus, a graph with $n$ vertices and $k$ edges has at least $n−k$ components. Hence every graph with $n$ vertices and fewer than $n-1$ edges has at least two components, and is disconnected. Therefore every connected graph with $n$ vertices must have at least $n-1$ edges; the path $P_n$ is an example of such a graph

弱连通

一个有向图被称作弱连通(weakly connected)的，如果将所有有向边替换为无向边之后的无向图是连通的，如果对于任意一对顶点 $u$ ，$v$，或者存在一条从 $u$ 到 $v$ 的有向路径，或者存在一条从 $u$ 到 $v$ 的有向路径，则该图是单连通(unilaterally conncected)的。

$对于任意一对顶点(u,v),\; 存在路径u \to v,\; 不存在路径v\to u$

强连通

如果对于如果对于任意一对顶点 $u$，$v$，同时存在一条从 $u$ 到 $v$ 的有向路径和一条从 $v$ 到 $u$ 的有向路径，则该图是强连通(strongly connected)的

$对于任意一对顶点(u,v),\; 存在路径u \to v,\; 且存在路径v\to u$

二元关系

集合 $X$ 与集合 $Y$ 上的二元关系是 $\mathcal{R}=(X,Y,G(\mathcal{R}))$，其中 $G(\mathcal{R})$，称为 $\mathcal{R}$ 的图，是笛卡儿积 $X\times Y$ 的子集。若 $(x,y) ∈ G(\mathcal{R})$ ，则称 $x\;与\;y\;有关系于 \mathcal{R}$，并记作 $x\mathcal{R}y$ 或 $\mathcal{R}(x,y)$。

否则称 $x \; 与 \; y \; 无关系\mathcal{R}$。但经常地我们把关系与其图等同起来，即：若 $\mathcal{R}⊆X×Y$，则 $\mathcal{R}$ 是一个关系。

关系的性质

关系的性质主要有以下五种：自反性，反自反性，对称性，反对称性和传递性。

• 自反性 (réfexivité)：在集合 $X$ 上的关系 $\mathcal{R}$ ，如对任意 $x \in E$，有 $(x,x) \in \mathcal{R}$，则称R是自反的。

$\forall x \in E,\quad x \mathcal{R} x$

• 非自反性（自反性的否定的强型式）：在集合 $X$ 上的关系 $\mathcal{R}$ ，如对任意 $x\in X$，有 $(x,x)\notin R$，则称R是非自反的。

$\forall x\in A, (x,x)\notin \mathcal{R}$

• 对称性 (symétrie)：在集合 $X$ 上的关系 $\mathcal{R}$，如果有 $(x,y) \in \mathcal{R}$ 则必有 $(y,x) \in \mathcal{R}$，则称R是对称的。

$\forall (x,y) \in E^2,\quad x \mathcal{R} y \Rightarrow y \mathcal{R} x$

• 非对称性（对称性的否定的强形式）：

$\forall (x,y) \in E^2, \quad (x,y) \in \mathcal{R} \Rightarrow (y,x) \notin \mathcal{R}$

• 反对称性（不是对称性的否定）：

$\forall (x,y) \in E^2, \quad ((x \mathcal{R} y) \land (y \mathcal{R} x) \Rightarrow x=y)$

• 传递性 (transitivité)：

$\forall (x,y,z) \in E^3, \quad ((x \mathcal{R} y) \land (y \mathcal{R} z) \Rightarrow x \mathcal{R} z$

设 $\mathcal{R}$ 为集合 $E$ 上的关系，下面给出 $\mathcal{R}$ 的五种性质成立的充要条件：

1. $\mathcal{R}$ 在 $E$ 上自反，当且仅当$I_{E}\subseteq \mathcal{R}$
2. $\mathcal{R}$ 在 $E$ 上非自反，当且仅当 $\mathcal{R} \cap I_{E}=\emptyset $
3. $\mathcal{R}$ 在 $E$ 上对称，当且仅当 $\mathcal{R} = \mathcal{R} ^{-1}$
4. $\mathcal{R}$ 在 $E$ 上反对称，当且仅当 $ \mathcal{R} \cap \mathcal{R}^{-1}\subseteq I_{E}$
5. $\mathcal{R}$ 在 $E$ 上非对称，当且仅当 $\mathcal{R} \cap \mathcal{R}^{-1}= \emptyset$
6. $\mathcal{R}$ 在 $E$ 上传递，当且仅当 $\mathcal{R} \circ \mathcal{R}\subseteq \mathcal{R}$

等价关系（ Relation d’équivalence）

等价关系也称为同值关系（英语：Equivalence relation）即设 $\mathcal{R}$ 是某个集合 $E$ 上的一个二元关系。若 $\mathcal{R}$ 满足以下条件（充分必要）：

1. 自反性 (réfexivité)：$\forall x \in E, \quad x \mathcal{R} x$
2. 对称性 (symétrie)：$\forall (x,y) \in E^2, \quad x \mathcal{R} y \Rightarrow y \mathcal{R}x$
3. 传递性 (transitivité)：$\forall (x,y,z) \in E^3, \quad ((x \mathcal{R} y) \land (y \mathcal{R} z) \Rightarrow x \mathcal{R} z$

例如，设 $E={1,2,...,8}$，定义 $E$上的关系 $\mathcal{R}$ 如下：

$x \mathcal{R} y \Longleftrightarrow \forall (x,y) \in E, x \equiv y(mod \; 3)$

其中，$x \equiv y(mod \; 3)$ 叫做 $x$ 与 $y模3$ 同余，即 $x$ 除以3的余数 与 $y$ 除以3的余数相等。例子有$1\mathcal{R} 4$，$2\mathcal{R}5$，$3\mathcal{R}6$。不难验证 $\mathcal{R}$ 为 $E$ 上的等价关系。

并非所有的二元关系都是等价关系。一个简单的反例是比较两个数中哪个较大：

• 没有自反性：任何一个数不能比自身为较大 $n\ngtr n$
• 没有对称性：如果 $m>n$，就肯定不能有 $n>m$

等价类（Classe d’équivalence）

令 $\mathcal{R}$ 是集合 $E$ 上的等价关系，$x$ 是 $E$ 的元素。我们称 $x$ 的等价类为 $E$ 中与 $x$ 相关的所有元素的集 $[x]$：

$[x] = {y ∈ E,x\mathcal{R}y}$

• 设 $\mathcal{R}$ 为集合 $E$ 上的等价关系，两个等价类不相交或相等。

  证明：

  $\begin{aligned} IF (v_k = \{v_j\} \cup \{v_i\}) \quad & THEN(v_i \mathcal{R} v_k,\;v_j \mathcal{R} v_k \Rightarrow v_i \mathcal{R} v_j \Rightarrow [v_i]=[v_j]) \\ & ELSE(\{v_j\} \cap \{v_i\} = \emptyset) \end{aligned}$

• 设 $\mathcal{R}$ 是集合 $E$ 上的等价关系，等价类的集合是 $E$ 的一个部分。

• 设 $G$ 是一个无向图（或有向图），当且仅当存在一条连接 $v_i$ 到 $v_j$ 的链（分别是从 $v_i$ 到 $v_j$ 的路径和从 $v_j$ 到 $v_i$ 的路径）时，由 $v_i \mathcal{R} v_j$ 在顶点集上定义的关系 $\mathcal{R}$ 到 $v_i$ 是等价关系。

连通分量（Composantes connexes）

无向图 $G$ 的极大连通子图称为 $G$ 的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。对于分量中任意两点 $u,v$，必然可以从 $u$ 走到 $v$，且从 $v$ 走到 $u$。

如下图所示，

强连通分量（Composantes fortement connexes）

有向图 $G= (V,E)$ 的极大强连通子图称为 $G$ 的强连通分量，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。极大连通分量。一个连通分量加上任何一些点都不是连通分量了，该连通分量就是强连通分量。

强连通分量的作用： 将任意有向图通过 缩点(将所有连通分量缩成一个点) 转换成有向无环图( $DAG$ )。如下图所示，

• 前驱：$Pred (S \subseteq V_{ertex}) = \{v' | v \in S, (v',v) \in E_{dge}\}$
• 后继：$Succ (S \subseteq V_{ertex}) = \{v' | v \in S, (v,v') \in E_{dge}\}$

我们还通过以下方式定义前驱和后继的自反和传递闭包：

• $Pred^* (S \subseteq V_{ertex}) = S \cup Pred^* (Pred(S))$
• $Succ^* (S \subseteq V_{ertex}) = S \cup Succ^* (Succ(S))$

Demoucron 算法

CFG_G <- ∅空集
WHILE (有一个顶点不在 CFC_G 子集的并集中)
DO
	选择 v ∈ V 不出现 CFC_G 子集的并集
	CFC_v <- SUCC*({v}) ∩交集 Pred*({v})
	CFC_G <- CFC_G ∪并集 {CFC_v}
END

例：应用 Demoucron 算法找出下图中的强连通分量：

• $CFC_G = \emptyset$
• $\begin{aligned} CFC_{v_1} & = \{1,2,3,7,5,6,8,4,10,9\} \quad \leftarrow 顺箭头方向_{Succ} \\ & \quad \cap \; \{ 1,4,5,3,6,2,7,9,10\} \quad \leftarrow 逆箭头方向_{Pred} \\ & = \{ 1,2,3,4,5,6,7,9,10\} \end{aligned}$
• $v_8 \;并不在上一轮的\;CFC_v 中$
• $CFC_G = \{ [1] , [8] \} \rightarrow \{ [8] \}_{seul}$

树（Arbre）

树是一个无环连通图。森林由若干个树连接得来（无环）。

• 由 $k$ 颗树组成的森林满足 $m = n − k$，其中 $n$ 为 $G$ 的顶点数，$m$ 为 $G$ 的边数．

Theorem:

$每棵非平凡树至少有两片树叶$

证明 :

设 $d_1 ≤ d_2 ≤ · · · ≤ dn$ 是树 $T$ 的度序列，因为 $T$ 是连通的，所以树 $T$ 的最小度 $δ(T) = d_1 ≥ 1$. 如果树 $T$ 中至多有一片树叶，那么 $2n − 2 = 2m(T) = \sum_{i=1}^n d_i ≥ 1 + 2(n − 1)$ , 出现矛盾．

$n := \text{NB of vertex}\\ m := \text{NB of Edge}\\ t := \text{NB of vertex with 1 degre}\\ \because \text{G is a tree}\quad \therefore \text{G is a connected graph}\\ \therefore \sum \delta(v) = 2m = 2(n-1) \quad \text{according to n=m-1} \\ \because \sum_{\delta(v) \ge 2} \delta(v) \ge 2(n-t)+t \\ \therefore 2(n-1) \ge 2(n-t)+t \quad \Rightarrow \quad t \ge 2$

设 $G$ 是具有 $n$ 个点 $m$ 条边的图，则下列命题等价：

1. $G$ 是树；
2. $G$ 无环且任意两个不同点之间存在唯一的路；
3. $G$ 连通，删去任一边便不连通；
4. $G$ 连通，且 $n = m - 1$；
5. $G$ 无圈，且 $n = m - 1$；
6. $G$ 无圈，添加任何一条边可得唯一的圈。

生成树

$G$ 的生成树（arbre couvrant）是具有 $G$ 的全部顶点，但边数最少的连通子图。

若有图 $G=(V_G, E_G)$ 和树 $T = (V_T, E_T)$，有 $V_T = V_G$ 且 $E_T \subset E_G$，那么我们说树 $T$ 是图 $G$ 的生成树。

最小生成树

带权图的生成树中，总权重最小的称为最小生成树。

求取最小生成树的算法：一种贪心算法

1. 新建图 $G$， $G$ 中拥有原图中相同的节点，但没有边；
2. 将原图中所有的边按权值从小到大升序；
3. 从权值最小的边开始，如果这条边连接的两个节点于图 $G$ 中不在同一个连通分量中，则添加这条边到图 $G$ 中；
4. 重复3，直至图 $G$ 中所有的节点都在同一个连通分量中；

第三部分：Euler 图与 Hamilton 图

欧拉图

• 无向图

  1. 经过 $G$ 的所有边的链被称为 Euler 链
  2. 经过 $G$ 的所有边的环（闭合的链）被称为 Euler 回路

• 有向图

  1. 经过 $G$ 的所有边的通路被称为 Euler 通路
  2. 经过 $G$ 的所有边的回路（闭合的通路）被称为 Euler 回路

• 存在 Euler 环或 Euler 回路的图叫做 Euler 图。

Theorem

假定 $G$ 是一个连通图，则下列命题等价：

1. $G$ 是欧拉图；

2. $G$ 的每个点的度都是偶数 或 只有 2 个顶点是奇数度，其余均为偶数度；

   • 连通无向图 $G$ 是欧拉图当且仅当 $G$ 的每个顶点都是偶度顶点

   • 连通无向图 $G$ 中存在连接顶点 $u,v$ 的欧拉链当且仅当只有 $u$ 和 $v$ 是奇度顶点

3. $G$ 的边集能划分为边不重的环的并。

性质

• 无向图

  1. 连通无向图 $G$ 是欧拉图当且仅当 $G$ 的每个顶点都是偶度顶点
  2. 连通无向图 $G$ 中存在连接顶点 $u,v$ 的欧拉链当且仅当只有 $u$ 和 $v$ 是奇度顶点

• 有向图

  1. 强连通图有向图 $D$ 是欧拉回路 当且仅当 $D$ 中的**每个顶点的出度数和入读数相同**
  2. 单向连通有向图 $D$ 有从顶点 $u$ 到 $v$ 的欧拉通路当且仅当 $u$ 的出度数比入度数大 1， $v$ 的入度数比出度数大 1， $D$ 中其他顶点入度数和出度数相同

寻找 Euler 回路算法：Hierholzer 算法

Hierholzer算法用于在连通图寻找欧拉迹，其流程非常简单。

从一个可能的起点出发，进行深度优先搜索，但是每次沿着辅助边从某个顶点移动到另外一个顶点的时候，都需要删除这个辅助边。如果没有可移动的路径，则将所在结点加入到栈中，并返回。

最后得到的栈中保存的就是整个欧拉闭迹中的顶点。

dfs(node, trace){
	while(!node.adj.isEmpty()){
		Node next = node.adj.removeLast();
		dfs(next, trace);
	}
	trace.addLast(node);
}

哈密顿图

• 无向图：

  1. 经过 $G$ 的每个结点一次且仅一次的链被称为 Hamilton 链
  2. 经过 $G$ 的每个结点一次且仅一次的环为 Hamilton 环

• 有向图

  1. 经过 $G$ 的每个结点一次且仅一次的链基本通路被称为 Hamilton 通路
  2. 经过 $G$ 的每个结点一次且仅一次的基本回路为 Hamilton 回路

• Hamilton 图：存在 Hamilton 回路 或 Hamilton 环的图叫做 Hamilton 图。

性质

• 若存在 $v_i \in V$，当 $v_i$ 的度数 $\delta(v_i) =1$ 且阶数 $n>1$ 时，不为哈密顿图
• 若存在 $v_i ∈ V$，当 $v_i$ 的度数 $δ(v) = 2$，那么与 $v_i$ 相关的两条边属于任何哈密顿环。
• $K_n$ 是哈密顿图
• 有向完全图中必存在哈密顿通路
• 强连通的有向完全图中必存在哈密顿回路

哈密顿图的判断方法

• Theorem (Ore，充分条件)

  对于阶 $n ≥ 3$ 的简单图 $G$，如果 $G$ 中的任意两个不相邻顶点 $u$ 与 $v$，都有：

  $\delta(u) + \delta(v) ≥ n，$

  那么 $G$ 是哈密顿图。( 注：上述定理只是充分条件，而非必要条件，例如长度为 5 的圈．)

  证明：

  等效地表明，每个非哈密顿图G都不满足条件。因此，令 $G$ 为非哈密顿图的 $n≥3$ 个顶点上的图，并通过一次不增加哈密顿边数加一个边，由 $G$ 形成 $H$，直到无法再增加边。

  令 $u$ 和 $v$ 为 $H$ 中的任何两个不相邻的顶点。然后将边 $(u, v)$ 添加到 $H$，将创建至少一个新的哈密顿回路，并且在 $H$ 中的此回路中的 $(u,v)$ 以外的边一定会形成哈密顿路径 $v_1, v_2, ... v_n$，其中 $u = v_1$，$v = v_n$。

  对于 $2≤i≤n$ 范围内的每个指数 $i$，考虑 $H$ 中从 $v_1$ 到 $v_i$ 和从 $v_(i-1)$ 到 $v_n$ 的两个可能边。在 $H$ 中最多可以存在这两个边之一，否则周期 $v_1,v_2 ... v_(i-1), v_n, v_{(n-1)} ... v_i$ 将是哈密顿回路。

  因此，入射到 $v_1$ 或 $v_n$ 的边的总数最多等于 $i$ 的选择数，即 $n-1$。因此，$H$不服从属性，这要求该边的总数 $δ(v_1) + δ(v_n)$ 大于或等于 $n$。由于 $G$ 的顶点度最多等于 $H$ 的度数，因此得出 $G$ 也没有服从特性的结论。

  

• Theorem (Dirac，充分条件)

  对于 $n ≥ 3$ 的简单图 $G$，如果 $G$ 中有：

  $\delta(G) ≥ \frac{n}{2}$

  那么 $G$ 是哈密顿图。( 注：上述定理只是充分条件，而非必要条件，例如长度为 5 的圈．)

二分图（Graphe biparti）

二分图又称作二部图，是图论中的一种特殊模型。 设 $G=(V,E)$ 是一个无向图，如果顶点 $V$ 可分割为两个互不相交的子集$A$,$B$)，并且图中的每条边 $(v_i, v_j)$ 所关联的两个顶点 $v_i$ 和 $v_j $ 分别属于这两个不同的顶点集 ($v_i \in A$ , $v_j \in B$)，则称图 $G$ 为一个二分图。

简而言之，就是顶点集 $V$ 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

如下图，

完全二分图：$V_1$ 的所有顶点都链接到 $V_2$的任何顶点。互补顶点子集分别有 $p$ 个顶点和 $q$ 个顶点的完全二分图记为 $𝐾_{𝑝,𝑞}$

性质

• 如果一个图 $G=(V,E)$ 是二分图，且 $| nb(V_1) - nb(V_2)| > 1$，则 $G$ 即不是哈密顿图，也不是半哈密顿图
• 若无向图 $G$ 中有长度为奇数的闭合链，则在 $G$ 中有长度为奇数的圈
• 非平凡无向图 $G$ 是二分图当且仅当 $G$ 中的每个圈的长度都是偶数

第四部分：最短路径问题

Dijkstra 最短路径算法

Dijkstra算法是一种经典的基于贪心的单源最短路算法，其要求图中的边全部非负。

算法描述

1. 算法思想：

设 $G=(V,E)$ 是一个带权有向图（或无向图），把图中顶点集合 $V$ 分成两组，

1. 第一组为已求出最短路径的顶点集合（用 $S$ 表示，初始时 $S$ 中只有一个源点，以后每求得一条最短路径 , 就将加入到集合 $S$ 中，直到全部顶点都加入到 $S$ 中，算法就结束了），
2. 第二组为其余未确定最短路径的顶点集合（用 $U$ 表示），按最短路径长度的递增次序依次把第二组的顶点加入 $S$ 中。在加入的过程中，总保持从源点 $v_0$ 到 $S$ 中各顶点的最短路径长度不大于从源点 $v_0$ 到 $U$ 中任何顶点的最短路径长度。

此外，每个顶点对应一个距离，$S$ 中的顶点的距离就是从 $v_0$ 到此顶点的最短路径长度，$U$ 中的顶点的距离，是从 $v_0$ 到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2. 算法伪代码：

DIJKSTRA(G, w, s)
    // s的当前最短路长度是0，其他节点的当前最短路长度是+∞。
    INITIALIZE-SINGLE-SOURCE(G, s)
    // S是节点集合（V的子集），其中每个节点u都已经求得了全图最短路。
    // 初期所有节点都没求得全图最短路。
    S ← ∅
    // Q是一个节点的优先队列，包含所有尚未求得全图最短路的节点。Q中的节点按照当前最短路的长度从小到大排序。
    // 初期所有节点都没求得全图最短路，所以都在Q中。
    Q ← V[G]
    // 循环直到Q中所有节点都清空（都移动到S），即所有节点都已经求出全图最短路。
    while Q ≠ ∅
        // 从Q中取出当前最短路长度最小的节点u
        // 并认为u的当前最短路就是全图最短路。（这个不是那么显然，后续有说明）
        do u ← EXTRACT-MIN(Q)
            // 将u放进集合S中，即标注为“已求得u的全图最短路”。
            S ← S∪{u}
            // 对于u的每个邻接点v
            for each vertex v∈Adj[u]
                // 更新v的当前最短路。
                // 具体策略是：有一个从s到v的新路径，即“从s走全图最短路到u，再从u到v”。
                // 这个新路径可能比v的当前最短路长，也可能比v的当前最短路短。（这个不那么显然，后续有说明）
                // 如果新路径比v的当前最短路短，就把v的当前最短路替换为这条新路径。
                do RELAX(u, v, w)

3. 算法步骤：

1. 初始时，$S$ 只包含源点，即 $S＝\{v_0\}$，$v_0$ 的距离为 $0$。$U$ 包含除 $v_0$ 外的其他顶点，即 : $U=\{其余顶点\}$，若 $v_0$ 与 $U$ 中顶点 $v_i$ 有边，则 $(v_0,v_i)$ 正常有权值，若 $v_0$ 不是 $v_i$ 的出边邻接点，则 $(v_0,v_i)$ 权值为 $∞$。
2. 从 $U$ 中选取一个距离 $v_0$ 最小的顶点 $v_k$ ，把 $v_k$ 加入 $S$ 中（该选定的距离就是 $v_0$ 到 $v_k$ 的最短路径长度）。
3. 以 $v_k$ 为新考虑的中间点，修改 $U$ 中各顶点的距离；若从源点 $v_0$ 到顶点 $v_i$ 的距离（经过顶点 $v_k$）比原来距离（不经过顶点 $v_k$）短，则修改顶点 $v_i$ 的距离值，修改后的距离值的顶点 $v_k$ 的距离加上边上的权。
4. 重复步骤 2 和 3，直到所有顶点都包含在 $S$ 中。

例：如下图所示，求出从 0 出发到 4 的最短路径。

【思路】：

1. 每次从没标记的节点中选择距离出发点最近的节点标记、收录到最优路径集合中；
2. 计算刚加入的节点 A 到临近节点 B 的距离（不包含已标记节点），若 $(节点A的距离 + 节点A到节点B的距离) < 节点B的距离$，则选择更小的那个路径，更新节点B的距离和前驱点pred
3. 标记完所有的节点

【解】

1. 将 [0] 放入集合：

	0	[1]	2	3	4	5	6	7	8
dist	0	4	$∞$	$∞$	$∞$	$∞$	$∞$	8	$∞$
pred	\	0	\	\	\	\	\	0	\

2. 将 [1] 放入集合：

	0	1	2	3	4	5	6	[7]	8
dist	0	4	12	$∞$	$∞$	$∞$	$∞$	$8^*$	$∞$
pred	\	0	1	\	\	\	\	0	\

注意⚠️：* 路径 $0 \to 1 \to 7$ 的距离为 $4+11=15$，而有路径 $0 \to 7$ 的距离为 8，小于前者。所以我们选择路径 $0 \to 7$，并更新表。以下步骤与此类次，不再单独列出。

3. 将 [7] 放入集合：

	0	1	2	3	4	5	[6]	7	8
dist	0	4	12	$∞$	$∞$	$∞$	9	8	15
pred	\	0	1	\	\	\	7	0	7

4. 将 [6] 放入集合：

	0	1	2	3	4	[5]	6	7	8
dist	0	4	12	$∞$	$∞$	11	9	8	15
pred	\	0	1	\	\	6	7	0	7

5. 将 [5] 放入集合：

	0	1	[2]	3	4	5	6	7	8
dist	0	4	12	25	21	11	9	8	15
pred	\	0	1	5	5	6	7	0	7

6. 将 [2] 放入集合：

	0	1	2	3	4	5	6	7	[8]
dist	0	4	12	19	21	11	9	8	14
pred	\	0	1	2	5	6	7	0	2

7. 将 [8] 放入集合：由于与 8 相邻的节点都已经加入集合，所以可以跳过这一步

	0	1	2	[3]	4	5	6	7	8
dist	0	4	12	19	21	11	9	8	14
pred	\	0	1	2	5	6	7	0	2

8. 将 [3] 放入集合：

	0	1	2	3	[4]	5	6	7	8
dist	0	4	12	19	21	11	9	8	14
pred	\	0	1	2	5	6	7	0	2

9. 将 [4] 放入集合：

	0	1	2	3	4	5	6	7	8
dist	0	4	12	19	21	11	9	8	14
pred	\	0	1	2	5	6	7	0	2

10. 遍历完毕，我们现在就得到了从 0 到该图中所有点的最短路程 (shortest distance)。欲求出 $0 \to 4$ 的路径，我们可以从 4 出发，沿着 pred 的顺序到推出最短路径 (shortest path)，即

$4 \leftarrow 5 \leftarrow 6 \leftarrow 7 \leftarrow 0$

对于有向图，大体思路与无向图一致，注意边的方向即可，顺方向为可达，逆方向为不可达（即 $∞$ ）

第五部分：平面图 及 图的上色问题

平面图（Graphe planire）

• 如下图，如果一个图 $G$ 可以在平面上绘制，并且其边不相交 （边不一定是直线），则称该图是平面图。
  • 平面图所在的特定平面称为地图（carte）；
  • 将地图划分为几个区域称为面（face）；
    • 内部面：每个区域内部连同边界称为 $G$ 的内部面
    • 外部面：无界的区域
    • 注：每个平面图有且仅有一个外部面。

• 而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。

  • 完全图 $K_5$和完全二分图 $K_{3,3}$ (汤玛森图) 是最“小”的非平面图。

• 面的次数：设 $f$ 是 $G$ 的一个面，构成 $f$ 的边界的边数（割边算两次）称为 $f$ 的次数， 记作 $deg(f)$

  • 定理：设平面图 $G$ 有 $m$ 条边，$G$ 的所有面的集合为 $\psi$， 则

    $\sum _{f \in \psi} deg(f) = 2m$

• 这实际上是一个研究图的拓扑方面的问题。 更一般地，人们可以问一个图形是否可以在表面 S 上表示的问题

欧拉公式

设 $G$ 是具有 $n$ 个顶点，$m$ 条边，$f$ 个面，$p$ 个连通分支(composantes connexes) 的平面图，则：

$f = m-n+1+p \quad 即 \quad 面数=边数-顶点数+1+连通部分的数量$

【欧拉示性数 (Euler characteristic)】：具有 $n$ 个顶点 $m$ 条边 $f$ 个面的连通平面图 $G$ 满足：

$n-m+f=2,\quad 即 \quad 顶点数-边数+面数=2$

【推论】具有 $n$ 个顶点，$m$ 条边的简单可平面图，若 $n \ge 3$，则 $m \le 3n -6$

极大可平面图

【定义】设 $G$ 是简单可平面图，如果在 $G$ 中的任意两个不相邻的顶点之间添加一条边所得到的图均为不可平面图，则称该图 $G$ 为极大可平面图。

• （必要条件）$G$ 是极大可平面图，则 $G$ 一定是连通图；如果 $G$ 的阶数大于3，则 $G$ 无割边
• 设 $G$ 是至少有3个顶点的平面图，则 $G$ 是极大平面图的充要条件是 $G$ 中各个面的次数均为3 且 为简单图
• 设 $G$ 是具有 $n$ 个顶点，$m$ 条边，$f$ 个面的极大平面图，则 $m=3n-6$，$f =2n-4$

图的顶点着色

【独立集】（Independent ensemble）是图论中的概念。一个独立集（也称为稳定集stable ensemble）是一个图中一些两两不相邻的顶点所形成的集合。换句话说，独立集 $S$ 由图中若干顶点组成，且 $S$ 中任两个顶点之间没有边。我们用 $\alpha (G)$ 表示稳定即的个数。

【着色】在一个图 $G$ 中，任意相邻的两个顶点不能着相同的颜色（即一条边两端的顶点不能着相同的颜色；也即当一个图的顶点可分为 $n$ 个独立集时，可着 $n$ 个颜色）。我们用 $\gamma (G)$ 表示颜色的个数。

如果一个图所需颜色 $\gamma (G)$ 的最小数量是 $k$，则我们称该图是 $k-点可着色的$

• 常见的图的着色所需颜色的数量：
  • $\gamma (K_p) = p$
  • $\gamma (具有2n个顶点的环) = 2$
  • $\gamma (具有2n+1个顶点的环) = 3$
  • $\gamma (Tree) = 2$

例：

上图 $G$ 所示的独立集为 $\{0\},\quad \{1\}, \quad \{2,3,4\}$

$\alpha (G) = 3$ , $\gamma (G) = 3$

色数的上下界

下界 (1)

$\gamma (G) \ge \frac {nb(V)}{nb(V) - min_{v \in V} \delta(v)}$

其中，

• $min_{v \in V} \delta(v)$ 是图 $G$ 中拥有最小度的顶点 $v$ 的度数，即 在一个图中，拥有最少相邻顶点的顶点 $v$ 的度数；

• $nb(V) - min_{v \in V} \delta(v) - 1$ 是与顶点 $v$ 不邻接的顶点数，而此时就可以知道最多的同色顶点数是 $nb(V) - min_{v \in V} \delta(v)$

• 总共色数是 $\gamma (G)$ ，其与最多的同色顶点数 $nb(V) - min_{v \in V} \delta(v)$ 相乘，应该小于等于顶点数 $nb(V)$ ，即 $\gamma (G) \times nb(V) - min_{v \in V} \delta(v) \le nb(V)$

• 整理可得出上式

下界 (2)

$\gamma (G) \ge \#(最大团_{(clique)}中的顶点数)$

上界 (1)

$\gamma (G) \le max_{v \in V} \delta(v) + 1$

其中，

• $max_{v \in V} \delta(v)$ 是图 $G$ 中拥有最大度的顶点 $v$ 的度数，也可写作 $\Delta (G)$ 。即 在一个图中，拥有最多相邻顶点的顶点 $v$ 的度数；

证明：（数学归纳法）

• 当 $n=1或2$ 时，结论显然成立；

• 假设有 $p$ 个顶点时结论成立，当有 $p+1$ 个顶点时，假设 $v_i$ 是 $G$ 中的任意一个顶点。我们可以将 $v_i$ 顶点从 $G$ 中删去，得到 $G_1$，则 $G_1$ 的阶数为 $p$。$G_1$ 是 $G$ 的子图，所以 $G_1$ 的最大度不可能超过 $G$ 的最大度。由假设我们应该有

  $\gamma (G_1)\quad \le \quad\Delta (G_1) + 1 \quad \le \quad\Delta (G) + 1$

  • 当将 $G_1$ 还原成 $G$ 时，由于 $v$ 至多与 $G_1$ 中 $\Delta (G)$ 个顶点相邻， 而在 $G_1$ 的点着色中，$\Delta (G)$ 个顶点至多用了 $\Delta (G)$ 种颜色，于是在 $\Delta (G) + 1$ 种颜色中至少存在一种颜色给 $v$ 着色，使 $v$ 与相邻的顶点着不同的颜色

Proof:

We use induction on the number of vertices in the graph, which we denote by $n$. Let $P(n)$ be the proposition that an n-vertex graph with maximum degree $\Delta(G)$ at most $k$ is $(k + 1)$-colorable.

Base case (n = 1):

1. A 1-vertex graph has maximum degree $0$ and is 1-colorable, so $P (1)$ is true.

Inductive step:

1. Now assume that $P (n)$ is true, and let $G$ be an (n + 1)-vertex graph with maximum degree $\Delta(G)$ at most $k$.
2. Remove a vertex $v$ (and all edges incident to it), leaving an n-vertex subgraph, $H$. The maximum degree of $H$, $\Delta H$ is at most $k$, and so $H$ is (k + 1)-colorable by our assumption $P (n)$.
3. Now add back vertex $v$. We can assign $v$ a color (from the set of $k + 1$ colors) that is different from all its adjacent vertices, since there are at most $k$ vertices adjacent to $v$ and so at least one of the $k + 1$ colors is still available.
4. Therefore, $G$ is (k + 1)-colorable. This completes the inductive step, and the theorem follows by induction.

上界 (2): 上界 (1) 的收紧

【Brooks定理】

设连通图即不是完全图 $K_n(n \ge 3)$，也不是长度为奇数的环，则

$\gamma (G) \le \Delta (G)$

上界 (3)

$\gamma (G) \le n + 1 - \alpha(G)$

图的边着色

在一个图 $G$ 中，任意相邻的两个边不能着相同的颜色（即与同一个顶点链接的边不能着相同的颜色）。我们用 $\gamma (G)$ 表示颜色的个数。

如果一个图对边着色所需颜色 $\gamma' (G)$ 的最小数量是 $k$，则我们称该图是 $k-边可着色的$

【性质】（维津定理）设G是简单图，则

$\Delta (G) \le \gamma'(G) \le \Delta (G) +1$

图的面着色

连通的无桥平面图的平面嵌入及其所有的面称为平面地图或地图，平面地图的面称为国家。若两个国家的边界至少有一条公共边，则称这两个国家是相邻的。

在一个平面地图 $G$ 中，任意相邻的两个面不能着相同的颜色。我们用 $\gamma^* (G)$ 表示颜色的个数。

如果一个地图所需颜色 $\gamma^* (G)$ 的最小数量是 $k$，则我们称该图是 $k-面可着色的$

【定理】地图 $G$ 是 $k-面可着色的$ 当且仅当 他的对偶图 $G^*$ 是 $k-点可着色的$

【五色定理】任何一个平面图都是 $5-面可着色的$

证明：

第六部分：网络流问题

回顾第二部分的连通部分

网络流

在生活中，经常会遇到一类问题：我们有一个如上图所示的抽象的供水管网，有起点和终点，我们需要求解关于这个供水管网的一系列性能问题。那么我们可以将其网络模型视为一种有向图 $D$，而网络上的流可视为边上的权，所以我们可以将该问题建模为

$D=(V,E,\omega)$

其中：

• $s,t \in V$，$s$ 为原点 (source)，$t$ 为目的点 (target)
• $\omega$ 为 $A \to R$ 的映射。任何一条边 $x \in A$，$\omega (x)$ 为边 $x$ 的容量 (Capacity)

【名词解释】

• 流量 (Flow)：实际在模型中管线里的流量，流量不能超过容量

• 容量 (Capacity)：模型中边的权重，为该条边所能够承受的最大流量

• 残差 (Residual)：又称空闲量，指“该条边在当前流量下还可以继续承受的流量”，即 $R_{esidual} = C_{apacity} - F_{low}$

• 最大流 (Maximum Flow)：在当前模型中能流过的最大总流量

• 最小割

最大流问题

简单算法

我们根据原图 (左) 创建一个残差图 (右)，其中空闲量 $R_{esidual} = C_{apacity} - F_{low}$，初始时 $F_{low}$ 均为 $0$；

【第一轮循环】

节点	$v_1$	$v_2$	$v_4$	t
[前序,方向,权重]	[s,+,4]	[S,+,2]	[$v_2$,+,2]	[$v_4$,+,3]

我们在残差图中找出一条从起点 $s$ 到终点 $t$ 的简单路径，其中不能有回路。例如，我们已经找到了一条最右边的路径 $s \stackrel{2}\longrightarrow v_2 \stackrel{2}\longrightarrow v_4 \stackrel{3}\longrightarrow t $ 。由于短板效应，该条路径最多只能输送 $2$ ，所以三条边的路径的残差量都会 $-2$，即 $s \stackrel{0}\longrightarrow v_2 \stackrel{0}\longrightarrow v_4 \stackrel{1}\longrightarrow t $。

当某一条边的饱和 (Staturated) 即残差量为 $0$ 时，就将其从残差图中移除。第一轮循环结束。

【第二轮循环】

节点	$v_1$	$v_4$	$v_3$	t
[前序,方向,权重]	[s,+,4]	[$v_1$,+,4]	[$v_1$,+,2]	[$v_3$,+,3]

如下图所示，我们找到了一条从起点 $s$ 到终点 $t$ 的简单路径：$s \stackrel{4}\longrightarrow v_1 \stackrel{2}\longrightarrow v_3 \stackrel{3}\longrightarrow t $ ，

由于短板效应，该条路径最多只能输送 $2$ ，所以三条边的路径的残差量都会 $-2$，即 $s \stackrel{2}\longrightarrow v_1 \stackrel{0}\longrightarrow v_3 \stackrel{1}\longrightarrow t $。更新残差图。第二轮循环结束。

【第三次循环】

节点	$v_1$	$v_4$	t
[前序,方向,权重]	[s,+,2]	[$v_1$,+,4]	[$v_4$,+,1]

如下图所示，我们找到了一条从起点 $s$ 到终点 $t$ 的简单路径：$s \stackrel{2}\longrightarrow v_1 \stackrel{4}\longrightarrow v_4 \stackrel{1}\longrightarrow t $ ，

由于短板效应，该条路径最多只能输送 $1$ ，所以三条边的路径的残差量都会 $-1$，即 $s \stackrel{1}\longrightarrow v_1 \stackrel{3}\longrightarrow v_4 \stackrel{0}\longrightarrow t $。更新残差图。第三轮循环结束。

【第四次循环】

节点	$v_1$	$v_2$	$v_4$	t
[前序,方向,权重]	[s,+,1]	[$v_1$,+,1]	[$v_1$,+,3]	[$v_3$,+,1]

如下图所示，我们无法找到一条从起点 $s$ 到终点 $t$ 的简单路径，终止程序。

用最后一次循环结果更新的残差 (Residual) 图与原图 (Capacity) 比较，得出流量 (Flow) 图，即 $F_{low} = C_{apacity} - R_{esidual}$，如下图所示。

其中，边上的权重为 $[F_{low}/C_{apacity}]$ ，我们也可以从图中看出，网络中的总流量 (Amount of Flow) $= 2+3 = 5$

• 注意⚠️：这种简单的算法不能保证结果的最优性，即总流量不一定是最大流。如下图所示的图的总流量就不是最大流，

  

  而图中红色的路径是阻塞流 (Blocking Flow)，即在当前流量下无法增加其他从源点到终点流，最大流也是一种阻塞流。

Ford-Fulkerson 算法

Ford-Fulkerson 算法一定能找到最大流，其与之前的简单算法的区别是：添加了一个回溯路径，一旦选择了“不好的”路径，就会撤销这个路径，沿着回溯路径回到源点。

【算法描述】

我们根据原图 (左) 创建一个残差图 (右)，其中空闲量 $R_{esidual} = C_{apacity} - F_{low}$，初始时 $F_{low}$ 均为 $0$；

【第一轮循环】

节点	$v_1$	$v_2$	$v_4$	t
[前序,方向,权重]	[s,+,4]	[S,+,2]	[$v_1$,+,4]	[$v_4$,+,3]
backtracking path (next)	[S,-,0]	[S,-,0]	[$v_1$,-,0]	[$v_4$,-,0]

我们在残差图中找出一条从起点 $s$ 到终点 $t$ 的简单路径，其中不能有回路。例如，我们已经找到了一条路径 $s \stackrel{4}\longrightarrow v_1 \stackrel{4}\longrightarrow v_4 \stackrel{3}\longrightarrow t $ 。由于短板效应，该条路径最多只能输送 $3$ ，所以三条边的路径的残差量都会 $-3$，即 $s \stackrel{1}\longrightarrow v_1 \stackrel{1}\longrightarrow v_4 \stackrel{0}\longrightarrow t $。更新残差图。

如上图所示，添加一条绿色的回溯路径，每个边的权都为 $3$： $t \stackrel{3}\longrightarrow v_4\stackrel{3}\longrightarrow v_1 \stackrel{3}\longrightarrow s$ 。第一轮循环结束。

【第二轮循环】

节点	$v_1$	$v_2$	$v_3$	t
[前序,方向,权重]	[S,+,1]	[S,+,2]	[$v_1$,+,2]	[$v_3$,+,3]
backtracking path	[S,-,3]	[S,-,0]	[$v_1$,-,0]	[$v_3$,-,0]

如下图所示，我们找到了一条从起点 $s$ 到终点 $t$ 的简单路径：$s \stackrel{1}\longrightarrow v_1 \stackrel{2}\longrightarrow v_3 \stackrel{3}\longrightarrow t $ ，

由于短板效应，该条路径最多只能输送 $1$ ，所以三条边的路径的残差量都会 $-1$，即 $s \stackrel{0}\longrightarrow v_1 \stackrel{1}\longrightarrow v_3 \stackrel{2}\longrightarrow t $。更新残差图。

如上图所示，添加一条绿色的回溯路径，每个边的权都为 $1$： $t \stackrel{1}\longrightarrow v_3\stackrel{1}\longrightarrow v_1 \stackrel{1}\longrightarrow s$，并于之前的回溯路径合并。第二轮循环结束。

【第三轮循环】

节点	$v_1$	$v_2$	$v_4$	$v_3$	t
[前序,方向,权重]	[S,+,0]	[S,+,2]	[$v_2$,+,2] / [$v_1$,+,1]	[$v_1$,+,1]	[$v_3$,+,2]
backtracking path	[S,-,4]	[S,-,0]	[$v_2$,-,0] / [$v_1$,-,1]	[$v_1$,-,1]	[$v_3$,-,1]

如果此时我们将绿色的回溯路径去掉，我们就不能在起点和终点之间找到一条路径。Ford-Fulkerson 算法的关键就在于这些回溯路径。如下图所示，我们考虑回溯路径，我们找到了一条从起点 $s$ 到终点 $t$ 的简单路径：$s \stackrel{2}\longrightarrow v_2 \stackrel{2}\longrightarrow v_4 \stackrel{3^*}\longrightarrow v_1 \stackrel{1}\longrightarrow v_3 \stackrel{2}\longrightarrow t$ ，

由于短板效应，该条路径最多只能输送 $1$ ，所以三条边的路径的残差量都会 $-1$，即 $s \stackrel{1}\longrightarrow v_2 \stackrel{1}\longrightarrow v_4 \stackrel{2^*}\longrightarrow v_1 \stackrel{0}\longrightarrow v_3 \stackrel{1}\longrightarrow t$。更新残差图。

如上图所示，添加一条绿色的回溯路径，每个边的权都为 $1$： $t \stackrel{1}\longrightarrow v_3 \stackrel{1}\longrightarrow v_1 \stackrel{1^*}\longrightarrow v_4 \stackrel{1}\longrightarrow v_2 \stackrel{1}\longrightarrow s$，并于之前的回溯路径合并。第三轮循环结束。

【第四轮循环】

如第三轮循环末的图所示，没有任何路径通往红色区域 $v_3 \stackrel{1}\longrightarrow t$，说明现在不存在其他路径从起点流向终点，所以终止程序。

用最后一次循环结果更新的残差 (Residual) 图去除所有回溯路径与原图 (Capacity) 比较，得出流量 (Flow) 图，即 $F_{low} = C_{apacity} - R_{esidual}$，如下图所示。

其中，边上的权重为 $[F_{low}/C_{apacity}]$ ，我们也可以从图中看出，网络中的总流量 (Amount of Flow) $= 2+3 = 5$，最大流的大小也等于 $5$。

• 注意⚠️：Ford-Fulkerson 算法的时间复杂度较高。仍然有其他算法可以更快速的求解该问题，如 Edmonds-Karp 算法 和 Dinic’s 算法（详见B站视频讲解），在此不再赘述。

最小割问题

我们先回顾一下之前之前学习的割，可类比与今天的网络流中最小割问题。

在如上图所示的网络流中，有向图 $D=(V,E,\omega)$

其中：

• $s,t \in V$，$s$ 为原点 (source)，$t$ 为目的点 (target)
• $\omega$ 为 $A \to R$ 的映射。任何一条边 $x \in A$，$\omega (x)$ 为边 $x$ 的容量 (Capacity)

【定义】S-T Cut：将所有的顶点分为两个集合 $S$ 和 $T$

• $S \cup P = V$ 并且 $S \cap P = \emptyset$
• $s \in S$ 并且 $t \in T$
• 二元组集合 $(S,T)$ 被称作 “S-T Cut”

如上图所示，我们去除图中红色的边，使得不存在任意一套路径可以从起点 $s$ 到终点 $t$ 。去除这些边后，定点集 $V$ 就会分裂成两部分 $_{Subset}S$ 和 $_{Subset}T$。然而这样的集合划分并不唯一。

【注意⚠️】图中有一条边 $v_4 \stackrel{4}\longrightarrow s$ 连通 $_{Subset}S$ 和 $_{Subset}T$，但是即使有这条边的存在，依然不存在任意一套路径可以从起点 $s$ 到终点 $t$ 。所以我们不用去管他。

• 容量 $Capacity(S,T)$ 是所有从集合 $_{Subset}S$ 通向集合 $_{Subset}T$ 的边的权重之和，
  • 上图中左边的容量 $Capacity_左(S,T) = 2+1 =3$，
  • 右边的“S-T Cut”容量 $Capacity_右(S,T) = 2+2+2 = 6$

【最小割】：Minimum S-T Cut (Min-Cut)，是在所有“S-T Cut” 中容量最小的那个。目标是用最小的“力气”（权）就可以截断水流（起点 $s$ 不到终点 $t$）。

最大流 - 最小割问题

对于一个网络流问题，最大流的流量 就等于 最小割的容量，即

$Max \;flow = Min\;cut$

我们可以将 寻找最小割的问题 等价转化为 寻找最大流问题：

在 寻找最大流问题 中，在最后一次迭代中去除回溯路径的残差图 (Residual Graph) 中，从起点 $s$ 出发，找到所有能达到的节点，将它们放入集合 $_{Subset}S$，将剩下的所有节点放入集合 $_{Subset}T$。这样就得到了最小割的二元组 $(S,T)$。