论文标题
警察和有见地的强盗
Cops and an Insightful Robber
论文作者
论文摘要
警察和强盗的“作弊机器人”版本是在有限的，简单，连接的图表上播放的。玩家在同一时期移动。但是，在移动之前，机器人观察了警察在哪个顶点移动的位置，并且足够快，可以在时间段内完成移动。警察还知道机器人将使用此信息。捕获机器人所需的警察比俘虏强盗需要更多的警察。实际上，最低度是捕获机器人所需的警察数量的下限。只有在树上是一名警察保证捕获机器人，尽管两个警察足以在外平面图上同时捕获强盗和机器人。在涉及缩回的图表中，我们展示了如何修改针对强盗的COP策略以捕获机器人。这种方法给出了超级管的确切数字，总体上为$ k $二维的网格提供了数字。
The 'Cheating Robot' version of Cops and Robbers is played on a finite, simple, connected graph. The players move in the same time period. However, before moving, the robot observes to which vertices the cops are moving and it is fast enough to complete its move in the time period. The cops also know that the robot will use this information. More cops are required to capture a robot than to capture a robber. Indeed, the minimum degree is a lower bound on the number of cops required to capture a robot. Only on a tree is one cop guaranteed to capture a robot, although two cops are sufficient to capture both a robber and a robot on outerplanar graphs. In graphs where retracts are involved, we show how cop strategies against a robber can be modified to capture a robot. This approach gives exact numbers for hypercubes, and $k$-dimensional grids in general.
