“警察抓小偷”游戏的传统的研究对象是图 G 的最小警察数目, 即保证玩家 A 赢得 游戏所需要的最小警察数目 c(G). 注意到有一类警察数 c(G) = 1 的图 G, 结合实际生活 背景, 警察的数量通常可能会大于抓捕小偷所需的最小警察数目, 此时警察的目标只是 在最短的时间内抓捕小偷. 在资源有限的现实世界网络中, 抓获小偷所需的时间也非常 重要, 于是在游戏中开始关注警察抓捕到小偷所需要最小步数. 在 c(G) = k 的图 G 中, 本文选择改变经典的游戏规则, 限制每轮游戏只允许一个警察移动. 本文主要研究了在 最小警察数目 c(G) = 1 的图上进行游戏时, 抓捕到小偷所需要最小步数并研究对应图的 结构. 进一步对 c(G) = k 的图 G, 计算抓捕到小偷所需要最小步数较为困难, 因此选择 结合算法给出警察的移动策略及对应的最小步数.

The traditional research object of the game of Cops and Robber is the minimum number of cops in graph G, which is the minimum number c(G) of cops required to ensure that player Awins the game. Note that there is a type of graph G where the number of cops is c(G) = 1. Considering the actual life background, the number of cops may usually be greater than the minimum number of cops required to catch a robber. At this point, the goal of the cops is only to catch the robber as soon as possible. In the graph G with c(G) = k, this article chooses to change the classic game rules and restrict only one cop to move in each round of the game. This article mainly studies the capture time of the cops, that is the minimum number of steps required to catch the robber when playing games on a graph with a minimum number of cop , and studied the structure of the corresponding graph. Further, for the graph G with c(G) = k, it is difficult to calculate the capture time directly. Therefore, we choose to use the algorithm to provide the cops’ movement strategy and corresponding capture time.