有向图衍生
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}$的时间余量
- 提前完成非关键活动不能加快工程进度
- 关键活动耗时一定范围变化影响工程整体完成时间
考虑如下事件和活动发生关系有
- $ve_i, vl_i$：事件（顶点）i最早、最晚发生的时间
- $a{ij}$：活动$a{ij}$需要持续时间
对$ve_i, vl_i$，存在如下递推关系
则依拓扑排序可计算得$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
流量守恒要求：除源点、汇点外其余顶点只能改变流方向，进入、 流出物质总量不变，不能消耗、添加物质
- 其中$x_{ij}$表示通过边$(i,j)$的流量（传输量）
- 等式左右为进入、离开顶点i的输入、输出流总和
并且
- 流的值 = 源点输出流 = 汇点输入流
- 可通过流量守恒要求推出
最大流
最大流：分配流量网络中边权（实际流量），使得网络在满足流量 守恒、容量束情况下，最大的流的值（边容量都为正整数）
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$的流量之和的差值（可由流量守恒推导）
由流量非负可得
即网络上任何可行流值不能超过网络上任意割容量
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^{*}$
则有
即存在某个割容量等于流量增益法得到最终流量值
