文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 算法合集之《浅谈图论模型的建立与应用》
侵权投诉

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

【关键字】 图论模型、建立、转化 【摘要】 在近几年的信息学竞赛中,图论题目层出不穷。图论作为 一个新生的数学分支,相比其他数学分支来说,具有许多自有 的特性。利用图论解题,通常具有高效、简洁的便利。有了这 门工具,并不意味就能很好地解决问题,还在于我们能否熟练 地识别与建立一系列的图论模型。本文通过一些实例,简单地 介绍一下图论建模的方法。

例题分析

〖例题1〗 (ZOJ)

[问题大意]

有一个N*M(N,M<=50)的棋盘,棋盘的每一

格是三种类型之一:空地、草地、墙。机器人

只能放在空地上。在同一行或同一列的两个机

器人,若它们之间没有墙,则它们可以互相攻

击。问给定的棋盘,最多可以放置多少个机器

人,使它们不能互相攻击。

[分析]

在问题的原型中,草地,墙这些信息不是我们所关心的,我们关心的只是空地和空地之间的联系。因此,我们很自然想到了下面这种简单的模型:

以空地为顶点,有冲突的空地间连边,我们可以得到下面的这个图:

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

4那么,问题转化为求图的最大独立集问题。众所周知,这是NP-完全问题。看来,建立这样的模型,没有给问题的求解带来任何便利,我们必须建立一个行之有效的新模型。

我们将每一行,每一列被墙隔开,且包含空地的区域称作“块”。显然,在每个块之中,最多只能放一个机器人。我们把这些块编上号,如下图所示

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

:

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

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

上一页第2页

你可能喜欢

  • 图论算法
  • 算法竞赛
  • 图论及其应用
  • 遗传算法应用
  • 历年数学建模优秀论文
  • 图论论文

热门文档

相关文档

  • 算法合集之《图论模型的建立与转化》

    算法合集之《浅谈图论模型... 27页 免费 图论模型的建立及转化方法 2页 5...第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方 法:拆分转化和...

  • 算法合集之《图论模型的建立与转化》

    算法合集之《图论模型的建立与转化》_天文/地理_自然科学_专业资料。算法合集...第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方 法:拆分转化和...

  • 图论模型的建立

    图论模型的建立与应用 37页 免费 算法合集之《图论模型的建... 12页 免费 算法合集之《浅谈图论模型... 9页 免费 图论模型的构建 41页 免费 算法合集之《...

  • 图论模型的建立与转化

    图论模型的建立与应用 37页 免费 算法合集之《浅谈图论模型... 9页 免费 ...建立图论模型的目的和建立其它的数学模型一样,都是为了简化问题,突出要点,以 便...

  • 算法合集之《图论的基本思想及方法》

    算法合集之《浅谈图论模型... 27页 免费 图论的基本算法及应用 60页 2财富...图论模型为 平台挖掘问题 的性质 结语图论基本思想的精华 “模型 ” 建立模型 ...

  • 算法合集之《数学模型的建立和选择》

    算法合集之《数学模型的建立和选择》_IT/计算机_...我们就要想方设法将信 息原型对应到图论中的模型...信息原型的独特属性,并且 有效地在算法中加以应用. ...

  • 算法合集之《浅谈网络流算法的应用》

    算法合集之《浅谈网络流算法的应用》_IT/计算机_专业资料。算法合集之《浅谈...浅谈网络流算法的应用缺点:相对于其它图论算法来说,它的模型更加复杂,编程复杂度...

  • 算法合集之《图论的基本思想及方法》

    建立模型仿佛 图论的基本思想及方法 任恺 是为算法设计搭建一个平台, 接下来的... 算法合集之《浅谈图论模... 9页 免费 算法合集之《浅谈图论模... 27页 ...

  • 图论在给水调度模型中的应用

    图论模型的建立与应用 37页 免费 算法合集之《浅谈图论模型... 9页 免费喜欢此文档的还喜欢 图论模型在实际中的应用 66页 免费 图论的应用 13页 免费 图论 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email