论文--浅谈图论模型的建立与应用

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

1、浅谈图论模型的建立与应用【关键字】图论模型、建立、转化【摘要】在近几年的信息学竞赛中，图论题目层出不穷。图论作为一个新生的数学分支，相比其他数学分支来说，具有许多自有的特性。利用图论解题，通常具有高效、简洁的便利。有了这门工具，并不意味就能很好地解决问题，还在于我们能否熟练地识别与建立一系列的图论模型。本文通过一些实例，简单地介绍一下图论建模的方法。【正文】引言应用数学知识解题时，首先要通过对实际问题的分析，研究组建用以描述这个问题的数学模型。使用数学的理论和方法对模型进行分析从而得到结果，再返回去解决现实的实际问题。图论模型是一类特殊的数学模型，建立图论

2、模型，就是要从问题的原型中，抽取对我们有用的信息和要素，把问题抽象为点、边、权的关系。经过图论建模之后，杂乱无章的信息变得有规可寻，要素的内在联系体现在了点、边、权的关系。有不少经典的图论模型可以直接用特定的算法解决，一些复杂的问题，只要能认清问题的本质，把握问题的关键，建立合适的图论模型，往往能转化为我们熟悉的经典问题。本文要写的，正是我在图论建模方面的一点心得与认识。例题分析〖例题1〗PlacetheRobots(ZOJ)[问题大意]有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列

3、的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。[分析]在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到下面的这个图：那么，问题转化为求图的最大独立集问题。众所周知，这是NP-完全问题。看来，建立这样的模型，没有给问题的求解带来任何便利，我们必须建立一个行之有效的新模型。我们将每一行，每一列被墙隔开，且包含空地的区域称作“块”。显然，在每个块之中，最多只能放一个机器人。

4、我们把这些块编上号，如下图所示：把横向块作为X部的顶点，竖向块作为Y部的顶点，如果两个块之间有公共的空地，就在它们之间连边。这样，我们得到了下面的二部图：由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。这是图论中的经典问题，可以用匈牙利算法解决。[小结]比较上面的两个模型，第一个过于简单，没有认清问题的本质；第二个则充分抓住了问题的内在联系，巧妙地建立了二部图模型。为什么会产生这样截然不同的结果呢？其一是由于对问题分析的角度不同，第一种模型以空地为点，第二种模型以空地为边；其二是由于第一种模型对原型中信息的选取不足

5、，所建立的模型没有保留原型中重要的性质，而第二种模型则保留了原型中“棋盘”这个重要的性质。由此可见，对信息的选取，是图论建模中至关重要的一步。〖例题2〗出纳员的雇佣（ACMTehran2000）[问题描述]Tehran的一家每天24小时营业的超市，需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决他的问题——超市在每天的不同时段需要不同数目的出纳员（例如：午夜时只需一小批，而下午则需要很多）来为顾客提供优质服务。他希望雇佣最少数目的出纳员。经理已经提供你一天的每一小时需要出纳员的最少数量——R0,R1,...,R23。R0表示从午夜到上午1：00需要出

6、纳员的最少数目，R1表示上午1：00到2：00之间需要的，等等。每一天，这些数据都是相同的。有N人申请这项工作，每个申请者I在没24小时中，从一个特定的时刻开始连续工作恰好8小时，定义tI（0≤tI≤23）为上面提到的开始时刻。也就是说，如果第I个申请者被录取，他（她）将从tI时刻开始连续工作8小时。你将编写一个程序，输入RI（I=0..23）和tI（I=1..N），它们都是非负整数，计算为满足上述限制需要雇佣的最少出纳员数目。在每一时刻可以有比对应的RI更多的出纳员在工作。输入输入文件的第一行为测试点个数（<=20）。每组测试数据的第一行为24个整数表示

7、R0，R1，...，R23（RI≤1000）。接下来一行是N，表示申请者数目（0≤N≤1000），接下来每行包含一个整数tI（0≤tI≤23）。两组测试数据之间没有空行。输出对于每个测试点，输出只有一行，包含一个整数，表示需要出纳员的最少数目。如果无解，你应当输出“NoSolution”。[分析]初看本题，很容易使人往贪心、动态规划或网络流这些方面思考，但这些算法对于本题都无能为力。由于本题的约束条件很多，为了理清思路，我们先把题目中的约束条件用数学语言表达出来。设S[i]表示0～i时刻雇佣出纳员的总数，Wi表示在时刻i开始工作的申请者的人数。那么我们可以

8、将题目中的约束条件转化为下面的不等式组：这样的不等式组，不禁使我们