有向图衍生

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^{*}$

  • 则有

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

Author

UBeaRLy

Posted on

2019-04-11

Updated on

2019-04-11

Licensed under

Comments