图论的基本思想及方法

图论的基本思想及方法湖南省长郡中学湖南省长郡中学任恺任恺由一道题目浅谈概述概述 信息学中的图论问题层出不穷，信息学中的图论问题层出不穷，变化多端，惟有掌握其变化多端，惟有掌握其基本思想基本思想和方法和方法，才能以不变应万变！，才能以不变应万变！下面通过实例主要从两方面论述下面通过实例主要从两方面论述图论的基本思想：图论的基本思想：一、合理选择图论模型一、合理选择图论模型 二、充分挖掘和利用图的性质二、充分挖掘和利用图的性质雪山上有一个滑雪场。滑雪雪山上有一个滑雪场。滑雪场由平台和滑道组成。每个平场由平台和滑道组成。每个平台有不同的高度，有一个最高台有不同的高度，有一个最高点和一个最低点。滑道连接着点和一个最低点。滑道连接着两个不同的平台，方向是从较两个不同的平台，方向是从较高点到较低点。高点到较低点。一些工人要检查滑道。每个工一些工人要检查滑道。每个工人从最高点滑到最低点，滑行人从最高点滑到最低点，滑行路径上的滑道便都被检查了。路径上的滑道便都被检查了。每个工人只能滑行一次。不同每个工人只能滑行一次。不同工人的滑行路径可以有相同的工人的滑行路径可以有相同的滑道。滑道。例题：滑雪者例题：滑雪者(POI 2002)问题：最少要多少个工人问题：最少要多少个工人才能检查完所有的滑道呢？才能检查完所有的滑道呢？Nar.in6 2 2 32 3 42 4 51 62 4 6Nar.out4顶点个数顶点个数n(1n5000)从左到右从左到右描述第描述第i个顶点发出个顶点发出边的另一个端点边的另一个端点 例题：滑雪者例题：滑雪者(POI 2002)123456选择模型选择模型(1)网络流模型网络流模型 最高点最高点 最低点最低点 每条滑道可以多次通过每条滑道可以多次通过 每条滑道必须被检查每条滑道必须被检查 有向无环图有向无环图网络的源点网络的源点 s网络的汇点网络的汇点 t边下界边下界 l 为为1边上界边上界 u 为为分析样例，发现问题中有如下关键点：分析样例，发现问题中有如下关键点：很容易想到建立一个很容易想到建立一个网络流模型网络流模型：最高点最低点st1,1,1,1,1,1,1,1,1,确定所求目标确定所求目标建立模型后，可以确定要求的建立模型后，可以确定要求的目标目标：求图求图G中一个最小可行流，满足：中一个最小可行流，满足：st213122111a)每条边的流量大于等于下界每条边的流量大于等于下界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,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。算法一的复杂度算法一的复杂度 易知构造可行流的时间复杂度为易知构造可行流的时间复杂度为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，若，若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中的元中的元素。素。可以发现，图可以发现，图G中从最高点到最低点中从最高点到最低点的路径对应了的路径对应了E的一个链。的一个链。目标的转化目标的转化 直接计算链的最少个数直接计算链的最少个数与网络流没有差别与网络流没有差别 唯有唯有继续转化目标继续转化目标目标的转化目标的转化 链和反链的计数满足下列关系：链和反链的计数满足下列关系：Dilworth定理定理 令令(E,)是一个有限偏序是一个有限偏序集，并令集，并令LA是是E中最大反链的大小，中最大反链的大小，SC是将是将E划分成最少的链的个数。在划分成最少的链的个数。在E中，中，有有 LA=SC。求求E中最长反链的大小中最长反链的大小 目标最终转化为：目标最终转化为：求最长的反链求最长的反链由偏序集由偏序集E的定义可以知道：的定义可以知道：偏序集偏序集E中的反链对应着图中的反链对应着图G中的一些边，其中的一些边，其中任意两条边之间都不能互达。中任意两条边之间都不能互达。右图橙色线段便是样例的最长反链右图橙色线段便是样例的最长反链如果用一条线将最长反如果用一条线将最长反链所对应的边从左到右链所对应的边从左到右连起来连起来 那么这条线不会与平面那么这条线不会与平面图中的其它边相交图中的其它边相交！这些线段满足如下性质：这些线段满足如下性质：求最长的反链求最长的反链换句话说，换句话说，将最长反链所对将最长反链所对应的边从左到右排列好，相应的边从左到右排列好，相邻的两条边一定是在同一个邻的两条边一定是在同一个域（闭曲面）中。域（闭曲面）中。（结论一）（结论一）所谓域，是指由从极高点到极低所谓域，是指由从极高点到极低点的两条独立路径围成的一个曲点的两条独立路径围成的一个曲面，在这个曲面里没有其他的点面，在这个曲面里没有其他的点和边。和边。极高点极低点左边界右边界求最长的反链求最长的反链令令f(x)表示图表示图G中在边中在边x左边的平面区域中左边的平面区域中以以x结尾的最长反链的长度。结尾的最长反链的长度。由结论一可以用递推方法计算最长反链：由结论一可以用递推方法计算最长反链：求最长的反链求最长的反链设设x在某个域在某个域F的右边界上，的右边界上，有递推式：有递推式：f(x)=max f(y)+1(y属于属于F的左边界）的左边界）递推式递推式(1)f(y)f(x)=f(y)+1ABCD因此只需要将因此只需要将所有所有的域的域求出来，然后求出来，然后按照按照一定的顺序一定的顺序，在每个域上运用递在每个域上运用递推式推式(1)求解每条边求解每条边 的的 f 函数。函数。一定的顺序求最长的反链求最长的反链递推的顺序递推的顺序一定的顺序一定的顺序如何确定递推的顺序呢？如何确定递推的顺序呢？一个域能够进行递推的前提条件一个域能够进行递推的前提条件它左边界上的边的它左边界上的边的 f 函数都已经求出函数都已经求出以此可以确定递推顺序：若域以此可以确定递推顺序：若域B左边界上的左边界上的某条边在域某条边在域A的右边界上，则的右边界上，则A一定先于一定先于B进行递推。进行递推。ABAB先于注意到，题目中的输入文件格式满足：注意到，题目中的输入文件格式满足：对于任意顶点，和它相邻的点已经对于任意顶点，和它相邻的点已经从左到右排好序。从左到右排好序。因此很容易想到因此很容易想到一个方法，能够一个方法，能够按照递推顺序找按照递推顺序找到所有的域！到所有的域！DFS深度优先深度优先遍历遍历算法的选择算法的选择找到了递推关系，接下来只需要选择合适找到了递推关系，接下来只需要选择合适的算法求出图的算法求出图G中所有的域来进行递推。中所有的域来进行递推。算法设计算法设计DFS对图对图G进行深度优先遍历，图进行深度优先遍历，图G中的中的顶点在遍历中有三种状态：顶点在遍历中有三种状态：一开始，所有点都处于一开始，所有点都处于未未遍历遍历的状态。的状态。当遍历到一个点，但没有检当遍历到一个点，但没有检查完它发出的边时，标记这查完它发出的边时，标记这个点为个点为未扩展完未扩展完的状态。的状态。当一个点发出的边都被检当一个点发出的边都被检查完时，这个点标记为查完时，这个点标记为扩扩展完毕展完毕状态。状态。在遍历中用一个指针在遍历中用一个指针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和和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遍历，复杂度为遍历，复杂度为O(|E|)；回溯寻找每个域边界上的边，并且进行回溯寻找每个域边界上的边，并且进行递推求解。由于是平面图，每条边最多递推求解。由于是平面图，每条边最多属于两个不同域的边界，因此这一步的属于两个不同域的边界，因此这一步的复杂度为复杂度为O(|E|+|F|)。因为原题给出的图是平面图，根据欧拉定因为原题给出的图是平面图，根据欧拉定理，边数理，边数|E|和域数和域数|F|都是都是O(n)级别的。级别的。总的复杂度为总的复杂度为O(n)算法一直接根据题目描述建立了网络流算法一直接根据题目描述建立了网络流模型，体现了原题的网络有向无环图特模型，体现了原题的网络有向无环图特性。性。总结总结没有利用图没有利用图G平平面图的性质面图的性质解法具有一般性，适解法具有一般性，适用任何有向无环图用任何有向无环图算法一的效率不算法一的效率不是最优是最优直接从定义下手的直接从定义下手的思考方式值得借鉴思考方式值得借鉴总结总结算法二很好的利用偏序集模型实现了问算法二很好的利用偏序集模型实现了问题目标的转变，从原来的网络流问题回题目标的转变，从原来的网络流问题回归到问题本身的平面图上，完整的揭示归到问题本身的平面图上，完整的揭示了了问题的本质问题的本质。两个算法思考历程的共同点两个算法思考历程的共同点实际问题实际问题寻找合适的图论模型寻找合适的图论模型以图论模型为以图论模型为平台挖掘问题平台挖掘问题的性质的性质设计相应设计相应的算法的算法解决问题解决问题结语结语“模型模型”图论基本思想的精华图论基本思想的精华解决图论问题的关键解决图论问题的关键建立模型建立模型熟练掌握经典模型熟练掌握经典模型勇于探索，大胆创新勇于探索，大胆创新挖掘利用挖掘利用模型性质模型性质独具慧眼独具慧眼一击中的一击中的样例的模拟下面在样例上模拟运行算法二，说明算法二是如何执行的：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)+1=2f(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=3f(5,4)=f(3,4)+1=3将4的前驱指针指向5123456f(1,2)=1f(2,4)=1f(4,6)=1f(2,3)=2f(3,4)=2f(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)=2f(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)=2f(3,5)=3f(5,4)=3f(5,6)=4f(1,3)=3f(2,4)=1