ACM算法浅谈图论模型的建立与应用PPT课件.ppt

该【ACM算法浅谈图论模型的建立与应用PPT课件 】是由【xinyala】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【ACM算法浅谈图论模型的建立与应用PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。浅谈图论模型的建立与应用广东省中山市第一中学黄源河*中山一中黄源河*引言图论是数学的一个有趣的分支。图论的建模,就是要抓住问题的本质,把问题抽象为点、边、权的关系。许多看似无从入手的问题,通过图论建模,往往能转化为我们熟悉的经典问题。*中山一中黄源河*例题1PlacetheRobots(ZOJ)问题描述有一个N*M(N,M<=50)的棋盘,棋盘的每一格是三种类型之一:空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人,若它们之间没有墙,则它们可以互相攻击。问给定的棋盘,最多可以放置多少个机器人,使它们不能互相攻击。WallGrassEmpty*中山一中黄源河*例题1PlacetheRobots(ZOJ)模型一5467832112346578于是,问题转化为求图的最大独立集问题。在问题的原型中,草地,墙这些信息不是我们所关心的,我们关心的只是空地和空地之间的联系。因此,我们很自然想到了下面这种简单的模型:以空地为顶点,有冲突的空地间连边,我们可以得到右边的这个图:*中山一中黄源河*例题1PlacetheRobots(ZOJ)模型一5467832112346578在问题的原型中,草地,墙这些信息不是我们所关心的,我们关心的只是空地和空地之间的联系。因此,我们很自然想到了下面这种简单的模型:以空地为顶点,有冲突的空地间连边,我们可以得到右边的这个图:这是NP问题!*中山一中黄源河*我们将每一行,每一列被墙隔开,且包含空地的连续区域称作“块”。显然,在一个块之中,最多只能放一个机器人。我们把这些块编上号。同样,把竖直方向的块也编上号。例题1PlacetheRobots(ZOJ)模型二123451234*中山一中黄源河*例题1PlacetheRobots(ZOJ)模型二123451234把每个横向块看作X部的点,竖向块看作Y部的点,若两个块有公共的空地,则在它们之间连边。于是,问题转化成这样的一个二部图:112233445*中山一中黄源河*由于每条边表示一个空地,有冲突的空地之间必有公共顶点,所以问题转化为二部图的最大匹配问题。例题1PlacetheRobots(ZOJ)模型二123412354112233445*中山一中黄源河*比较前面的两个模型:模型一过于简单,没有给问题的求解带来任何便利;模型二则充分抓住了问题的内在联系,巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢?其一是由于对问题分析的角度不同:模型一以空地为点,模型二以空地为边;其二是由于对原型中要素的选取有差异:模型一对要素的选取不充分,模型二则保留了原型中“棋盘”这个重要的性质。由此可见,对要素的选取,是图论建模中至关重要的一步。例题1PlacetheRobots(ZOJ)小结*中山一中黄源河*例题2出纳员的雇佣(ACMTehran2000)问题描述有一家24小时营业的超市,需要雇佣一批出纳员。一天中每个小时需要出纳员的最少数量为R0,R1,R2,...,R23。有N个人申请这项工作,每个申请者,从一个特定时刻开始连续工作恰好8个小时,设Wi(i=0...23)表示从时刻i开始工作的申请者的人数(∑Wi=N<=1000)。你的任务是计算出需要雇佣出纳员的最少数目,满足在每一时刻i,至少有Ri名出纳员在工作。*中山一中黄源河*