有向图衍生

Directed Acycline Graph

DAG：有向无环图

• 描述含有公共子式的表达式的有效工具
  • 可以实现对相同子式的共享，节省存储空间
• 描述一项工程、系统进行过程的有效工具
  • 拓扑排序：工程能否顺利进行
  • 关键活动：整个工程完成必须的最短时间

Dependence Analysis

依赖性分析：由有向图判断、构造可行任务执行序列

Topological Sort

• 拓扑有序：由偏序得到的全序
• 拓扑排序：由偏序定义得到拓扑有序的操作

• 构造有向图中顶点的拓扑有序序列

  • 得到可行任务执行顺序

• 判断有向图AOV-网中是否存在环，即是否为DAG

  • 若图中所有顶点都在拓扑有序序列中，则有向图中不存在环

• 参见algorithm/problems/graph
• AOV网：activity on vertex network，顶点表示活动，弧 表示活动间优先关系的有向图

关键活动优化

Critical Path

关键路径：路径长度最长的路径

• 对整个AOE网，开始点到结束点的关键路径长度即为完成工程 的最短时间

• 对事件$v_i$，从起始点$v_1$到其的关键路径长度即为，以 $v_i$为尾的活动的最早开始时间

• 关键路径上的所有活动均为关键活动

  • 分析关键路径目的就是找出关键活动
  • 提高关键活动工效缩短工期

• AOE网：activity on edge network，顶点表示事件，边表示 活动持续事件的带权有向无环图

  • 一般网络中只有一个源点、汇点，表示工程开始、完成
  • 以上假设AOE网中活动可以并行进行

关键活动

• 关键活动：记$ee{ij}$为活动$a{ij}$最早开始时间、 $el{ij}$为不推迟整个工程完成前提下$a{ij}$最迟开始时间 ，称$ee{ij} = el{ij}$称为关键活动

• $el{ij} - ee{ij}$表示完成活动$a_{ij}$的时间余量

  • 提前完成非关键活动不能加快工程进度
  • 关键活动耗时一定范围变化影响工程整体完成时间

• 考虑如下事件和活动发生关系有

  $$\left \{ \begin{array}{l} ee_{ij} & = ve_{i} \\ el_{ij} & = vl_{j} - a_{ij} \end{array} \right.$$

  • $ve_i, vl_i$：事件（顶点）i最早、最晚发生的时间
  • $a{ij}$：活动$a{ij}$需要持续时间

• 对$ve_i, vl_i$，存在如下递推关系

  $$\left \{ \begin{array}{l} ve_i = \max\{ve_m + a_{mi} \}, & \forall a_{mi} \in E \\ vl_i = \max\{vl_n - a_{in} \}, & \forall a_{in} \in E \end{array} \right.$$

  则依拓扑排序可计算得$ve_i$，逆拓扑排序可计算得$vl_i$

• 参见algorithm/problems/graph
• 为求解AOE网中活动$e{ij}, l{ij}$，应该首先求出事件

Flow Network

流量网络

• 包含一个源点：物质流唯一出发点
• 包含一个汇点：物质流唯一汇聚点
• 每条有向边权重为边capacity的正整数$u_{ij}$
  • 事实上，有理数总可以通过变换变为整数，所以只要容量为 有理数就可以
  • 计算机无法真正处理无理数，无理数边权只具有理论意义

流量约束

Capacity Constraits

容量约束：通过边的流量不大于边容量$x{ij} \leqslant u{ij}$

Flow-Conservation Requirement

流量守恒要求：除源点、汇点外其余顶点只能改变流方向，进入、 流出物质总量不变，不能消耗、添加物质

$$\sum_{i:(i,j) \in E} x_{ij} = \sum_{k:(j,k) \in E} x_{jk}$$

• 其中$x_{ij}$表示通过边$(i,j)$的流量（传输量）
• 等式左右为进入、离开顶点i的输入、输出流总和

并且

$$\sum_{j:(1,j) \in E} x_{1j} = \sum_{i:(i,n) \in E} x_{in}$$

• 流的值 = 源点输出流 = 汇点输入流
• 可通过流量守恒要求推出

最大流

最大流：分配流量网络中边权（实际流量），使得网络在满足流量 守恒、容量束情况下，最大的流的值（边容量都为正整数）

$$\max = \sum_{j:(1,j)} x_{i,j} \\ s.t. 0 \leqslant x_{ij} \leqslant u_{ij} \\ \sum_{j:(j,i) \in E) x_{ji} - \sum_{j:(i,j) \in E} x_{ij} = 0$$

cut

割：$C(X,\bar X)$=所有头在$X$、尾在$\bar X$边集合

• $X$；包含源点、不包含汇点的顶点V的子集
• $\bar X$：$X$的补集，包含汇点
• 删除割中所有边，则不存在从源点的汇点的路径

Augmenting-Path Method

Augmenting-Path

流量增益路径：当前流情况下，可以传输更多流量、从源点到 汇点路径，考虑路径$i \rightarrow j \leftarrow k$中顶点j边

• forward edge：前向边$(i, j)$，同流量网络中边$(i, j)$ 方向相同

  • 具有正的未使用容量$r{ij} = u{ij} - x_{ij}$
  • 可以把该边流量增加最多$r_{ij}$

• backward edge：后向边$(j, k)$，同流量网络中边$(k, j)$ 方向相反

  • 具有正流量$x_{kj}$
  • 可以把该边流量减少最多$x_{kj}$

增益路径法

• 寻找网络中增益路径，设$r$为路径中各前向边未使用容量 $r{ij}$、后向边流量$x{jk}$最小值

• 每条前向边流量加r、后向边流量减r，可以得到新的可行流量， 且流量值增加r，不断迭代

• 基于边容量、流量都为正整数假设

  • r也为正整数，每次迭代流量值至少增加1

  • 流量最大值有上界为源点为起点边容量和，则增益路径法 在有限步迭代后会停止

• 联合最大流-最小割定律可以证明

  • 最终流量一定是最大化的，等于最小割容量
  • 和增量路径选择无关

• 最后一步迭代中

  • 所有已标记顶点和未标记顶点之间边就构成最小割
  • 这样边流量要么满（标记到未标记）、要么空（反）

• 增益路径法具体实现参见graph
• 算法主要问题在于如何寻找增益路径，生成路径的顺序对算法 有巨大影响

Max-Flow Min-Cut Theorem

最大流-最小割定理：网络中最大流量值等于其最小割容量

Theorem1

网络中最大流量值小于任意割容量

• 设可行流量x值为v，割$C(X, \bar_X)$容量为c

• 通过该割的流量为：$X$到$\bar_X$的流量之和与 $\bar_X$到$X$的流量之和的差值（可由流量守恒推导）

  $$v = \sum_{i \in X, j \in \bar_X} x_{ij} - \sum{j \in \bar_X, i \in X} x_{ji}$$

• 由流量非负可得

  $$v \leqslant \sum_{i \in X, j \in \bar_X} x_{ij} \leqslant \sum_{i \in X, j \in \bar_x} u_{ij}$$

  即网络上任何可行流值不能超过网络上任意割容量

  $$v \leqslant c$$

Theorem2

网络中最大流量等于最小割容量，可以使用增益路径法证明

• 设$v^{}$为通过路径增益法得到的最终流$x^{}$的值

• 对增益路径法最终流量情况下，考虑顶点集合$X^{*}$

  • 包含源点
  • 其他顶点可由源点出发，经未使用的容量大于0的前向边、 流量大于0的后向边组成路径到达

• 则汇点不属于$X^{*}$，否则存在一条流量增益路径，不是流量 增益法最终流情况

• 考虑割$C(X^{}, \bar_{X^{}})$

  • $X^{}, \bar_{X^{}}$之间任意边$(i,j)$： $x{ij} = u{ij}$，没有未使用容量

  • $\bar{X^{}}, X^{}$之间任意边$(j,i)$：$x{ji}=0$， 没有流量

  • 否则顶点j$\in X^{*}$

• 则有

  $$\begin{align}{c} v* & = \sum_{i \in X^{*}, j \in \bar_{X^{*}} x_{ij} - \sum{j \in \bar_{X^{*}, i \in X^{*}} x_{ji} \\ & = \sum_{i \in X^{*}, j \in \bar_{X^{*}}} u_{ij} - 0 \\ & = C(X^{*}, \bar_{X^{*}}) \end{align}$$

  即存在某个割容量等于流量增益法得到最终流量值