图的应用

最小生成树

生成树回

• 生成树：所有顶点均由边连接在一起，但不存在回路的 图
• 一个图可以有多个不同的生成树
• 所有的生成树具有以下的共同特点: 生成树的顶点个数与图的顶点个数相同 生成图是图的极小连通子图，去掉一条边则非连通 n 个结点的连通图的生成树有 n-1 条边 生成树再加一条边会形成回路
• 无向图的生成树:
  • 深度优先生成树
  • 广度优先生成树

最小生成树

对于一个无向网, 该网所得有生成树中, 各边权值和最小的生成树叫做最小生成树.

典型用途: 用最小的成本在城市之间建立通信网

MST 性质:

在生成树的构造过程中, 图的 n 个顶点分为两个集合:

• 已经位于生成树的顶点集: U
• 尚未落入生成树的顶点集: V-U

接下来应该加入连通U与V-U中顶点的边中选取权值最小的边, 且不能形成环路

Prim 算法

思想:

• 开始时 U 中仅包含一个顶点, 在 U 集合中找一个顶点, V-U 中找一个顶点, 将依附于这两个顶点的边加入生成树, 这条边具有的特点是: 符合要求的边中权值最小.

Kruskal 算法

思想:

• 贪心. 一开始最小生成树的状态为 n 个顶点而无边的非连通图 T=(V,{}), 每个顶点自成一个连通分量.
• 在边集合 E 中选取权值最小的边, 若该边依附的顶点落在 T 的不同连通分量上(即加入这条边不会形成环) , 则将这条边加入T ,否则舍去这条边, 选取下一条代价最小的边.

两个算法的比较:

最短路径

典型应用: 交通网络问题:

• 顶点:地点
• 弧:表示两个地点之间连通
• 弧上的权值: 两个地点之间额距离, 交通费或者途中花费的时间等等

问题抽象: 在有向网中 A 点到 B 点的多条路径中, 寻找一条权值和最小的路径,称为最短路径.

与最小生成树的区别: 最短路径不一定要包括所有的顶点或边.

Dijkstra 算法—单源最短路径

Floyd 算法—所有顶点间的最短路径

求所有顶点间的最短路径：

• 以每一个顶点为源点，重复执行 Dijkstra 算法 n 次 O(n^3)
• Floyd 算法

初始：建立一个邻接矩阵, 对角线元素置为0, 不直接相连的顶点置为\infty , 否则置为权值. 然后依次在原来的直接路径中加入中间顶点, 若加入后路径变短, 则修改. 所有顶点探查完毕后, 结束.

过程图

用顶点表示活动的网络(AOV网络)

把一个工程分为若干个子工程, 只要这些子子工程(活动)完成了, 工程就完成了.

AOV网络: 用一个有向图表示一个工程的各个子工程的相互制约关系, 顶点表示活动, 边表示活动之间的制约

拓扑排序

由上表得 AOV 图:

AOV 网络特点:

• i 到 j 有一条有向路径, 则 i 为 j 的前驱, j 为 i 的后继.
• 若 为图中有向边, 则 i 为 j 的直接前驱, j 为 i 的直接后继.
• 由于AOV 网络中, 前驱表示先决条件, 因此在 AOV 网络中不允许出现有向环, 对于给定的 AOV 网络, 必须判断它是否存在有向环——拓扑排序

拓扑排序的定义:

• 将 AOV 网络中各个顶点排列成一个线性有序序列, 保证原 AOV 网络中的前驱顶点一定位于后继顶点之前.

步骤:

• 在网络中找一个没有前驱的顶点输出.
• 在网络中删除这个顶点以及所有出边.
• 不断重复, 直到找不到无前驱的顶点(此时网络中仍然存在顶点,则该AOV图中含有向环)或者所有的顶点都已经输出.

如上述 AOV 图可以这样拓扑排序(注意不唯一):

用边表示活动的网络 (AOE 网络)

AOE 网络: 用有向边表示活动, 有向边上的权值表示持续时间,顶点表示事件.

如图所示, 事件表示在它值钱的活动已经完成, 之后的活动可以开始.

对应的有向图:

AOE 网络应用:

• 估计工程总共需要的时间
• 为缩短工程所需时间, 应该加快哪些活动?

关键路径

定义: 路径长度最长的路径

• 入度为零的点: 源点, 表示工程开始
• 出度为零的点: 汇点, 表示工程结束

只要找到了关键路径, 上面的两个问题就能解决.

几个描述量:

• ve(vj):事件 v_j 最早发生时间
• vl(vj):事件 v_j 最晚发生时间
• e(i): 活动 a_i 最早开始时间
• l(i):活动 a_i 最晚开始时间
• l(i)-e(i): 完成活动 a_i 的时间余量, 即在这一段时间内任何时候开始都不会影响到进度.

关键活动: 关键路径上的活动,l(i)- e(i)==0.只要找到关键活动, 就能构建关键路径.

对于一个事件来讲, 它相邻的活动可能不止两个;对于一个活动来讲, 他相邻的事件仅有确定的两个.

v_i-a(不止一个)->v_j-b->v_k

需要计算的量:

• e(b) = ve(v_j)
• l(b) = vl(v_k)-w_{j,k}
• ve(v_j) = \max(ve(v_i)+w_{i,j})
• vl(v_j)=\min(vl(v_k)-w_{j,k})

步骤:

1. 正向计算 ve() ve(v_1)= 0, 则根据递推公式可以求出
2. 反向计算 vl() 由最后一个事件的最晚结束时间往前推
3. 求各个活动的 l()-e()

举个例子：

对于这张网络:

有如下分析:

则关键路径为:

     
V1→V2→V5→V8/V7→V9

分析:

• 两个顶点之间存在多条关键路径, 需要同时缩短这些关键路径以减少总的时间.
• 若关键事件缩减过多, 会造成它不再是关键事件.