acm算法 浅谈图论模型的建立与应用

《acm算法 浅谈图论模型的建立与应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈图论模型的建立与应用xxx省xxx市第一中学xxx引言图论是数学的一个有趣的分支。图论的建模，就是要抓住问题的本质，把问题抽象为点、边、权的关系。许多看似无从入手的问题，通过图论建模，往往能转化为我们熟悉的经典问题。例题1PlacetheRobots（ZOJ）问题描述有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。WallG

2、rassEmpty例题1PlacetheRobots（ZOJ）模型一5467832112346578于是，问题转化为求图的最大独立集问题。在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：例题1PlacetheRobots（ZOJ）模型一5467832112346578在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了

3、下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：这是NP问题！我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。同样，把竖直方向的块也编上号。例题1PlacetheRobots（ZOJ）模型二123451234例题1PlacetheRobots（ZOJ）模型二123451234把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二部图：112233

4、445由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。例题1PlacetheRobots（ZOJ）模型二123412354112233445比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由

5、此可见，对要素的选取，是图论建模中至关重要的一步。例题1PlacetheRobots（ZOJ）小结例题2出纳员的雇佣（ACMTehran2000）问题描述有一家24小时营业的超市，需要雇佣一批出纳员。一天中每个小时需要出纳员的最少数量为R0,R1,R2,...,R23。有N个人申请这项工作，每个申请者，从一个特定时刻开始连续工作恰好8个小时，设Wi（i=0...23）表示从时刻i开始工作的申请者的人数（∑Wi=N<=1000）。你的任务是计算出需要雇佣出纳员的最少数目，满足在每一时刻i，至少有Ri名出纳员在工作

6、。例题2出纳员的雇佣（ACMTehran2000）分析初看本题，很容易使人往贪心、动态规划或网络流这些方面思考。然而，对于本题，这些算法都无能为力。由于本题的约束条件很多，为了理清思路，我们先把题目中的约束条件用数学语言表达出来。设S[i]表示0～i时刻雇佣出纳员的总数，那么我们可以将题目中的约束条件转化为下面的不等式组：0≤S[i]-S[i-1]≤Wi(0≤i≤23)S[i]-S[i-8]≥Ri(8≤i≤23)S[23]+S[i]-S[i+16]≥Ri(0≤i≤7)例题2出纳员的雇佣（ACMTehran2

7、000）分析这样的不等式组，不禁使我们想到了差分约束系统。对于每个不等式S[i]-S[j]≤K，从顶点ｊ向顶点ｉ引一条权值为K的有向边。我们要求S[23]的最小值，就是要求顶点0到顶点23的最短路。注意上面第三条不等式：它包含三个未知数，无法在图中表示为边的关系。0≤S[i]-S[i-1]≤Wi(0≤i≤23)S[i]-S[i-8]≥Ri(8≤i≤23)S[23]+S[i]-S[i+16]≥Ri(0≤i≤7)怎么办例题2出纳员的雇佣（ACMTehran2000）分析退一步考虑：如果S[23]已经确定了，那么上

8、面的不等式组可以完全转化为一个有向图，顶点0到顶点ｉ的最短路，就是S[i]的解。而当图中存在负权回路时，不等式组无解。至于S[23]，我们可以用二分法枚举，逐步缩小范围，用迭代法判断是否存在负权回路（判定可行性），最终求得S[23]的最小值。时间复杂度为O(243*log2N)。0≤S[i]-S[i-1]≤Wi(0≤i≤23)S[i]-S[i-8]≥Ri(8≤i≤23)S[23]+S