一罐可乐

1. 无向图与有向图#

• 无向图：记为 $G=(V, E)$，其中 $V$ 是顶点（点）集合，$E$ 是边集合。连接点 $u$ 和 $v$ 的无向边记作 $[u, v]$。
• 有向图：记为 $D=(V, A)$，其中 $A$ 是弧（有向边）集合。从始点 $u$ 指向终点 $v$ 的弧记作 $(u, v)$。
• 基础图：去掉有向图 $D$ 中所有弧的箭头所得到的无向图，记为 $G(D)$。

2. 基本术语与概念#

• 相邻与关联：若 $e=[u, v] \in E$，则称 $u, v$ 相邻，且称 $e$ 与 $u, v$ 关联。
• 环：一条边的两个端点相同，如 $e=[u, u]$。
• 多重边：两个顶点之间有多于一条的边。
• 简单图：不含环且无多重边的图。
• 次（度, Degree）：以顶点 $v$ 为端点的边的个数，记为 $d(v)$。环在计算度数时算作两次。
  • 悬挂点：度数为 1 的点。其关联的边称为悬挂边。
  • 孤立点：度数为 0 的点。
• 链与初等链：点边交错序列。若链中所有顶点各不相同，则为初等链。若首尾顶点相同，其余顶点互不相同，则为初等圈（圈）。
• 路与回路（有向图）：方向一致的弧链。首尾相连的有向路称为回路。
• 连通图：无向图中任意两点之间都至少存在一条链。否则为不连通图。
• 支撑子图：包含原图所有顶点（但边集是原图边集子集）的子图。

1. 树（Tree）的定义与性质#

树是不含圈的连通无向图，记为 $T$。

• 性质 1：若图 $G$ 的顶点数 $p(G) \ge 2$，则 $G$ 中至少有 2 个悬挂点（度数为 1）。
• 性质 2：图 $G$ 是树的充分必要条件是 $G$ 连通且恰有 $p - 1$ 条边。
• 性质 3：树中任意两点之间有且仅有一条初等链。从树中去掉任意一条边，图将不再连通（即树的边都是割边）。

2. 支撑树（Spanning Tree）#

图 $G$ 的支撑树是 $G$ 的一个包含所有顶点的支撑子图，且该子图本身是一棵树。

• 定理：图 $G$ 存在支撑树的充要条件是 $G$ 为连通图。

3. 最小支撑树算法（Minimum Spanning Tree, MST）#

对于连通赋权无向图，各边有非负权值 $w(e)$，要求一棵支撑树使得所有边的权值之和最小。

1. 问题描述#

在一个赋权图（有向或无向）中，寻找从起点 $v_s$ 到终点 $v_t$ 的一条路径，使得该路径上的边（弧）权值之和最小。

2. Dijkstra 双标号算法（限边权非负）#

• 标号思想：为每个点记录双标号 $(v_i, d_j)$。其中 $v_i$ 代表该点前驱节点（路标），$d_j$ 代表从起点 $v_s$ 到该节点的最短路权值（路权）。
  • P 标号：永久标号，代表已求得的最短路权值。
  • T 标号：临时标号，代表当前求得的最短路权值上界。
• 算法步骤：
  1. 给起点 $v_s$ 赋永久标号 $P(v_s) = (v_s, 0)$。其余点均设为临时标号 $T(v_j) = (-, \infty)$。
  2. 若刚获得永久标号的节点为 $v_i$，考察所有从 $v_i$ 出发且目前为临时标号的邻接点 $v_j$。更新其临时标号值： $d_j = \min \{ d_j^{\text{old}}, d_i + w_{ij} \}$ 若发生更新，则将前驱节点记录为 $v_i$。
  3. 在所有当前具有临时标号（T 标号）的节点中，选择路权值 $d$ 最小的一个 $v_k$，将其转化为永久标号 $P(v_k)$（画横线锁定）。
  4. 重复步骤 2-3，直到终点 $v_t$ 获得永久标号，或所有可达节点都已变为永久标号。
  5. 反向追踪：从终点 $v_t$ 开始，根据前驱节点标号反向追踪，即可还原整条最短路径。

3. 应用案例：设备更新问题#

• 建模方法：用顶点 $v_i$ 代表“第 $i$ 年年初购进一台新设备”这种状态。从 $v_i$ 到 $v_j$（$j > i$）画一条弧，代表这台在第 $i$ 年年初购入的设备一直连续使用到第 $j$ 年年初。弧权 $w_{ij}$ 设为： $w_{ij} = \text{第 } i \text{ 年设备购置费} + \sum_{k=i}^{j-1} (\text{该设备使用第 } k-i+1 \text{ 年的维修费}) - \text{第 } j \text{ 年年初设备残值}$ 求解从起点到终点的最短路径，其对应路径即为总更新费用最低的设备更新计划。

1. 数学模型#

设网络为有向图 $D=(V, A, C)$，指定发点 $v_s$、收点 $v_t$，每条弧 $(v_i, v_j)$ 的容量限制为 $c_{ij} \ge 0$。求一个可行流 $f = \{f_{ij}\}$ 使流值 $v(f)$ 最大： $\max v(f)$ $\text{s.t. } \begin{cases} 0 \le f_{ij} \le c_{ij}, & \forall (v_i, v_j) \in A \quad \text{（容量限制）} \\ \sum_j f_{ij} - \sum_j f_{ji} = \begin{cases} v(f), & i = v_s \\ 0, & i \neq v_s, v_t \quad \text{（流量平衡）} \\ -v(f), & i = v_t \end{cases} \end{cases}$

2. 增广链（Augmenting Chain）#

设 $f$ 是当前可行流，$\mu$ 是从 $v_s$ 到 $v_t$ 的一条无向链：

• 前向弧 $\mu^+$：方向与链一致。要求非饱和，即 $f_{ij} < c_{ij}$。
• 后向弧 $\mu^-$：方向与链相反。要求非零流，即 $f_{ij} > 0$。 若链上所有弧都满足上述要求，则称 $\mu$ 为关于可行流 $f$ 的增广链。沿增广链可将流值调大。

3. 截集与截量（Cut Set and Capacity）#

将点集 $V$ 分为两个互斥子集 $S$ 和 $T$（其中 $v_s \in S, v_t \in T$）。

• 截集：始点在 $S$、终点在 $T$ 的有向弧集合，记为 $(S, T)$。
• 截量（容量）：截集中所有弧容量的和，记为 $c(S, T) = \sum_{v_i \in S, v_j \in T} c_{ij}$。
• 最大流最小截定理：网络中最大流的流值等于分离发点与收点的最小截集的截量。

4. Ford-Fulkerson 标号算法#

• 第一阶段：标号过程（寻找增广链）：
  1. 发点 $v_s$ 标上永久标记 $(\infty)$，并放入已标号未检查集合。
  2. 选取一个已标号但未检查的节点 $v_i$。对于所有与 $v_i$ 邻接的未标号节点 $v_j$：
     • 前向弧 $(v_i, v_j) \in A$：若 $f_{ij} < c_{ij}$，则给 $v_j$ 标号 $(v_i, \theta_j)$，其中 $\theta_j = \min \{ \theta_i, c_{ij} - f_{ij} \}$。
     • 后向弧 $(v_j, v_i) \in A$：若 $f_{ji} > 0$，则给 $v_j$ 标号 $(-v_i, \theta_j)$，其中 $\theta_j = \min \{ \theta_i, f_{ji} \}$。
  3. 若收点 $v_t$ 成功获得标号，说明找到了增广链，转入第二阶段（调整过程）；若全部标号节点检查完毕，收点仍无法获得标号，则当前可行流即为最大流。
• 第二阶段：调整过程： 从收点 $v_t$ 开始反向追踪到发点 $v_s$，确定增广链 $\mu$。令调整量 $\theta = \theta_t$：
  • 对于前向弧：新流量 $f'_{ij} = f_{ij} + \theta$。
  • 对于后向弧：新流量 $f'_{ji} = f_{ji} - \theta$。 擦除所有临时标号，返回第一阶段重新开始。

1. 数学描述#

每条弧 $(v_i, v_j)$ 除了有容量 $c_{ij}$ 限制外，还对应单位运费（费用系数） $b_{ij} \ge 0$。在保证网络流量达到最大流的前提下，求使得总输送费用最小的流分布： $\min \sum_{(v_i,v_j) \in A} b_{ij} f_{ij}$

2. 算法 1：负回路调整法（Cycle-Canceling）#

• 原理：一个流是最小费用流，当且仅当它的残余网络中不存在负费用回路。
• 步骤：
  1. 忽略费用，用 Ford-Fulkerson 标号法求出当前网络的一个最大流 $f$。
  2. 构造对应的赋权残余网络 $W(f)$：
     • 若 $f_{ij} < c_{ij}$，存在前向弧 $(v_i, v_j)$，容量为 $c_{ij} - f_{ij}$，权（费用）为 $b_{ij}$。
     • 若 $f_{ij} > 0$，存在后向弧 $(v_j, v_i)$，容量为 $f_{ij}$，权（费用）为 $-b_{ij}$（负费用）。
  3. 在 $W(f)$ 中寻找总权数为负的有向回路（负回路）。若不存在，则当前最大流已是最小费用最大流，计算结束。
  4. 若存在负回路，沿该负回路调整流量，调整量为回路中各弧容量的最小值。调整后返回步骤 2。

3. 算法 2：最小费用增广路算法（Successive Shortest Path）#

• 原理：从零流开始，每次沿着残余网络 $W(f)$ 中从发点 $v_s$ 到收点 $v_t$ 的最短路（以单位费用为路权）进行流的增广，得到的流一定是该流量下的最小费用流。
• 步骤：
  1. 初设可行流 $f = 0$（费用为 0）。
  2. 构造残余网络 $W(f)$，以各弧的费用作为权值（注意后向弧的权为 $-b_{ij}$）。
  3. 在 $W(f)$ 中寻找从 $v_s$ 到 $v_t$ 的最短路（由于残余网络中含有负权弧，不能直接用 Dijkstra，需使用能处理负权的算法，如 SPFA、Bellman-Ford 或直接枚举）。
  4. 若不存在从 $v_s$ 到 $v_t$ 的路，则当前的流 $f$ 即为最小费用最大流。
  5. 若存在最短路，将其作为增广链 $\mu$，调整量为该路径上各弧剩余容量的最小值 $\theta$。进行流量增广后，返回步骤 2。
• 易错警示：在第 3 步构建残余网络 $W(f)$ 时，必须正确为反向弧赋予负权值 $-b_{ij}$。如果不画反向弧或忽略负权，计算就会退化为不具回溯修正能力的“贪心法”，求得的往往是错误解。

1. 问题提出#

管梅谷于 1962 年提出：邮递员投递信件要走遍他负责的全部街道至少一次，然后回到邮局。如何选择路线，使所走的总路程最短？

• 图论抽象：在一个连通赋权图中，求一个包含所有边的闭途径（圈），使该圈的总权值最小。

2. 欧拉图与一笔画问题#

• 欧拉圈：穿过图中每条边一次且仅一次的回路。含有欧拉圈的图称为欧拉图。
• 定理：连通多重图 $G$ 有欧拉圈（是欧拉图），当且仅当 $G$ 中没有奇点（所有顶点的度数均为偶数）。
• 欧拉链：穿过图中每条边一次且仅一次的路径。
• 推论：连通多重图 $G$ 有欧拉链，当且仅当 $G$ 中恰有两个奇点（此时一笔画必须以一个奇点为起点，另一个奇点为终点）。

3. 奇偶点图上作业法#

若图中存在奇点（其个数必为偶数），则邮递员无法不重复地走完所有街道，必须在某些边上重复走。

• 算法思想：在奇点之间添加重复边（相当于重复走这些路），使所有奇点变为偶点，且添加的重复边总权值最小。
• 判断最优方案的标准：
  1. 条件 1：在最优重复边方案中，图的每一条边上最多只能添加一条重复边。
  2. 条件 2：对图中的任意一个圈，添加的重复边的权值之和，不能超过该圈总权值的一半。如果超过，可以通过“圈上对调”（即给原来没有重复边的边加上重复边，去掉原有的重复边）来降低总路程。
• 步骤：
  1. 配对奇点，通过寻找奇点间的最短路添加初始重复边，使新图无奇点。
  2. 检查新图中是否满足条件 1 和条件 2。若不满足条件 2（即存在某个圈上重复边权之和大于圈总权之一半），则进行调整。
  3. 直至所有圈均满足判定标准，所得方案即为最优方案，新图的任意一个欧拉圈即为最优邮递路线。