算法合集之《图论的基本思想及方法》.ppt

《算法合集之《图论的基本思想及方法》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论的基本思想及方法湖南省长郡中学任恺由一道题目浅谈——概述信息学中的图论问题层出不穷，变化多端，惟有掌握其基本思想和方法，才能以不变应万变！下面通过实例主要从两方面论述图论的基本思想：一、合理选择图论模型二、充分挖掘和利用图的性质雪山上有一个滑雪场。滑雪场由平台和滑道组成。每个平台有不同的高度，有一个最高点和一个最低点。滑道连接着两个不同的平台，方向是从较高点到较低点。一些工人要检查滑道。每个工人从最高点滑到最低点，滑行路径上的滑道便都被检查了。每个工人只能滑行一次。不同工人的滑行路径可以有相同的滑道。例题：滑雪者(PO

2、I2002)问题：最少要多少个工人才能检查完所有的滑道呢？Nar.in622323424516246Nar.out4顶点个数n(1≤n≤5000)从左到右描述第i个顶点发出边的另一个端点例题：滑雪者(POI2002)123456选择模型(1)——网络流模型最高点最低点每条滑道可以多次通过每条滑道必须被检查有向无环图——网络的源点s——网络的汇点t——边下界l为1——边上界u为∞分析样例，发现问题中有如下关键点：很容易想到建立一个网络流模型：最高点最低点st1,∞1,∞1,∞1,∞1,∞1,∞1,∞1,∞1,∞确定所求目标建

3、立模型后，可以确定要求的目标：求图G中一个最小可行流，满足：st213122111a)每条边的流量大于等于下界b)从源点流出的总流量最小求最小流的方法如何求图G的最小流呢求最小流可以分成两步：1）求出图G上的可行流f2）将可行流f转化成最小流对于有上下界的网络，通常用构造附加网络的方法求可行流。但是观察图G可以发现，边的上界都是无穷大，也就是说没有流量上限。jistui,j=∞因此可以利用这个性质构造可行流求可行流的方法jist求可行流的方法枚举每条流量为0的边，设为(i,j)任意找到一条从s到i的路径和一条从j到t的路径

4、那么s–i–j–t便是一条可行的流，将这条路径上的边流量加1，便满足了边(i,j)的容量下界fi,j=0fi,j=1+1+1f可行jist求最小流设用上法求出的可行流的总流量为F，这个可行流可能“过剩”。因此要将多余的流从汇点“退回”到源点。f最小求最小流sjit在新图中，原图G的边(i,j)拆成两条边：边(i,j),u'i,j=fi,j–li,j，l'i,j=0边(j,i),u'j,i=ui,j–fi,j，l'j,i=0fi,jfi,j–li,jui,j–fi,j回退“过剩”流量可以用如下方法：求最小流在新图中，从t到s

5、求出一个最大流，令这个最大流的总流量为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的范围扩大时，算法一便无能为力了

6、。偏序集的定义偏序集是一个集合P和一个偏序关系≤，满足下列性质：自反性：所有x∈P，都有x≤x。反对称性：所有x,y∈P，若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,v∈E,u≤v当且仅当u=v或图G中存在v到u的一

7、条路径。问题的偏序集模型图G可以定义成一个偏序集E：E中的元素是图G中的边；uvu≤v问题的偏序集模型因此，原问题可以重新用偏序集语言表述为：将偏序集（E,≤）划分成最少的链，使得这些链的并集包含所有E中的元素。可以发现，图G中从最高点到最低点的路径对应了E的一个链。目标的转化直接计算链的最少个数——与网络流没有差别唯有——继续转化目标目标的转化链和反链的计数满足下列关系：Dilworth定理令(E,≤)是一个有限偏序集，并令LA是E中最大反链的大小，SC是将E划分成最少的链的个数。在E中，有LA=SC。求E中最长反链的大

8、小目标最终转化为：求最长的反链由偏序集E的定义可以知道：偏序集E中的反链对应着图G中的一些边，其中任意两条边之间都不能互达。右图橙色线段便是样例的最长反链如果用一条线将最长反链所对应的边从左到右连起来那么这条线不会与平面图中的其它边相交！这些线段满足如下性质：求最长的反链换句话说，将最长反链所对应的边从