论文国家队黄源河

《论文国家队黄源河》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

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

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

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

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

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