k步循环图上的追逃博弈策略研究一—k+1名警察的必胜策略

Pursuit Strategies on k-Step Circulant Graph )A Winning Strategy for k + 1 Cops

摘要: 警察与强盗问题(Cops and Robbers Game)是图论与组合博弈论中的经典研究课题，其中图的警察数描述了保证警察最终能够抓获强盗所需的最少警察数量。已有研究表明，对于由k个生成元构造的k步循环图，其警察数不超过k＋1。然而，相关工作主要从结构性质出发给出了存在性证明，而未给出具体的追捕策略。本文在已有结果的基础上，给出一种新的构造性证明方法。通过引入警察与强盗之间的距离表示，将顶点之间的位置关系表示为生成元的线性组合，并设计k个警察的协同策略，使其在有限步后能够形成特定的距离组合结构。在该结构下，强盗的可行动作被完全限制，只能保持静止，从而由第k＋1个自由警察完成最终捕获。该方法从策略构造的角度解释了k＋1名警察能够保证抓获强盗的原因，为理解循环图上的追逃博弈提供了一种新的分析思路。

Abstract: The cops and robbers game is a classical topic in graph theory and combinatorial game theory, where the cop number of a graph represents the minimum number of cops required to guarantee the capture of a robber. It is known that for k-step circulant graphs generated by k elements, the cop number is at most k + 1. However, existing results mainly provide existential proofs based on structural properties of the graph and do not explicitly describe a concrete capture strategy. In this paper, we present a constructive proof of this result by developing an explicit pursuit strategy. By introducing a distance representation between the cops and the robber, the positional relations among vertices are expressed as linear combinations of the generating steps. Based on this representation, we design a cooperative strategy for k cops such that after finitely many moves their distances to the robber form a specific configuration. Under this configuration, all possible movements of the robber are blocked, forcing the robber to remain stationary, and the (k+1)-th free cop can eventually capture the robber. This approach provides a strategy-based explanation for why k+1 cops suffice on k-step circulant graphs and offers a new perspective for studying pursuit-evasion games on circulant graphs.