算法合集之〔图论基本思想及方法〕.ppt

图论的基本思想及方法 湖南省长郡中学 任恺 概述 信息学中的图论问题层出不穷，变化多端，惟有掌握其基本思想和方法，才能以不变应万变！ 例题：滑雪者(POI 2002) 例题：滑雪者(POI 2002) 选择模型(1)——网络流模型 最高点 最低点 每条滑道可以多次通过 每条滑道必须被检查 有向无环图 确定所求目标 求最小流的方法 对于有上下界的网络，通常用构造附加网络的方法求可行流。 算法一的复杂度 易知构造可行流的时间复杂度为O(nm) 选择模型(2)——另辟蹊径的偏序集 是否存在效率更高的算法？ 偏序集的定义 偏序集是一个集合P和一个偏序关系≤ ，满足下列性质： 偏序集的相关概念 链：链是P的一个子集C，在偏序关系≤下，它的每一对元素都是可比的。 问题的偏序集模型 E中的偏序关系： 对于边u,v∈E, u ≤ v当且仅当u = v或图G中存在 v到 u的一条路径。 目标的转化 直接计算链的最少个数 求最长的反链 求最长的反链 求最长的反链 递推的顺序 算法的选择 算法二的复杂度 算法一直接根据题目描述建立了网络流模型，体现了原题的网络有向无环图特性。 算法二很好的利用偏序集模型实现了问题目标的转变，从原来的网络流问题回归到问题本身的平面图上，完整的揭示了问题的本质。 结语 样例的模拟 寻找pre[v]和u的最近公共祖先，只需要利用pre回溯寻找v的祖先，第一个未被扩展完毕的祖先便是域的极高点。 从v到pre[v]再回溯到vh的路径便是域的左边界。 从极高点到u再到v的路径便是域的右边界。 v pre[v] u vh 极高点 极低点 算法设计——DFS vl vh 极高点 极低点 找到域之后，域左边界上的边都被遍历过，f函数都已经求出。 F f (x) = max{ f (y) } + 1 可见，DFS寻找图G的域的同时，已经完成 f函数的求解。 问题解决 算法设计——DFS f (y) f (x) 对每一个点进行DFS遍历，复杂度为O(|E|)； 回溯寻找每个域边界上的边，并且进行递推求解。由于是平面图，每条边最多属于两个不同域的边界，因此这一步的复杂度为O(|E|+|F|)。 因为原题给出的图是平面图，根据欧拉定理，边数|E|和域数|F|都是O(n)级别的。 总的复杂度为O(n) 总结 没有利用图G平面图的性质 解法具有一般性，适用任何有向无环图 算法一的效率不是最优 直接从定义下手的思考方式值得借鉴 总结 两个算法思考历程的共同点 实际问题 寻找合适的图论模型 以图论模型为平台挖掘问题的性质 设计相应的算法 解决问题 “模型” 图论基本思想的精华 解决图论问题的关键 建立模型 熟练掌握经典模型 勇于探索，大胆创新 挖掘利用模型性质 独具慧眼 一击中的 下面在样例上模拟运行算法二，说明算法二是如何执行的： 1 2 3 4 5 6 从结点1开始遍历 一直深搜到结点6 可知(1,2), (2,4)和(4,6)为最靠左的边，所以 f 值为1 f(1,2)=1 f(2,4)=1 f(4,6)=1 样例的模拟 1 2 3 4 5 6 回溯到2，扩展结点3 扩展结点4，发现4已经被扩展。根据前驱指针找到域A。 进行递推： f (2, 3) = f (2, 4) + 1 = 2 f (3, 4) = f (2, 4) + 1 = 2 将4的前驱指针指向3 f(1,2)=1 f(2,4)=1 f(4,6)=1 f(2,3)=2 f(3,4)=2 * * 由一道题目浅谈—— 下面通过实例主要从两方面论述图论的基本思想： 一、合理选择图论模型 二、充分挖掘和利用图的性质 雪山上有一个滑雪场。滑雪场由平台和滑道组成。每个平台有不同的高度，有一个最高点和一个最低点。滑道连接着两个不同的平台，方向是从较高点到较低点。 一些工人要检查滑道。每个工人从最高点滑到最低点，滑行路径上的滑道便都被检查了。每个工人只能滑行一次。不同工人的滑行路径可以有相同的滑道。 问题：最少要多少个工人才能检查完所有的滑道呢？ Nar.in 6 2 2 3 2 3 4 2 4 5 1 6 2 4 6 Nar.out 4 顶点个数n (1≤n≤5000) 从左到右描述第i个顶点发出边的另一个端点 1 2 3 4 5 6 ——网络的源点 s ——网络的汇点 t ——边下界 l 为1 ——边上界 u 为∞ 分析样例，发现问题中有如下关键点： 很容易想到建立一个网络流模型： 最高点 最低点 s t 1,∞ 1,∞ 1,∞ 1,∞ 1,∞ 1,∞ 1,∞ 1,∞ 1,∞ 建立模型后，可以确定要求的目标： 求图G中一个最小可行流，满足： s t 2 1 3 1 2 2 1 1 1 a) 每条边的流量大于等于下界 b) 从源点流出的总流量最小 如何求图G的最小流呢 求最小流可以