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

《图论中的追捕问题——警察抓小偷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、研究生图论课程作业（论文）重庆邮电大学图论论文题目：图论中的游戏——警察抓小偷学院名称：通信与信息工程学院学生姓名：周易德专业：信息与通信工程班级：通信14班学号：S160101195联系方式：goliathchoe@foxmail.com指导教师：李红刚2016年12月-1-研究生图论课程作业（论文）摘要本文简要地介绍了一种简单的图论游戏——警察抓小偷（agameofcopsandrobbers）。这是一个在图上进行的点追捕游戏（vertex-pursuitgame），通常由一个警察或多个警察和一个小偷组成，两名队玩家在一个有限无向简单图上进行游戏，且交替沿着边进行

2、移动。当任意警察与小偷重合时，则代表警察抓住了小偷；反之，如果小偷一直不能被捉住，则小偷赢。关于这个游戏，虽然看似简单并已经被研究了三十多年，但仍然有一些未能解决的问题和未能证明的假设。本文旨在介绍这个游戏规则，并从零开始介绍一些由此引发的简单定理，并在力所能及的范围内尝试证明它们。【关键词】Pursuit-evasiongameongraphs;CopsandRobbers;Vertex-pursuitGame;MeynielsConjectureABSTRACTThisarticlebrieflyintroducesasimplegameongraphswhichca

3、lledthepolicecatchthethief,oragameofcopsandrobbers.ThisisaPursuitGame,usuallyincludingatleastonepolicemanandonlyonethief,whoplayonafiniteundirectedgraphandmovealongtheedgealternately.Whenanyofpolicemenandthethiefcoincidewitheachother,itmeansthatthepolicemanseizedthethief.Ontheotherhand,if

4、thethiefhasbeenunabletobecaught,thethiefisconsideredtowin.Aboutthisgame,althoughseeminglysimpleandhasbeenstudiedforoverthirtyyears,therearestillsomeunsolvedproblemsandunprovenassumptions.Thepurposeofthisarticleistointroducetherulesofthegameandintroducesomeofthesimpletheoremsthatresultfrom

5、them,andtrytoprovethemwithinmylimits.【Keywords】Pursuit-evasiongameongraphs;CopsandRobbers;Vertex-pursuitGame;MeynielsConjecture-2-研究生图论课程作业（论文）1.游戏简介警察抓小偷（Agameofcopsandrobbers或vertex-pursuitgame）最早是由R.Nowakowski和P.Winkler于1983年,在[1]中提出的。游戏由两队人组成警察和小偷组成。玩家在一个有限的无向简单连通图G中进行，每个小偷和警察能交替地沿着边

6、在相邻的点之间移动或者选择停留在原地。警察可能不止一个，他们的目的抓住小偷，也就是通过不断移动与小偷所在点重合。而小偷的目的当然是永远不要被警察抓住。这样一个简答的游戏却引出了一串复杂的理论。游戏开始时，先由每个警察选一个点作为初始位置；之后再由小偷选择初始位置。之后，每个回合小偷和警察都只能移动“一步”，即只能从自己所在点前往这个点的相邻定点。为了化简问题的难度，我们认为小偷和警察的位置都不是秘密的，即所有人都知道其他人的位置。在确定的有限无向简单图上的游戏流程如下：1.警察选择初始位置，位置可以重叠。2.小偷选择初始位置，令t=1。3.第t回合开始，每个警察可以选择移

7、动至邻居点或者停留。每个警察都只能移动一步。4.如果警察到达了小偷所在点则游戏结束，否则继续。5.小偷可以选择移动至邻居点或者停留。小偷只能移动一步。6.t=t+1,返回3注意我们定义的游戏是警察先选择初始位置，小偷后选择初始位置。每回合开始也是警察先移动。后文中提到“回合开始时”就是指轮到警察选择前的时刻。游戏过程中，小偷和警察知道关于游戏的所有信息，包括：(1)图G的连接情况；（2）所有警察和小偷的。这种所有玩家拥有关于游戏的所有信息在博弈论中被称为完全信息（completeinformation）。在[2]中，Isler