警察与小偷博弈

警察与小偷博弈在图论中常称图上的追逐博弈（cops and robbers game）。它把地点抽象为顶点、可走的通道抽象为边，研究追逐者需要怎样的起点与移动规则才可保证在有限步内到达逃避者所在顶点。这里的“警察”“小偷”只是两种数学角色，不对应真实执法情境。

采用一个精确的版本：图 $G$ 有限、简单、连通；一名警察先选顶点，小偷看到后选顶点。此后警察先走，双方轮流；每步可沿一条边移动，或留在原顶点，双方始终知道对方位置。只要任一方行动后两者位于同一顶点，就抓到小偷；若小偷能无限避开，则小偷获胜。研究其他版本时，不可擅自省去起点顺序、可否停留、是否看得见这几项规则。

一条路径与一个环

先看四个顶点的路径 $P_{4} : 1 - 2 - 3 - 4$ 。警察起于 2。若小偷选 1 或 3，警察第一步即到达该顶点；若小偷选 4，警察先走到 3，小偷在 4 只能留在 4 或走到已被占据的 3，下轮警察到 4 抓到。因此 $P_{4}$ 一名警察足够。路径上更一般的策略是向小偷靠近，并把小偷逼向端点。

再看四顶点的环 $C_{4} : 0 - 1 - 2 - 3 - 0$ 。不论警察先选哪个点，小偷都选它的对面。每当警察移动到某个相邻点，小偷可移到新位置的对面；若警察停留，小偷也停留。警察从距离 2 的位置一步到不了小偷当前顶点，而小偷每轮都能恢复“相对”的局面，所以一名警察不能保证抓到。图中两幅小图只有一条边的差别，却改变了追逐结果。

左侧四顶点路径上警察从第二点迫使小偷退到端点，右侧四顶点环上小偷始终保持与警察相对的顶点 — 路径有端点可封锁；环没有端点，一名警察在四环上无法保证抓到小偷。

若允许两名警察， $C_{4}$ 可让他们先占一对对顶点 0 与 2。小偷必须选 1 或 3，它与至少一名警察相邻，警察第一步便可到达。这说明“至少需要几名警察”是图本身与规则共同决定的最小人数问题。对别的图，不能只凭顶点数或边数推出答案。

策略是一套条件指令

说“警察总往右走”并不足以描述完整策略，因为小偷位置会变。策略应在每一轮可见的两个位置上指定下一步。证明“保证抓到”还须排除无限躲避的可能；证明“不能保证”则要给出小偷对警察任何合法行动的应对。上面 $C_{4}$ 的“始终在对面”就是这样的不变量。图的对称性帮助发现策略，但真正的论证是：每轮移动合法、不会当场被抓、移动后不变量恢复。

参考资料

Richard Nowakowski 与 Peter Winkler，〈Vertex-to-vertex pursuit in a graph〉，《Discrete Mathematics》，1983，可停留、可沿边移动且双方可见的图上追逐模型原始论文。
Anthony Bonato 与 Andrea Burgess，〈Cops and Robbers on Graphs Based on Designs〉，多警察版本与图的最小追捕人数的研究实例。