强积图上的警察与强盗游戏两个变体

《Discrete Applied Mathematics》：Two variants of Cops and Robbers on strong product graphs

　　

摘要

"Cops and Robbers"（警察与小偷）是一种在图上进行的轮流策略博弈，其中一队警察试图抓捕一个小偷。图的警察数是指抓住小偷所需的最少警察数量。本文研究该博弈的两个变体：包围型警察与小偷博弈，以及警察与洞察型小偷博弈。Burgess等人（Discrete Appl. Math. 285 (2020), 552–566）建立了完全二部图强积$K_{m,n}\boxtimes K_{m,n}$的包围警察数的下界。我们填补了这一差距，确定了所有正整数$m$和$n$的精确值。此外，我们还获得了在强积$P_m\boxtimes C_n$和$C_m\boxtimes C_n$上抓捕洞察型小偷所需最少警察数量的紧致结果。我们的结果推广了Huggan和Nowakowski（Discrete Appl. Math. 295 (2021), 112–119）此前针对$P_m\boxtimes P_n$所得到的结论。

**引言**

"Cops and Robbers"博弈由Nowakowski和Winkler[10]以及Quillot[11]独立提出，两者均设定为单个警察的情形。Aigner和Fromme[1]将该博弈推广到任意数量的警察，并引入了警察数的概念。Fomin等人[6]证明了计算抓住小偷所需的最少警察数量是NP难的。该博弈在人工智能、图搜索和追捕-逃逸博弈开发等领域有应用和联系[2], [8], [9], [12]。关于"Cops and Robbers"博弈的更多背景知识，请参考Bonato和Nowakowski的专著[3], [4]。

已有许多该博弈的变体被研究。本文关注其中两个：警察包围小偷博弈以及警察与洞察型小偷博弈。Burgess等人[5]获得了完全二部图强积的包围警察数的下界；我们通过确定精确值来改进了他们的结果。Huggan和Nowakowski[7]确定了在路径强积上抓捕洞察型小偷所需的最少警察数，我们通过确定环强积的相应值来扩展了他们的工作。

**警察包围小偷博弈**

警察包围小偷博弈是经典"Cops and Robbers"博弈的变体。它在有限、简单、连通的图上进行。一个玩家控制$k$个警察，另一个玩家控制一个小偷。游戏开始时，警察首先选择初始位置；多个警察可以占据同一顶点。然后小偷选择一个未被警察占据的顶点作为其初始位置。玩家轮流行动。在每一回合中，每个警察和小偷都可以移动到相邻顶点或停留在当前顶点。小偷不允许移动到或被警察占据的顶点上停留。特别是，如果在某个时刻一个警察移动到了小偷所在的顶点，则小偷必须移动到一个没有被警察占据的相邻顶点。

与经典博弈不同，警察并不是通过占据与小偷相同的顶点来获胜。相反，如果某个时刻小偷所在顶点的所有邻居都被警察占据，小偷没有任何合法移动，即被包围，则警察获胜。如果小偷能无限期地避免被包围，则小偷获胜。博弈在完全信息下进行。对于图$G$，我们用$s(G)$表示$G$的包围警察数，即在$G$上包围小偷所需的最少警察数量。

我们使用强积的标准定义。对于图$G$和$H$，强积$G\boxtimes H$的顶点集为$V(G\boxtimes H)=\{(g,h):g\in V(G),h\in V(H)\}$，其中两个顶点$(g,h)$和$(g',h')$相邻当且仅当$(g,h)\neq(g',h')$，$g$在$G$中等价于或相邻于$g'$，且$h$在$H$中等价于或相邻于$h'$。

Burgess等人[5]建立了一系列基础结果，揭示了包围警察数与若干标准图参数之间的联系，包括最小度、最大团的大小和独立数。特别是，他们的工作提供了本文中将反复使用的基本界限。我们将频繁依赖以下涉及最小度$\delta(G)$的推论。

**引理1.1** [5] 设$G$是一个图。则$s(G)\geq\delta(G)$。

Burgess等人[5]工作的重要部分涉及各种图积的包围警察数的界限。特别是，他们确定了路径的笛卡尔积$s(P_m\square P_n)$的精确值，以及关于路径强积的以下更复杂的结果。

**定理1.2** [5] 设$m,n$为整数，$2\leq m\leq n$。则
$$s(P_m\boxtimes P_n)=\begin{cases}5, & \text{若 } m\geq 4, \\ 4, & \text{若 } m=3 \text{ 或 } m=2 \text{ 且 } n\geq 4, \\ 3, & \text{若 } m=2 \text{ 且 } n\leq 3.\end{cases}$$

图$K_{m,n}\boxtimes K_{m,n}$的结构与此前研究的路径和环的强积有显著差异。路径和环的强积具有清晰的网格状或环面网格结构，其局部度要么均匀，要么仅在边界附近变化。相比之下，$K_{m,n}$的度已经高于路径和环，而强积进一步放大了这一特征，产生出更大且更复杂的顶点邻域。因此，$K_{m,n}\boxtimes K_{m,n}$中的局部邻域远比强网格中的复杂且依赖于度。这为小偷提供了更大的移动空间和许多可能的逃跑路线，因此警察不能简单地通过借鉴类似网格强积的局部策略来获胜。因此，$K_{m,n}\boxtimes K_{m,n}$构成了理解更复杂强积的包围警察数的一个自然且具有挑战性的测试案例。Burgess等人[5]开创了完全二部图强积的包围警察数的研究，并建立了以下下界。

**引理1.3** [5] 对于整数$m$和$n$，有$s(K_{m,n}\boxtimes K_{m,n})\geq mn$。

我们确定了所有正整数$m$和$n$的$s(K_{m,n}\boxtimes K_{m,n})$的精确值。我们的主要结果如下。

**定理1.4** 设$m$和$n$为满足$1\leq m\leq n$的整数。则
$$s(K_{m,n}\boxtimes K_{m,n})=\begin{cases}n+2, & \text{若 } m=1, \\ 8, & \text{若 } m=2 \text{ 且 } 2\leq n\leq 3, \\ 2n+2, & \text{若 } m=2 \text{ 且 } n\geq 4, \\ m^2+2m, & \text{若 } m\geq 3 \text{ 且 } m\leq n\leq m+1, \\ mn+1, & \text{若 } m\geq 3 \text{ 且 } n\geq m+2.\end{cases}$$

**警察与洞察型小偷**

沿用Huggan和Nowakowski[7]的术语，我们在全篇中将洞察型小偷称为机器人。警察与机器人博弈是经典"Cops and Robbers"博弈的变体，在有限、简单、连通的图上进行。一个玩家控制$k$个警察，另一个玩家控制一个机器人。游戏开始时，警察首先选择初始位置；多个警察可以占据同一顶点。然后机器人选择一个未被任何警察占据的顶点作为其初始位置。博弈按回合进行。在每一回合中，每个警察可以移动到相邻顶点或停留在原地，而机器人凭借对该回合警察策略的完全预知，选择最优的移动或停留。在这个意义上，警察和机器人的移动几乎是同时进行的。

尽管警察和机器人并非严格地轮流行动，但为了便利——我们将在全篇采用这一视角——我们将博弈视为按交替回合进行，同时理解抓捕条件已根据这一时序进行了调整。如果以下任一事件在某一回合中发生，则警察成功抓捕机器人：(i) 机器人移动后，一个警察与机器人占据同一顶点；或 (ii) 机器人穿过了警察在上一次移动中穿过的边。在制定策略时，假设警察知道机器人能够准确预判其移动。

对于图$G$，我们用$ccr(G)$表示在$G$上抓捕机器人所需的最少警察数量。一个重要的相关概念是$k$-核。给定正整数$k$，若导出子图$H\subseteq G$满足其最小度$\delta(H)\geq k$，则称$H$为$k$-核。

Huggan和Nowakowski[7]为警察与机器人模型发展了一个系统框架，获得了多种图类上$ccr(G)$的精确值和界限，以及显式的抓捕策略。他们还揭示了$ccr(G)$与$G$的核之间的根本联系，并确定了路径强积$ccr(P_m\boxtimes P_n)$的精确值。

**引理1.5** [7] 设$G$为包含某个$k$-核（$k$为正整数）的图。则$ccr(G)\geq k$。

**定理1.6** [7] 设$G$为强网格，即$G=P_m\boxtimes P_n$。则
$$ccr(G)=\begin{cases}4, & \text{若 } m,n>3, \\ 3, & \text{若 } \min\{m,n\}=2 \text{ 或 } 3.\end{cases}$$

一个自然的下一步是将研究从路径的强积扩展到环的强积。在Huggan和Nowakowski[7]工作的基础上，我们确定了$ccr(C_m\boxtimes C_n)$的精确值。我们在此方向上的主要结果如下。

**引理1.7** $ccr(P_m\boxtimes C_n)=5$，其中$m\geq 2$，$n\geq 3$为整数。

**定理1.8** $ccr(C_m\boxtimes C_n)=8$，其中$m,n\geq 3$为整数。

在全篇中，我们用$[m]=\{1,2,\ldots,m\}$。

**组织**

在第2节中，我们给出图$G=K_{m,n}\boxtimes K_{m,n}$的顶点划分和结构分析，由此推导出两个关键引理。基于这一预备工作，第3节专门证明该图的包围警察数。特别是，定理3.4处理了一般情形$m\geq 3$，而特殊情形$m=2$和$m=1$分别在定理3.5和定理3.6中详细处理。在第4节中，我们转向环强积上的警察与机器人博弈，并确定相应的警察数。

**第2节 图$K_{m,n}\boxtimes K_{m,n}$的结构与关键引理**

在本节中，我们分析强积$K_{m,n}\boxtimes K_{m,n}$的结构。在证明$K_{m,n}\boxtimes K_{m,n}$的包围警察数时，我们不妨设$n\geq m$。

设$K_{m,n}$为部集为$\{\alpha_1,\ldots,\alpha_m\}$和$\{\beta_1,\ldots,\beta_n\}$的完全二部图，令$G=K_{m,n}\boxtimes K_{m,n}$。我们将$G$的顶点集划分为三部分（见图2.1，图2.2），并描述每部分内部的邻接关系。

**第1部分。** 对于$1\leq i\leq m$，令$T_i=\{(\alpha_j,\alpha_i):1\leq j\leq m\}$，并令$U_1=T_1\cup\cdots\cup T_m$。则$|U_1|=m^2$，且$U_1$是……

**$K_{m,n}\boxtimes K_{m,n}$的包围警察数**

**引理3.1** 对于$m\geq 2$，有$s(K_{m,m}\boxtimes K_{m,m})=m^2+2m$。

**证明** 注意$K_{m,m}\boxtimes K_{m,m}$是一个$(m^2+2m)$-正则图。因此，由引理1.1，$s(K_{m,m}\boxtimes K_{m,m})\geq\delta(K_{m,m}\boxtimes K_{m,m})=m^2+2m$。

只需证明反向不等式。

对于每个固定的$i\in[m]$，在$V_i$的一个顶点上放置一个警察，记为$c_i$。在$V_{m+i}$的每个顶点上各放置一个警察；特别地，选择$V_{m+i}$的一个顶点，在其上放置两个警察，并记其中一个为$c_{m+i}$。总共放置$m^2+2m$个警察。在这种布置下，警察处于最优位置。

**第4节 警察与洞察型小偷**

在本节中，我们扩展定理1.6。我们确定了在路径和环的强积上抓捕机器人所需的最少警察数量，证明$ccr(P_m\boxtimes C_n)=5$。作为进一步的结果，我们建立了在两个环的强积上抓捕机器人所需的最少警察数量为$ccr(C_m\boxtimes C_n)=8$。

**引理1.7的证明**

将$P_m$的顶点标记为$\{1,\ldots,m\}$，将$C_n$的顶点标记为$\{1,\ldots,n\}$。图$P_m\boxtimes C_n$是一个$m\times n$的强柱面网格，其顶点为对$(i,j)$，其中$i\in[m]$……

**利益冲突声明**

作者声明不存在可能影响本文工作的已知竞争财务利益或个人关系。

**致谢**

Y. Zhang部分由中国河北省自然科学基金（项目编号：A2026205045，A2023205045）资助。H. Zhi部分由河北师范大学数学科学学院创新基金（项目编号：ycxzzbs202605）资助。

Hexuan Zhi | Yanbo Zhang