算法合集之《浅谈图论模型的建立与应用》.pdf

《算法合集之《浅谈图论模型的建立与应用》.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、，且包含空地的区域称作“块”。显然，在每个块之中，最多只能放一个机器人。我们把这些块编上号，如下图所示：112334425第2页共9页IOI2004国家集训队论文黄河源把横向块作为X部的顶点，竖向块作为Y部的顶点，如果两个块之间有公共的空地，就在它们之间连边。这样，我们得到了下面的二部图：123451234由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。这是图论中的经典问题，可以用匈牙利算法解决。[小结]比较上面的两个模型，第一个过于简单，没有认清问题的本质；第二个则充分抓住了问题的内在联系，巧妙地建立了二部图模型。为什么会产生这样截然

5、不同的结果呢？其一是由于对问题分析的角度不同，第一种模型以空地为点，第二种模型以空地为边；其二是由于第一种模型对原型中信息的选取不足，所建立的模型没有保留原型中重要的性质，而第二种模型则保留了原型中“棋盘”这个重要的性质。由此可见，对信息的选取，是图论建模中至关重要的一步。〖例题2〗出纳员的雇佣（ACMTehran2000）[问题描述]Tehran的一家每天24小时营业的超市，需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决他的问题——超市在每天的不同时段需要不同数目的出纳员（例如：午夜时只需一小批，而下午则需要很多）来为顾客提供优质服务。他希望雇佣最少数目的出纳员。经理

6、已经提供你一天的每一小时需要出纳员的最少数量——R0,R1,...,R23。R0表示从午夜到上午1：00需要出纳员的最少数目，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更多的出纳员在

7、工作。输入第3页共9页IOI2004国家集训队论文黄河源输入文件的第一行为测试点个数（<=20）。每组测试数据的第一行为24个整数表示R0，R1，...，R23（RI≤1000）。接下来一行是N，表示申请者数目（0≤N≤1000），接下来每行包含一个整数tI（0≤tI≤23）。两组测试数据之间没有空行。输出对于每个测试点，输出只有一行，包含一个整数，表示需要出纳员的最少数目。如果无解，你应当输出“NoSolution”。[分析]初看本题，很容易使人往贪心、动态规划或网络流这些方面思考，但这些