• / 12
  • 下载费用:10 金币  

图论中的追捕问题——警察抓小偷.pdf

关 键 词:
图论中的追捕问题——警察抓小偷.pdf
资源描述:
研究生图论课程作业 (论文) - 1 -重庆邮电大学图论论文题目: 图论中的游戏 —— 警察抓小偷学 院 名 称 : 通信与信息 工程 学院学 生 姓 名 : 周 易 德专 业 : 信息与通信工程班 级 : 通信 14 班学 号 : S160101195联 系 方 式 : goliathchoe@foxmail.com指 导 教 师 : 李 红 刚2016 年 12 月研究生图论课程作业 (论文) - 2 -摘 要本文简要地介绍了一种简单的图论游戏 ——警察抓小偷( a game of cops and robbers)。这是一个在图上进行的 点 追捕游戏( vertex-pursuit game), 通常由一个警察或多个警察 和一个小偷组成,两名 队 玩家在一个有限无向 简单 图上进行游戏,且交替沿着边进行移动。当 任意 警察与小偷重合时,则代表警察抓住了小偷;反之, 如果小偷一直不能被捉住,则小偷赢。关于这个游戏, 虽然看似简单并 已经 被研究了三十多年,但仍然有一些未能解决的问题和未能证明的假设。本 文旨在介绍这个游戏规则,并从零开始 介绍 一些由此引发的简单定理 ,并在力所能及的范围内尝试证明它们。【关键词】 Pursuit-evasion game on graphs; Cops and Robbers; Vertex-pursuit Game; Meyniels ConjectureABSTRACTThis article briefly introduces a simple game on graphs which called the police catch the thief, or a game of cops and robbers. This is a Pursuit Game, usually including at least one policeman and only one thief, who play on a finite undirected graph and move along the edge alternately. When any of policemen and the thief coincide with each other, it means that the policeman seized the thief. On the other hand, if the thief has been unable to be caught, the thief is considered to win. About this game, although seemingly simple and has been studied for over thirty years, there are still some unsolved problems and unproven assumptions. The purpose of this article is to introduce the rules of the game and introduce some of the simple theorems that result from them, and try to prove them within my limits.【 Key words】 Pursuit-evasion game on graphs; Cops and Robbers; Vertex-pursuit Game; Meyniels Conjecture研究生图论课程作业 (论文) - 3 -1. 游戏 简介警察抓小偷( A game of cops and robbers 或 vertex-pursuit game)最早是由 R. Nowakowski 和 P. Winkler 于 1983 年 ,在 [1]中提出的。 游戏由两 队人组 成警察和小偷组成。玩家在一个有限的无向 简单 连通图 G 中进行, 每个 小偷和警察能交替地沿着边在相邻的点之间移动 或者选择停留在原地 。警察可能不止 一个,他们的目的抓住小偷,也就是通过不断移动与小偷所在点重合。而小偷的目的当然是永远不要被警察抓住。这样一个简答的游戏却引出了一串复杂的理论。游戏开始时,先由每个警察选一个点作为初始位置 ;之后再由小偷选择初始位置。之 后,每个回合小偷和警察都只能移动 “一步 ”,即只能从自己所在点前往这个点的相邻定点。为了化简问题的难度,我们认为小偷和警察的位置 都不是秘密的,即所有人都知道其他人的位置。在确定的有限无向简单图上的游戏流程如下
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:图论中的追捕问题——警察抓小偷.pdf
链接地址:https://www.weizhuannet.com/p-9475389.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开