图论与网络优化2

CSDN 有字数限制，因此笔记分别发布，目前：

1. 【笔记1】概念与计算、树及其算法
2. 【笔记2】容量网络模型

---

4 最大流及其算法

4.1 容量网络模型

4.1.1 容量网络

容量网络：如果一个加权有向网络 $D$ 满足如下三个条件：①存在唯一一个入度为 $0$ 的顶点，称为源；②存在唯一一个出度为 $0$ 的顶点，称为汇；③每条弧 $(v_i,v_j)$ 赋权 $c_{ij}$ 是一个非负数，称为弧 $(v_i,v_j)$ 的容量，则把这个加权有向网络 $D$ 称为容量网络。

---

4.1.2 流

流：设 $D$ 是一个容量网络，令 $c_{ij}$ 表示弧 $(v_i,v_j)$ 的容量。设 $f$ 是定义在 $D$ 的弧集上的一个函数，它赋予每条弧 $(v_i,v_j)$ 一个非负实数 $f_{ij}$，若 $f$ 满足：① $f_{ij}\le c_{ij}$；② $\forall v_j\in V(D)$ \ { v s , v t } \{v_s,v_t\} {vs​,vt​} 有 ${\sum }_{(v_i,v_j)\in E(D)}{f}_{ij}={\sum }_{(v_j,v_i)\in E(D)}{f}_{ji}$，则称 $f$ 为容量网络 $D$ 的一个流，称 $f_{ij}$ 为弧 $(v_i,v_j)$ 上的流量。
(非)饱和弧：弧上的流量(未)达到弧的容量。

---

4.1.3 流值

定理：设 $f$ 是容量网络 $D$ 的一个流，其中源为 $v_s$，汇为 $v_t$，由源的流出量等于汇的流入量，即 ${\sum }_{(v_s,v_j)\in E(D)}{f}_{si}={\sum }_{(v_i,v_t)\in E(D)}{f}_{it}$
证明：注意到每条弧上的流量，既是其头顶点的流入量，也是其尾顶点的流出量，因此所有弧上的流量之和、所有顶顶啊的流入量之和、所有顶点的流出量之和，这三者相等。
流值：设 $f$ 是容量网络 $D$ 的一个流，其源为 $v_s$，汇为 $v_t$，称源的流出量为流 $f$ 的流值，记作 $val(f)$。

---

4.1.4 最大流

最大流：设 $D$ 是一个容量网络，若 $f$ 是 $D$ 上流值最大的流，则把 $f$ 称为 $D$ 的最大流。
截：设 $D$ 是一个容量网络，源为 $v_s$，汇为 $v_t$。设顶点子集 $S\subset V(D),\overline{S}=V(D)$ \ $S$，且 $v_s\in S,v_t\in \overline{S}$，则称弧集 $\{(v_i,v_j)\in E(D)|v_i\in S,v_j\in \overline{S}\}$ 为容量网络 $D$ 的截，记作 $(S,\overline{S})$。
截的容量：${\sum }_{(v_i,v_j)\in (S,\overline{S})}{c}_{ij}$，记作 $c_{(}S,\overline{S})$。
最小截：容量达最小的截为最小截。
定理：设 $D$ 是一个容量网络，源为 $v_s$，汇为 $v_t$。设 $f$ 是容量网络 $D$ 的一个流，$(S,\overline{S})$ 是 $D$ 的一个截，则有 $val(f)\le c(S,\overline{S})$。
证明：…
流值与截容量相等当且仅当每条弧都是饱和弧且无逆流的时候。
若容量网络的一个流 $f$ 的流值等于某个截 $(S,\overline{S})$的容量，即 $c(S,\overline{S})=val(f)$，则 $f$ 为最大流，$(S,\overline{S})$ 为最小截。

---

4.2 最大流算法

4.2.1 可增路

可增路：设 $P$ 是一条 $(v_s,v_j)$ 路，如果①对 $P$ 中每条正向弧 $(v_i,v_j),f_{ij}<c_{ij}$；②对 $P$ 中每条反向弧 $(v_i,v_j),f_{ij}>0$，则称 $(v_s,v_j)$ 为 $f$ 非饱和路；否则为饱和路。从源到汇的 $f$ 非饱和路，称为 $f$ 可增路。

---

4.2.2 最大流算法

定理：设容量网络 $D$ 的源为 $v_s$，汇为 $v_t$，$f$ 为 $D$ 的一个流，则 $f$ 为最大流当且仅当 $D$ 中不存在 $f$ 可增路。
证明：只需证明充分性。只需证明存在截 $(S,\overline{S})$ 满足：$(S,\overline{S})$ 中的每条弧都是饱和弧，$(\overline{S},S)$ 中的每条弧都是零弧。
将顶点分类，令 S = { v s } ∪ { v j ∣ 存在一条 f 非饱和路 ( v s , v j ) } S=\{v_s\} \cup \{v_j|存在一条 f 非饱和路 (v_s,v_j)\} S={vs​}∪{vj​∣存在一条f非饱和路(vs​,vj​)}，故有 $v_t\in \overline{S}$ 。
则 $S$ 与 $\overline{S}$ 之间假设 $f_{ij}<c_{ij}$，易见 $P+(v_i,v_j)$ 亦为 $f$ 非饱和路，与 $v_j\in \overline{S}$ 矛盾。同理可以证明 $f_{ij}=0$。
标号法能求解可增路

---

4.2.3 最大流最小截定理

最大流算法结束时，最大流流值等于最小截容量。
定理：在任何容量网络 $D$ 中，最大流的流值等于最小截的容量。
证明：(大致思路)设 $S$ 为能用标号法能够获得标号的顶点集合，则 $(S,\overline{S})$ 之间的弧的值必定为 $0$。

---

4.3 最小费用最大流

4.3.1 问题描述

流 $f$ 的费用：设容量网络 $D$ 的源为 $v_s$，汇为 $v_t$，$c_{ij}$ 和 $b_{ij}$ 分别表示弧 $(v_i,v_j)$ 上的容量和单位流量费用，设 $f$ 是 $G$ 的流，则称 $b(f)={\sum }_{(v_i,v_j)\in E(D)}{f}_{ij}{b}_{ij}$ 为流 $f$ 的费用。在容量网络 $D$ 的所有最大流中寻找费用最小的流，这样的流称为最小费用最大流。

---

4.3.2 F增广圈

增广圈：设 $Q$ 是一个具有指定正向的圈，$Q^{+}$ 为圈 $Q$ 上正向弧的集合，$Q^{-}$ 为圈 $Q$ 上反向弧的集合。

1. ${\delta }_{ij}=c_{ij}-f_{ij}，(v_i,v_j)\in Q^{+}$
2. ${\delta }_{ij}=f_{ij}，(v_i,v_j)\in Q^{-}$。

δ ( Q ) = m i n { δ i j ∣ ( v i , v j ) ∈ E ( Q ) } \delta(Q)=min\{\delta_{ij}|(v_i,v_j) \in E(Q)\} δ(Q)=min{δij​∣(vi​,vj​)∈E(Q)}。
若 $\delta (Q)>0$，则称 $\delta (Q)$ 为允许修改流量，称圈 $Q$ 为容量网络 $D$ 上关于流 $f$ 的增广圈。
对于 $f$ 增广圈 $Q$，我们可以定义 $f^{\prime }$：

1. $f_{ij}^{{}^{\prime }}=f_{ij}+\delta (Q)，(v_i,v_j)\in Q^{+}$
2. $f_{ij}^{{}^{\prime }}=f_{ij}-\delta (Q)，(v_i,v_j)\in Q^{-}$
3. $f_{ij}，(v_i,v_j)\notin E(Q)$

这样 $f^{\prime }$ 仍是 $D$ 的流并且 $val(f^{\prime })=val(f)$，称 $f^{\prime }$ 为基于 $f$ 增广圈 $Q$ 的修正流。

负圈：设有容量网络 $D$，$f$ 是一个流，$f_{ij},c_{ij},b_{ij}$ 分别为弧 $(v_i,v_j)$ 上的流量、容量和单位费用，设 $Q$ 是关于流 $f$ 的增广圈。称 $b(Q,f)={\sum }_{(v_i,v_j)\in Q^{+}}{b}_{ij}-{\sum }_{(v_i,v_j)\in Q^{-}}{b}_{ij}$ 为增广圈的费用，若小于 $0$，则称 $Q$ 为负圈。负圈与流量、容量、费用、圈的指定方向有关。

---

4.3.3 Klein 算法

算法：

1. 求容量网络 $D$ 的一个最大流。
2. 寻找网络中的负圈。若没有负圈，算法结束；若找到一个负圈，转step 3
3. 修改负圈 $Q$ 上各弧的流量，得到修正流。在新修正流的基础上，转step 2，继续寻找负圈。

定理：设有容量网络 $D$，$f$ 是一个流，$f_{ij},c_{ij},b_{ij}$ 分别为弧 $(v_i,v_j)$ 上的流量、容量和单位费用，则 $f$ 是最小费用最大流当且仅当任何 $f$ 增广圈 $Q$ 的费用 $b(Q,f)\ge 0$，即无负圈。

---

5 遍历性及其算法

5.1 Euler图和有向Euler图

5.1.1 定义

Euler图：如果图 $G$ 中存在包含所有边的闭迹 $W$，则称 $G$ 为 $Euler$ 图，$W$ 称为 $G$ 的 $Euler$ 闭迹。
半Euler图：如果图 $G$ 中存在包含所有边的迹 $P$，则称 $G$ 为 $半Euler$ 图，$P$ 称为 $G$ 的 $Euler$ 迹。
定理：设 $G$ 为非空连通图，则下面三个命题等价：

1. $G$ 是 $Euler$ 图；
2. $G$ 中不含奇点；
3. $G$ 可以表示为若干个没有公共边的圈的并。

证明：

1. 1->2:设 $G$ 是连通的 $Euler$ 图，$W$ 是 $G$ 的 $Euler$ 闭迹，则 $\forall v\in V(G)，v$ 必定在 $W$ 中出现，当 $v$ 作为内部点，每出现一次，必定与 $G$ 中两条边关联；当 $v$ 作为 $W$ 的起点，则 $v$ 也是重点，从而它必与两条边关联，因此 $G$ 的每个顶点都是偶点。
2. 2->3:设 $G$ 是非空连通图且不含奇点，则 $G$ 不是树，从而 $G$ 中含有圈，不断取出圈来得到新图再取圈，因此可以从第二个命题演变成第三个命题。
3. 3->1:由 $Euler$ 图的定义，结论显然。

有向Euler图：若有向图 $D$ 中存在包含所有弧的有向闭迹，则称 $D$ 为有向 $Euler$ 图，这样的有向闭迹，称为 $D$ 的有向 $Euler$ 闭迹。
有向半Euler图：若有向图 $D$ 中存在包含所有弧的有向迹，则称 $D$ 为有向 $Euler$ 图，这样的有向迹，称为 $D$ 的有向 $Euler$ 迹。
定理：设 $G$ 为非空连通有向图，则下面三个命题等价：

1. $D$ 是有向 $Euler$ 图；
2. $\forall v\in V(D)$，有 $d^{+}(v)=d^{-}(v)$
3. $G$ 可以表示为弧不交的回路的并。

---

5.1.2 Fleury 算法

算法思想：从任意顶点出发，除非别无选择，否则总是选择一条不是割边的且没走过的边，直到获得 $Euler$ 闭迹为止。
定理：设 $G$ 是 $Euler$ 图，$W=v_0{e}_1{v}_1...e_n{v}_n$ 是 $Fleury$ 算法结束时得到的迹，则 $W$ 一定是图 $G$ 的 $Euler$ 闭迹。
证明：…

---

5.1.3 编码盘设计

例题：16个二进制数应该如何排列，使得圆盘沿顺时针旋转一部分，恰好组成 $0000$ 到 $1111$ 的 $16$ 组四位二进制输出，同时旋转一周又返回到 $0000$ 状态？
答案：定义一个有 $8$ 个顶点的有向图 $D$，其中顶点用 $3$ 维 $0-1$ 序列 $x_1{x}_2{x}_3$ 标记，且顶点 $x_1{x}_2{x}_3$ 与顶点 $x_2{x}_{3}0,x_2{x}_{3}1$ 以出弧的形式相连，这样得到的有向图 $D$ 中，每个顶点的入度和出度相等，都等于 $2$。然后从 $000$ 出发，可以得到一个有向 $Euler$ 闭迹为 …。注意起终点重复，所以序列取末尾数字，得…
该问题可以扩展，得到的有向图为德布鲁英图 $B(2,n)$。每个顶点最后一位数字构成序列为 德布鲁英序列。

---

5.2 中国邮递员问题

5.2.1 问题描述

管梅谷教授提出并研究了中国邮递员问题。
问题内容：在加权连通图 $G$ 中，寻找一条经过每条边至少一次且权和最小的闭迹，即 $G$ 的最优环游。
思考角度：对于重复走的边，可以看作为两点之间的重边(即重复走的边视为 $k$ 重边)。

---

5.2.2 奇偶点图上作业法

最优环游的奇偶点图上作业法：

1. 把图 $G$ 所有奇点配成对，将每对奇点之间的一条链的每条边改为二重边，得到一个新图 $G_1$，图中没有奇点
2. 在图 $G_1$ 中，若顶点之间有 $k(k\ge 3)$ 重边，则去掉其中偶数条，只保留 $1/2$ 条边，得到图 $G_2$。
3. 检查 $G_2$ 中的每一个圈 $C$，若重复边的权和超过此圈权和的一半，则重边变为单边，单边变为二重边，重复这一过程，直到所有圈上重边的权和都不超过圈权和一半，得到 $G_3$。
4. 用 $Fleury$ 算法求 $G_3$ 的 $Euler$ 闭迹，得到图 $G$ 的最优环游

定理：设 $G$ 是加权连通图，则奇偶点图上作业法得到的闭途径是最优环游。
证明：…
例题：

答案：图 $G$ 中有 $6$ 个奇点 $v_2,v_3,v_5,v_8,v_{10},v_{11}$，将它们搭配成三对，因此添加 $v_2{v}_3{v}_4{v}_5，v_3{v}_2{v}_1{v}_8，v_{10}{v}_{11}$。注意 $v_2{v}_3$ 间有两条新添加的边，删去得到新图。

$v_1{v}_2{v}_7{v}_8{v}_1，v_3{v}_4{v}_5{v}_6{v}_3$ 中非最优添边，因此重边变单边，单边变重边，再次得到新图：

再检查圈 $v_2{v}_3{v}_6{v}_{11}{v}_{10}{v}_7{v}_2$，也非最优，执行单重边置反，得到新图。

检查通过，执行 $Fleury$ 算法，得到最优环游为：
$v_1{v}_2{v}_3{v}_2{v}_7{v}_8{v}_7{v}_6{v}_5{v}_6{v}_{11}{v}_{12}{v}_5{v}_4{v}_3{v}_6{v}_{11}{v}_{10}{v}_7{v}_{10}{v}_9{v}_8{v}_1$，环游总长度 $109$。