《图论的基本思想及方法》ppt课件

1、图论的根本思想及方法由一道标题浅谈概述概述 信息学中的图论问题层出不穷，信息学中的图论问题层出不穷，变化多端，惟有掌握其根本思想变化多端，惟有掌握其根本思想和方法，才干以不变应万变！和方法，才干以不变应万变！ 下面经过实例主要从两方面论述下面经过实例主要从两方面论述图论的根本思想：图论的根本思想： 一、合理选择图论模型一、合理选择图论模型 二、充分发掘和利用图的性质二、充分发掘和利用图的性质雪山上有一个滑雪场。滑雪雪山上有一个滑雪场。滑雪场由平台和滑道组成。每个平场由平台和滑道组成。每个平台有不同的高度，有一个最高台有不同的高度，有一个最高点和一个最低点。滑道衔接着点和一个最低点。滑道衔接着两

2、个不同的平台，方向是从较两个不同的平台，方向是从较高点到较低点。高点到较低点。一些工人要检查滑道。每个工一些工人要检查滑道。每个工人从最高点滑到最低点，滑行人从最高点滑到最低点，滑行途径上的滑道便都被检查了。途径上的滑道便都被检查了。每个工人只能滑行一次。不同每个工人只能滑行一次。不同工人的滑行途径可以有一样的工人的滑行途径可以有一样的滑道。滑道。 例题：滑雪者例题：滑雪者(POI 2002)问题：最少要多少个工人问题：最少要多少个工人才干检查完一切的滑道呢？才干检查完一切的滑道呢？Nar.in6 2 2 32 3 42 4 51 62 4 6Nar.out4顶点个数顶点个数n (1n5000

3、)从左到右描画第从左到右描画第i i个顶点发出个顶点发出边的另一个端点边的另一个端点 例题：滑雪者例题：滑雪者(POI 2002)123456选择模型选择模型(1)网络流模型网络流模型 最高点最高点 最低点最低点 每条滑道可以多次经过每条滑道可以多次经过 每条滑道必需被检查每条滑道必需被检查 有向无环图有向无环图网络的源点 s网络的汇点 t边下界 l 为1边上界 u 为分析样例，发现问题中有如下关键点：分析样例，发现问题中有如下关键点：很容易想到建立一个网络流模型：很容易想到建立一个网络流模型：最高点最低点st1,1,1,1,1,1,1,1,1,确定所求目的确定所求目的建立模型后，可以确定要求

4、的目的：建立模型后，可以确定要求的目的：求图求图G中一个最小可行流，满足：中一个最小可行流，满足：st213122111a) 每条边的流量大于等于下界每条边的流量大于等于下界b) 从源点流出的总流量最小从源点流出的总流量最小求最小流的方法求最小流的方法如何求图如何求图G的最小流呢的最小流呢求最小流可以分成两步：求最小流可以分成两步：1求出图求出图G上的可行流上的可行流 f2将可行流将可行流 f 转化成最小流转化成最小流 对于有上下界的网络，通常用构造附对于有上下界的网络，通常用构造附加网络的方法求可行流。加网络的方法求可行流。 但是察看图但是察看图G可以发现，边的上界都可以发现，边的上界都是无

5、穷大，也就是说没有流量上限。是无穷大，也就是说没有流量上限。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求最小流求最小

6、流设用上法求出的可行流的总流量设用上法求出的可行流的总流量为为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 求出一个最大求出一

7、个最大流，令这个最大流的总流量为流，令这个最大流的总流量为F。sjitfi,j li,jui,j fi,j可得图可得图G的最小流的流量为的最小流的流量为F F。算法一的复杂度算法一的复杂度 易知构造可行流的时间复杂度为易知构造可行流的时间复杂度为O(nm) 修正可行流所用的最大流算法时间复修正可行流所用的最大流算法时间复杂度为杂度为O(mC)，其中，其中C为增广的次数。为增广的次数。 由于图由于图G是平面图，所以边数是是平面图，所以边数是O(n)级级别。而由可行流构造方法可知，增广次别。而由可行流构造方法可知，增广次数数C也是也是O(n)级别。级别。总的复杂度为总的复杂度为O(n2)选择模型选

8、择模型(2)另辟蹊径的偏序集另辟蹊径的偏序集 能否存在效率更高的算法？能否存在效率更高的算法？下面引见的偏序集模型将更好的下面引见的偏序集模型将更好的处理此问题。处理此问题。 算法一可以很迅速的处理原题数据。算法一可以很迅速的处理原题数据。 但当但当n的范围扩展时，算法一便无能的范围扩展时，算法一便无能为力了。为力了。偏序集的定义偏序集的定义偏序集是一个集合偏序集是一个集合P和一个偏序关和一个偏序关系系 ，满足以下性质：，满足以下性质：自反性：自反性： 一切一切xP，都有，都有x x。反对称性：反对称性：一切一切x,yP，假设，假设x y且且y x，那么，那么x = y。传送性：传送性：一切一

9、切x,y,z P，假设，假设x y且且y z，那么，那么x z。偏序集的相关概念偏序集的相关概念 链：链是链：链是P的一个子集的一个子集C，在偏序，在偏序关系关系下，它的每一对元素都是可下，它的每一对元素都是可比的。比的。 反链：反链是反链：反链是P的一个子集的一个子集A，在偏，在偏序关系序关系下，它的每一对元素都是下，它的每一对元素都是不可比的。不可比的。 对于属于对于属于P的两个元素的两个元素x、y，假设有，假设有x y 或或 y x，那么，那么x和和y被称作是可比的被称作是可比的，否那么被称为不可比的。，否那么被称为不可比的。问题的偏序集模型问题的偏序集模型 E中的偏序关系：中的偏序关系

10、：对于边对于边u,vE, u v当且仅当当且仅当u = v或图或图G中存在中存在 v到到 u的一条途径。的一条途径。图图G可以定义成一个偏序集可以定义成一个偏序集E： E中的元素是图中的元素是图G中的边；中的边；uvu v问题的偏序集模型问题的偏序集模型因此，原问题可以重新用偏序集言语因此，原问题可以重新用偏序集言语表述为表述为 ：将偏序集将偏序集E, 划分成最少的链，划分成最少的链，使得这些链的并集包含一切使得这些链的并集包含一切E中的元中的元素。素。 可以发现，图可以发现，图G中从最高点到最低点中从最高点到最低点的途径对应了的途径对应了E的一个链。的一个链。目的的转化目的的转化 直接计算链

11、的最少个数直接计算链的最少个数与网络流没有差别与网络流没有差别 唯有唯有继续转化目的继续转化目的目的的转化目的的转化 链和反链的计数满足以下关系：链和反链的计数满足以下关系：Dilworth定理定理 令令(E, )是一个有限偏序是一个有限偏序集，并令集，并令LA是是E中最大反链的大小，中最大反链的大小，SC是将是将E划分成最少的链的个数。在划分成最少的链的个数。在E中，中，有有 LA = SC。求求E中最长反链的大小中最长反链的大小 目的最终转化为：目的最终转化为：求最长的反链求最长的反链由偏序集由偏序集E的定义可以知道：的定义可以知道：偏序集偏序集E中的反链对应着图中的反链对应着图G中的一些

12、边，中的一些边，其中恣意两条边之间都不能互达。其中恣意两条边之间都不能互达。右图橙色线段便是样例的最长反链右图橙色线段便是样例的最长反链假设用一条线将最长反假设用一条线将最长反链所对应的边从左到右链所对应的边从左到右连起来连起来 那么这条线不会与平面那么这条线不会与平面图中的其它边相交图中的其它边相交 ！这些线段满足如下性质：这些线段满足如下性质：求最长的反链求最长的反链换句话说，将最长反链所对换句话说，将最长反链所对应的边从左到右陈列好，相应的边从左到右陈列好，相邻的两条边一定是在同一个邻的两条边一定是在同一个域闭曲面中。域闭曲面中。 结论一结论一所谓域，是指由从极高点到极低所谓域，是指由从

13、极高点到极低点的两条独立途径围成的一个曲点的两条独立途径围成的一个曲面，在这个曲面里没有其他的点面，在这个曲面里没有其他的点和边。和边。极高点极低点左边境右边境求最长的反链求最长的反链令令f(x)表示图表示图G中在边中在边x左边的平面区域左边的平面区域中以中以x结尾的最长反链的长度。结尾的最长反链的长度。 由结论一可以用递推方法计算最长反链：由结论一可以用递推方法计算最长反链：求最长的反链求最长的反链设设x在某个域在某个域F的右边境上，的右边境上，有递推式：有递推式：f (x) = max f (y) + 1 (y属于属于F的左边境的左边境递推式递推式(1)f (y)f (x)= f (y)

14、+ 1ABCD因此只需求将一切因此只需求将一切的域求出来，然后的域求出来，然后按照一定的顺序，按照一定的顺序，在每个域上运用递在每个域上运用递推式推式(1)求解每条边求解每条边 的的 f 函数。函数。一定的顺序求最长的反链求最长的反链递推的顺序递推的顺序一定的顺序一定的顺序如何确定递推的顺序呢？如何确定递推的顺序呢？一个域可以进展递推的前提条件一个域可以进展递推的前提条件它左边境上的边的它左边境上的边的 f 函数都曾经求出函数都曾经求出以此可以确定递推顺序：假设域以此可以确定递推顺序：假设域B左边境上左边境上的某条边在域的某条边在域A的右边境上，那么的右边境上，那么A一定先一定先于于B进展递推

15、。进展递推。ABAB先于留意到，标题中的输入文件格式满足：留意到，标题中的输入文件格式满足：对于恣意顶点，和它相邻的点曾经对于恣意顶点，和它相邻的点曾经从左到右排好序。从左到右排好序。因此很容易想到因此很容易想到一个方法，可以一个方法，可以按照递推顺序找按照递推顺序找到一切的域！到一切的域！DFS深度优先深度优先遍历遍历算法的选择算法的选择找到了递推关系，接下来只需求选择适宜找到了递推关系，接下来只需求选择适宜的算法求出图的算法求出图G中一切的域来进展递推。中一切的域来进展递推。算法设计算法设计DFS对图对图G进展深度优先遍历，图进展深度优先遍历，图G中中的顶点在遍历中有三种形状：的顶点在遍历

16、中有三种形状：一开场，一切点都处于未一开场，一切点都处于未遍历的形状。遍历的形状。当遍历到一个点，但没有检当遍历到一个点，但没有检查完它发出的边时，标志这查完它发出的边时，标志这个点为未扩展完的形状。个点为未扩展完的形状。当一个点发出的边都被检当一个点发出的边都被检查完时，这个点标志为扩查完时，这个点标志为扩展终了形状。展终了形状。在遍历中用一个指针在遍历中用一个指针prev记录记录v最新的前驱结点。最新的前驱结点。当当u1扩展到扩展到v时，时，后来检查后来检查u2发出的边发出的边(u2, v)时，时，指针指针pre的更新方式如下：的更新方式如下：prev = u1。prev = u2。虽然虽

17、然v曾经扩展终了，但曾经扩展终了，但仍更新仍更新prev ：u1u2v算法设计算法设计DFS可知，点可知，点v 一定是边一定是边(u, v)所在域的极低点。所在域的极低点。根据根据DFS中点的形状和指针中点的形状和指针pre就就可以按如下方法确定图可以按如下方法确定图G中的域中的域：当检查点当检查点u的某条边时，发的某条边时，发现边的另一个顶点现边的另一个顶点v曾经被曾经被扩展终了。扩展终了。而而prev和和u最近公共祖先最近公共祖先点一定是域的极高点。点一定是域的极高点。vprevuvh极高点极高点极低点极低点算法设计算法设计DFS寻觅寻觅prev和和u的最近公的最近公共祖先，只需求利用共祖

18、先，只需求利用pre回溯寻觅回溯寻觅v的祖先，第一的祖先，第一个未被扩展终了的祖先个未被扩展终了的祖先便是域的极高点。便是域的极高点。从从v到到prev再回溯到再回溯到vh的的途径便是域的左边境。途径便是域的左边境。从极高点到从极高点到u再到再到v的途的途径便是域的右边境。径便是域的右边境。vprevuvh极高点极低点算法设计算法设计DFSvlvh极高点极低点找到域之后，域左边境找到域之后，域左边境上的边都被遍历过，上的边都被遍历过，f函数都曾经求出。函数都曾经求出。Ff (x) = max f (y) + 1可见，可见，DFS寻觅图寻觅图G的的域的同时，曾经完成域的同时，曾经完成 f函数的求

19、解。函数的求解。问题处理问题处理算法设计算法设计DFSf (y)f (x)算法二的复杂度算法二的复杂度对每一个点进展对每一个点进展DFS遍历，复杂度为遍历，复杂度为O(|E|)；回溯寻觅每个域边境上的边，并且进展回溯寻觅每个域边境上的边，并且进展递推求解。由于是平面图，每条边最多递推求解。由于是平面图，每条边最多属于两个不同域的边境，因此这一步的属于两个不同域的边境，因此这一步的复杂度为复杂度为O(|E|+|F|)。由于原题给出的图是平面图，根据欧拉定由于原题给出的图是平面图，根据欧拉定理，边数理，边数|E|和域数和域数|F|都是都是O(n)级别的。级别的。总的复杂度为总的复杂度为O(n) 算

20、法不断接根据标题描画建立了网络流算法不断接根据标题描画建立了网络流模型，表达了原题的网络有向无环图特模型，表达了原题的网络有向无环图特性。性。总结总结没有利用图没有利用图G平平面图的性质面图的性质解法具有普通性，适解法具有普通性，适用任何有向无环图用任何有向无环图算法一的效率不算法一的效率不是最优是最优直接从定义下手的直接从定义下手的思索方式值得自创思索方式值得自创总结总结算法二很好的利用偏序集模型实现了问算法二很好的利用偏序集模型实现了问标题的的转变，从原来的网络流问题回标题的的转变，从原来的网络流问题回归到问题本身的平面图上，完好的提示归到问题本身的平面图上，完好的提示了问题的本质。了问题的本质。 两个算法思索历程的共同点两个算法思索历程的共同点实践问题实践问题寻觅适宜的图论模型寻觅适宜的图论模型以图论模型为以图论模型为平台发掘问题平台发掘问题的性质的性质设计相应设计相应的算法的算法处理问题处理问题结语结语“模型模型图论根本思想的精华图论根本思想的精华处理图论问题的关键处理图论问题的关键建立模型建立模型熟练掌握经典模型熟练掌握经典模型勇于探求，大胆创新勇于探求，大胆创新发掘利用发掘利用模型性质模型性质独具慧眼独具慧眼一击中的一击中的样例的模拟下面在样例上模拟运转算法二，阐明算法二是如何执行的：123456从结点1开场遍历不断深搜到结点6