《算法合集之图论地基本思想及方法》由会员分享，可在线阅读，更多相关《算法合集之图论地基本思想及方法（21页珍藏版）》请在金锄头文库上搜索。
1、word图论的根本思想与方法某某省某某市长郡中学 任恺【摘要】文章着眼于图论根本思想与方法的讨论，不涉与高深的图论算法。文章主要从两方面阐述图论的根本思想：一是合理选择图论模型；二是如何深入挖掘问题本质，充分利用模型的特性。同时还归纳了一些解决问题的普适性方法。【关键字】根本思想、图论模型、问题本质、定义法、分析法、综合法【正文】一、引论图是用点和边来描述事物和事物之间的关系，是对实际问题的一种抽象。之所以用图来解决问题，是因为图能够把纷杂的信息变得有序、直观、清晰。因而图论中最根本的思想就是搭建适宜的模型，深刻挖掘问题的本质，分析和利用图论模型各种性质，从而到达解决问题的目的。下面着重从模型
2、的选择和开掘利用图的性质来阐述图的根本思想和运用方法。二、合理选择图论模型在解决一道实际问题时，往往先将实际问题抽象成一个数学模型，然后在模型上寻找适宜的解决方法，最后再将解决方法复原到实际问题本身。而图论模型就是一种特殊的数学模型。在搭建图论模型时，是通过图中的点和边来表现原问题的特点。搭建的模型务必要真实的、贴切的和透彻的反映出原问题的本质，同时也要做到力求简练、清晰。图论问题往往关系错综复杂，变化多端，因此搭建一个适宜的模型实非易事。在选择图论模型时，应该深入分析实际问题的特点，大胆的猜测和验证。下面通过一个具体实例，来揭示选择适宜图论模型的重要性和一些方法：例一：滑雪者Poland O
3、lympiad of Informatics 2002 Stage III：Skiers题目大意：给出一个平面图，图中有n2 n 5000个点，m条有向边。每个点都有不同的横坐标和纵坐标，有一个最高点vh和一个最低点vl。每条有向边连接着两个不同的点，方向是从较高点连到较低点。对于图中任意一点u，都至少存在一条vh到u的路径和一条u到vl的路径。任务：图中由每个点发出的边都已经按照完毕点的位置从左到右给出。要求你用假如干条从vh到vl的路径覆盖图中所有的边，并且使路径数最少。所谓覆盖，就是指每条边至少在一条路径中出现。选取的路径之间可以有一样的边。题目中和下面分析中所说的路径都是有向路径，假如
4、a到b存在一条路径，并不表示b到a一定存在一条路径。原题请见附录123459681013121171415图2-1样例： 图2-1中所示的平面图最少需要8条路径才能覆盖所有的边。2.1 以网络流为模型分析一下样例，很快联想到经典的网络流模型：最高点vh是网络的源点，而最低点vl是网络的汇点。题目中的路径是网络中从源点到汇点的流。要求用路径覆盖图中所有的边，且路径数最少，就是要求网络中每条边的流量大于等于1，并且从源点流出的总流量最小。因此解决这个问题只需要建立一个有容量下界的网络，然后求这个网络的最小可行流。大致做法：首先求出可行流：枚举每条流量为0的边，设为(i,j)。找到一条从s到i的路径
5、和一条从j到t的路径。对“s i j t路径上的每一条边流量加1，这样既满足了每个点的流量平衡，又满足了边(i, j)的容量下界。然后在可行流上进展修改，从汇点到源点求一个最大可行反向流，就得到了一个最小可行流。分析算法二的复杂度：求可行流时，可以先预处理源点和汇点到每个顶点的路径，因此构造可行流的时间复杂度为O(|E|+|V|)。求最大流时，可以用朴素的增广路算法，复杂度为O(|E|C)，C是进展增广的次数。因为是平面图，根据欧拉公式有O(|E|)=O(|V|)，而反向流的流量最大为O(|E|)，所以总的复杂度为O(|V|2)=O(n2)。此算法实际效率很高，能够迅速的通过测试数据。但是，这
6、种模型并没有很好的挖掘原题中平面图的性质，所以改良的余地应该很大。2.2 以偏序集为模型题目中强调了每个点都有不同的横纵坐标，图是有向无环平面图。而且图中两点之间的有向边似乎反映着一种元素的比拟关系。是否存在更好的模型描述此图呢？为了更好的揭示问题的本质，下面引入偏序集。2.2.1 偏序集的相关概念偏序集是一个集合X和一个二元关系R，符合如下特性：a) 对于X中的所有的x，有x R x，即R是自反的。b) 对于X中的所有的x和y，只要有x R y且xy，就有，即R是反对称的。c) 只要有x R y和y R z，就有x R z，即R是传递的。符合这些特性的关系叫做偏序，通常用标记R。ab也可以记
7、作ba。假如有ab，且ab，那么就记作a a。又叫做严格偏序关系。含偏序的偏序集X用(X, )表示。令R是集合X上的一个偏序，对于属于X的两个元素x、y，假如有x R y 或y R x，如此x和y被称作是可比的，否如此被称为不可比的。集合X上的一个偏序关系R，如果使得X中的任意一对元素都是可比的，那么该偏序R就是一个全序。例如，正整数集上的小于等于关系就是一个全序。令a和b是偏序集(X, )中的两个元素。假如有a b，且X中不存在另一个元素c，使得a c b，那么就称a被b覆盖或b覆盖a，记作a cb。假如X是一个有限集，由偏序集的传递性易知，任一个偏序关系都可以用多个覆盖关系表示出来，也就是
8、说可以用覆盖关系有效的表示偏序关系。有限偏序集(X, )的图表示也就是哈斯图是用平面上的点描述的。偏序集中的元素用平面上的点来表示。假如有a b，那么a在平面上的位置严格说是坐标平面中的纵坐标就应当低于b在平面上的位置。假如a cb，那么a和b之间连一条边。也可以用有向图来表示偏序关系，图中的每个结点对应偏序集中的每个元素。假如偏序集中的两个元素有a cb，那么对应到图中的两个结点a和b，就有一条从b到a的有向边(b, a)。因此可以看出原图事实上是一个偏序集的图表示。链：链是E的一个子集C，在偏序关系下，它的每一对元素都是可比的，即C是E的一个全序子集。反链或称杂置：顾名思义，它和链的定义恰
9、恰相反。反链是E的一个子集A，在偏序关系下，它的每一对元素都是不可比的。链和反链的大小是指集合中元素的个数。2.2.2 构筑原问题的偏序集模型有了上文有关偏序集的概念，不难搭建出原问题的偏序集模型：令原图表示的偏序集为(X, )，而新构造的偏序集为(E, )。如此集合E满足，即E中的元素全部是图中的有向边。令a、b为E中的两个元素，设。当且仅当时，有ab，即存在一条从有向边a到有向边b的路径。当且仅当va = ub时，有acb。原问题可以重新用偏序集语言表述为：将偏序集E, 划分成最少的链，使得这些链的并集包含所有E中的元素。直接计算链的个数似乎并不容易，好在有Dilworth定理揭示了链与反
10、链的关系，从而使得问题的目标进一步转化。定理2.1 : Dilworth定理 令E, 是一个有限偏序集，并令m是E中最大反链的大小，M是将E划分成最少的链的个数。在E中，有m = M。证明过程请参见附录。根据Dilworth定理，问题转化成求E中最长的反链的大小。也就是要求在原图中选尽量多的边，同时保证选出的边是互不可达的即在(E, )中不可比。如何求解最长的反链呢？事实上，这和原题给出的平面图有很大关系，接下来，返回到原图上继续讨论。2.2.3 从偏序集模型回归到原题由于原题给出的图是平面图，而且图中顶点也是从左到右给出的，那么对于反链中的所有边都能按照从左到右的顺序排列好。如果用一条线将最
11、长反链所对应的边从左到右连起来如图2-2所示，那么这条线不会与平面图中的其它边相交。更加准确地说：将最长反链所对应的边从左到右排列好，相邻的两条边一定是在同一个域闭曲面中。所谓的域，是由从一个点到另一个点一个是极高点，一个是极低点的两条不同路径两条路径没有公共边围成的一个曲面，在这个曲面里没有其他的点和边如图2-3所示，记作F。在围成域F的两条路径中，左边的那条路径定义为F的左边界，右边的那条路径定义为F的右边界。图2-2123459681013121171415极高点图2-3极低点关于定理2.2的简略证明请参见附录。受定理2.2的启发，我们可以用递推的方法求得图中最长反链的长度。设f(x)表
12、示在边x左边的平面区域中以x结尾的最长反链的长度。设x在某个域F的右边界上，有。因为根据定理2.2，假如x在某个最长反链中，那么反链中和x相邻且在x左边的边，只有可能在域F的左边界上。得到这个递推式后，只需要按照从左到右从上到下把每一个域求出进展递推即可。2.2.4 相应的算法设计可以用DFS深度优先遍历实现平面图中域的寻找。DFS中需要记录两个信息：结点的颜色和扩展它的父结点。每个结点的颜色用Cu来记录。Cu有三种状态：白色表示结点u尚未被遍历，一开始所有结点的颜色都是白色；灰色表示结点u已经被遍历，但是它尚未检查完毕，也就是说它还有后继结点没有扩展；黑色表示结点u不但被遍历且被检查完毕。扩
13、展它的父结点用pre记录。算法的大致框架如下：DFS结点ubeginCu 灰色while v是u后继结点 do 按照从左到右的顺序扩展u的后继结点vif Cv 是白色then beginprev u DFS(v)end else beginvl vvh vwhile Cvh 是黑色 do vh prevh (是黑色，说明是域的边界上的结点；灰色就是极高点)递推求出右边界的f(x) (pre回溯的边是左边界，是右边界)prev u endCu 黑色end计算上述算法的复杂度：a.对每一个点进展DFS遍历，复杂度为O(|E|)；b.回溯寻找每个域边界上的边，并且进展递推求解。由于是平面图，每条边最
14、多属于两个不同域的边界，因此这一步的复杂度为O(|E|+|F|)。因为原题给出的图是平面图，根据欧拉定理，边数|E|和域数(或者说面数)|F|都是O(n)级别的。因此总的时间复杂度为O(n)。2.3 小结方法一利用网络流模型直接的表现了原题的网络有向无环特性，解法具有一般性，但是没有充分的表现出原题的平面图性质。而方法二很好的利用偏序集模型实现了问题目标的转变，从原来的网络流问题回归到问题本身的平面图上，完整的揭示了问题的本质。正是由于回归到问题的本质，后面才能用DFS充分挖掘平面图的性质，得到最优复杂度的算法。从上述两种方法的比拟可以看出，两种不同的图论模型导致了两种算法在时间复杂度上的较大
15、差异，可见选择模型的重要性。正所谓“磨刀不误砍柴功，在设计算法之前，选择一个正确的图论模型往往能够起到事半功倍的效果，不仅能降低算法设计的难度，还使设计出的算法简单高效。在为实际问题选择适宜的图论模型的时候，不能仅仅局限于问题外表所表现的某些性质，只根据自有的经验去解题，否如此会落入俗套，得不到效率最高的算法。新题新作，应该创新思路，深入分析问题的各种性质，将这些性质结合在一起，从而寻找到最能表现问题本质的图论模型。很多时候，最终算法并不是基于所选图论模型来设计的，就如方法二，偏序集并没有出现在DFS中，但一旦想到偏序集，问题可以说就解决了一半。图论模型更多的是思考的一种过渡，使思路变得清晰，就像一座灯塔，指引你到成功的彼岸。三、充分挖掘和利用模型的性质上一节讲述了选择适宜模型的重要性和搭建图论模型的方法。建立模型仿佛是为算法设计搭建一个平台，接下来的工作是在这个平台上充分挖掘和利用原题的性质，设计一个解决问题的好算法。如何挖掘和利用模型的性质呢？下面同样用一个具体实例来说明。例二：爱丽丝和鲍勃
