《国家集训队2005论文集 任恺》由会员分享，可在线阅读，更多相关《国家集训队2005论文集 任恺（44页珍藏版）》请在金锄头文库上搜索。
1、图论的基本思想及方法湖南省长郡中学 任恺由一道题目浅谈概述 信息学中的图论问题层出不穷， 变化多端，惟有掌握其基本思想 和方法，才能以不变应万变！ 下面通过实例主要从两方面论述 图论的基本思想： 一、合理选择图论模型 二、充分挖掘和利用图的性质雪山上有一个滑雪场。滑雪 场由平台和滑道组成。每个平 台有不同的高度，有一个最高 点和一个最低点。滑道连接着 两个不同的平台，方向是从较 高点到较低点。一些工人要检查滑道。每个工 人从最高点滑到最低点，滑行 路径上的滑道便都被检查了。 每个工人只能滑行一次。不同 工人的滑行路径可以有相同的 滑道。 例题：滑雪者(POI 2002)问题：最少要多少个工人
2、才能检查完所有的滑道呢？Nar.in 6 2 2 3 2 3 4 2 4 5 1 6 2 4 6Nar.out 4顶点个数n (1n5000) 从左到右描述第i个顶点发出 边的另一个端点 例题：滑雪者(POI 2002)123456选择模型(1)网络流模型 最高点 最低点 每条滑道可以多次通过 每条滑道必须被检查 有向无环图网络的源点 s 网络的汇点 t边下界 l 为1边上界 u 为分析样例，发现问题中有如下关键点：很容易想到建立一个网络流模型：最 高 点最 低 点st1,1,1,1,1,1,1,1,1,确定所求目标建立模型后，可以确定要求的目标：求图G中一个最小可行流，满足：st213122
3、111a) 每条边的流量大于等于下界b) 从源点流出的总流量最小求最小流的方法如何求图G的最小流呢求最小流可以分成两步：1）求出图G上的可行流 f2）将可行流 f 转化成最小流 对于有上下界的网络，通常用构造附 加网络的方法求可行流。 但是观察图G可以发现，边的上界都是 无穷大，也就是说没有流量上限。jistui,j = 因此可以利用这个性质构造可行流求可行流的方法jist求可行流的方法枚举每条流量为0的边，设为(i, j)任意找到一条从 s 到 i 的路径 和一条从 j 到 t 的路径那么s i j t 便是一条可行的流， 将这条路径上的边流量加1， 便满足 了边(i, j)的容量下界fi,
4、j = 0fi,j = 1+1+1f 可行 jist求最小流设用上法求出的可行流的总流量 为F，这个可行流可能“过剩”。因此要将多余的流从汇点“退回” 到源点。f 最小求最小流sjit在新图中，原图G的边(i, j)拆成两条边：边(i, j), ui,j = fi,j li,j，li,j = 0边(j, i), uj,i = ui,j fi,j，lj,i = 0fi,jfi,j li,jui,j fi,j回退“过剩”流量可以用如下方法：求最小流在新图中，从 t 到 s 求出一个最大 流，令这个最大流的总流量为F。sjitfi,j li,jui,j fi,j可得图G的最小流的流量为F F。算法一
5、的复杂度 易知构造可行流的时间复杂度为O(nm) 修改可行流所用的最大流算法时间复 杂度为O(mC)，其中C为增广的次数。 由于图G是平面图，所以边数是O(n)级 别。而由可行流构造方法可知，增广次 数C也是O(n)级别。总的复杂度为O(n2) 是否存在效率更高的算法？选择模型(2)另辟蹊径的偏序集下面介绍的偏序集模型将更好的 解决此问题。 算法一能够很迅速的解决原题数据。 但当n的范围扩大时，算法一便无能 为力了。偏序集的定义偏序集是一个集合P和一个偏序关 系 ，满足下列性质：自反性：所有xP，都有x x。反对称性： 所有x,yP，若x y且y x，则x = y。传递性： 所有x,y,z P
6、，若x y且y z，则x z。 链：链是P的一个子集C，在偏序 关系下，它的每一对元素都是可 比的。偏序集的相关概念 反链：反链是P的一个子集A，在偏 序关系下，它的每一对元素都是 不可比的。 对于属于P的两个元素x、y，若有x y 或 y x，则x和y被称作是可比的，否 则被称为不可比的。 E中的偏序关系： 对于边u,vE, u v当且仅当u = v或图 G中存在 v到 u的一条路径。问题的偏序集模型图G可以定义成一个偏序集E： E中的元素是图G中的边；uvu v问题的偏序集模型因此，原问题可以重新用偏序集语言 表述为 ：将偏序集（E, ）划分成最少的链， 使得这些链的并集包含所有E中的元
7、素。 可以发现，图G中从最高点到最低点 的路径对应了E的一个链。目标的转化 直接计算链的最少个数与网络流没有差别 唯有继续转化目标目标的转化 链和反链的计数满足下列关系：Dilworth定理 令(E, )是一个有限偏序 集，并令LA是E中最大反链的大小，SC 是将E划分成最少的链的个数。在E中， 有 LA = SC。求E中最长反链的大小 目标最终转化为：求最长的反链由偏序集E的定义可以知道：偏序集E中的反链对应着图G中的一些边，其 中任意两条边之间都不能互达。右图橙色线段便是样例的最长反链如果用一条线将最长反 链所对应的边从左到右 连起来 那么这条线不会与平面 图中的其它边相交 ！这些线段满足
8、如下性质：求最长的反链换句话说，将最长反链所对 应的边从左到右排列好，相 邻的两条边一定是在同一个 域（闭曲面）中。（结论一）所谓域，是指由从极高点到极低 点的两条独立路径围成的一个曲 面，在这个曲面里没有其他的点 和边。 极高点极低点左边界右边界求最长的反链令f(x)表示图G中在边x左边的平面区域中 以x结尾的最长反链的长度。 由结论一可以用递推方法计算最长反链：求最长的反链设x在某个域F的右边界上， 有递推式：f (x) = max f (y) + 1 (y属于F的左边界）递推式(1)f (y)f (x)= f (y) + 1ABCD因此只需要将所有 的域求出来，然后 按照一定的顺序， 在
9、每个域上运用递 推式(1)求解每条边 的 f 函数。一定的顺序求最长的反链递推的顺序一定的顺序如何确定递推的顺序呢？一个域能够进行递推的前提条件 它左边界上的边的 f 函数都已经求出以此可以确定递推顺序：若域B左边界上的 某条边在域A的右边界上，则A一定先于B 进行递推。ABAB先于注意到，题目中的输入文件格式满足：对于任意顶点，和它相邻的点已经 从左到右排好序。因此很容易想到 一个方法，能够 按照递推顺序找 到所有的域！DFS深度优先 遍历算法的选择找到了递推关系，接下来只需要选择合适的 算法求出图G中所有的域来进行递推。算法设计DFS对图G进行深度优先遍历，图G中的 顶点在遍历中有三种状态
10、：一开始，所有点都处于未 遍历的状态。当遍历到一个点，但没有检 查完它发出的边时，标记这 个点为未扩展完的状态。当一个点发出的边都被检 查完时，这个点标记为扩 展完毕状态。在遍历中用一个指针prev 记录v最新的前驱结点。当u1扩展到v时，后来检查u2发出的边(u2, v)时，指针pre的更新方式如下：prev = u1。prev = u2。虽然v已经扩展完毕，但仍 更新prev ：u1u2v算法设计DFS可知，点v 一定是边(u, v) 所在域的极低点。根据DFS中点的状态和指针pre就 可以按如下方法确定图G中的域：当检查点u的某条边时，发 现边的另一个顶点v已经被 扩展完毕。而prev和
11、u最近公共祖先 点一定是域的极高点。vprevuvh极高点极低点算法设计DFS寻找prev和u的最近公 共祖先，只需要利用pre 回溯寻找v的祖先，第一 个未被扩展完毕的祖先 便是域的极高点。从v到prev再回溯到vh的 路径便是域的左边界。从极高点到u再到v的路 径便是域的右边界。vprevuvh极高点极低点算法设计DFSvlvh极高点极低点找到域之后，域左边界 上的边都被遍历过，f 函数都已经求出。Ff (x) = max f (y) + 1可见，DFS寻找图G的 域的同时，已经完成 f 函数的求解。问题解决算法设计DFSf (y)f (x)算法二的复杂度对每一个点进行DFS遍历，复杂度为
12、O(|E|)；回溯寻找每个域边界上的边，并且进行 递推求解。由于是平面图，每条边最多属 于两个不同域的边界，因此这一步的复杂 度为O(|E|+|F|)。因为原题给出的图是平面图，根据欧拉定 理，边数|E|和域数|F|都是O(n)级别的。总的复杂度为O(n) 算法一直接根据题目描述建立了网络流 模型，体现了原题的网络有向无环图特 性。总结没有利用图G平 面图的性质解法具有一般性，适 用任何有向无环图算法一的效率不 是最优直接从定义下手的 思考方式值得借鉴总结算法二很好的利用偏序集模型实现了问 题目标的转变，从原来的网络流问题回 归到问题本身的平面图上，完整的揭示 了问题的本质。 两个算法思考历程
13、的共同点实际问题寻找合适的图论模型以图论模型为 平台挖掘问题 的性质设计相应 的算法解决问题结语“模型”图论基本思想的精华解决图论问题的关键建立模型熟练掌握经典模型勇于探索，大胆创新挖掘利用 模型性质独具慧眼一击中的样例的模拟下面在样例上模拟运行算法二， 说明算法二是如何执行的： 123456从结点1开始遍历一直深搜到结点6可知(1,2), (2,4)和(4,6) 为最靠左的边，所以 f 值为1f(1,2)=1f(2,4)=1f(4,6)=1样例的模拟123456回溯到2，扩展结点3扩展结点4，发现4已 经被扩展。根据前驱 指针找到域A。进行递推： f (2, 3) = f (2, 4) +
14、1 = 2 f (3, 4) = f (2, 4) + 1 = 2将4的前驱指针指向3f(1,2)=1f(2,4)=1f(4,6)=1f(2,3)=2f(3,4)=2样例的模拟回溯到3，扩展结点5扩展结点4，发现4已 经被扩展。根据前驱 指针找到域A。进行递推： f (3, 5) = f (3, 4) + 1 = 3 f (5, 4) = f (3, 4) + 1 = 3将4的前驱指针指向5123456f(1,2)=1f(2,4)=1f(4,6)=1f(2,3)=2f(3,4)=2 f(3,5)=3f(5,4)=3样例的模拟扩展结点6，发现6已 经被扩展。根据前驱 指针找到域C。进行递推： f (5, 6) = maxf (4, 5), f (4,6) + 1 = 4将6的前驱指针指向5123456f(1,2)=1f(2,4)=1f(4,6)=1f(2,3)=2f(3,4)=2 f(3,5)=3f(5,4)=3f(5,6)=4回溯到1扩展结点3，发现3已 经被扩展。根据前驱 指针找到域D。样例的模拟进行递推： f (1,3) = maxf (1,2), f (2,3) + 1 = 3123456f(1,2)=1f(4,6)=1f(2,3)=2f(3,4)=2 f(3,5)=3f(5,4)=3f(5,6)=4f(1,3)=3f(2,4)=1
