Pursuit evasion on infinite graphs
Pursuit evasion on infinite graphs
复制标题
无限图上的追逃
DOI：
10.1016/j.tcs.2016.04.024
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Florian Lehner
中科院分区：
文献类型：
--
作者：
Florian Lehner
警察与强盗游戏是两个玩家之间的游戏，其中一个玩家试图通过沿着图的边缘移动来抓住另一个玩家。众所周知，在有限图上，警察有获胜策略，当且仅当图是可构造的，并且有限性对于这个结果是必要的。我们提出了弱警察获胜图的概念，这是无限图的获胜标准，可以导致泛化。事实上，我们概括了结果的一半，即我们证明每个可构造图都是弱共赢的。我们还表明 Chastand 等人研究的类似概念。 （他们也称为弱cop-win）不足以将上述结果推广到无限图。在局部有限情况下，我们将可构造图描述为警察具有所谓保护策略的图，并证明这种策略的存在意味着即使对于非局部有限图也是可构造的。
The cop-and-robber game is a game between two players, where one tries to catch the other by moving along the edges of a graph. It is well known that on a finite graph the cop has a winning strategy if and only if the graph is constructible and that finiteness is necessary for this result.We propose the notion of weakly cop-win graphs, a winning criterion for infinite graphs which could lead to a generalisation. In fact, we generalise one half of the result, that is, we prove that every constructible graph is weakly cop-win. We also show that a similar notion studied by Chastand et al. (which they also dubbed weakly cop-win) is not sufficient to generalise the above result to infinite graphs.In the locally finite case we characterise the constructible graphs as the graphs for which the cop has a so-called protective strategy and prove that the existence of such a strategy implies constructibility even for non-locally finite graphs.