Graph searching - structural properties

警察与抢劫犯 自20世纪80年代以来，人们一直在研究S的游戏，特别是在 发现具有各种图形宽度的连接。算法和复杂性问题 由于在最优化等方面的应用，似乎占据了该领域的主导地位，但一些基本问题仍然没有得到回答：图的COP数、k-COP-WIN图的特征、最优博弈的长度等。 我们希望研究诺瓦科夫斯基所定义的游戏的这些基本问题，并 Winkler和Quillot，并考虑新的型号。我们的图论 小组(两名研究人员，最多五名学生)一直在研究 循环对所需COP数量的影响(存在COP-WIN之间交替的图 而不是从无环图开始一个接一个地添加循环)。 2016年的夏天 我们做了一个游戏的版本，在这个版本中，警察必须抓住 强盗在指定的顶点(这不再是一个完全的知识游戏，强盗不知道这个顶点)。我们希望继续 研究这些变种，我们有了一些初步的结果。我们的算法来决定k个警察是否能在给定的条件下抓到r个抢劫犯 (有限)图用于机器人运动规划，我们认为指定捕获顶点和描述策略的算法对机器人专家也很有用。 此外，我们想概括地说，不仅要考虑到抓捕 强盗，还有这么做的代价。也许再多几个警察 成本会更低吗？这里的主要问题是确定成本。我们已经考虑了几个 有可能，并将继续朝着这个方向发展。 由于有限正则图除非是完全的，否则不是COP-WIN的，所以Cayley图并没有得到太多的考虑。我们认为他们 值得再看一遍，特别是与(含糊地)描述的一些模型有关的 上面。 最后，我们希望研究COP-WIN无限图。我们相信，理解无限带来了对有限的理解。无限图上的警察与强盗博弈是不同的(有许多COP-WIN点传递无限图，但只有完全有限图)。一个 Lehner最近的一篇论文表明，我们一直在向后看这个问题，忽略了这样一个事实，即良序的逆序对于有限图是良序，而对于无限图则不是。因此，任何试图 通过有限个COP-WIN图的类似序来刻画无限COP-WIN图注定要 失败了。这表明，即使是对于 有限图我们应该重新考虑我们的方法。我们建议这样做。 无限COP-WIN图研究的一部分是对图的结构性质的暗示。概括为 从我们2009年的论文中，我们有一些泛可数图的例子，它们是 不同于唯一(超)齐次可数图(随机或RADO图)。 我们希望继续研究这种结构。

Cops-and-robbers games have been studied since the 1980's, especially after the discovery of connections with various graph widths. Algorithmic and complexity questions seem to dominate the field because of applications in optimisation, among other things, but some basic questions remain unanswered: the cop-number of a graph, a characterisation of k-cop-win graphs, the length of an optimal game, etc. We wish to study these basic questions for the game as defined by Nowakowski and Winkler, and by Quillot, and to consider new models. Our graph theory group (two researchers, up to five students) has been studying the influence of loops on the number of cops needed (there are graphs that alternate between cop-win and not with the addition of loops one by one starting with a loopless graph). In the summer 2016 we have worked on a version of the game in which the cops have to catch the robber at a specified vertex (this is no longer a total knowledge game, the robber does not know the vertex). We wish to continue studying these variants where we have some preliminary results. Our algorithm to decide whether k cops can catch r robbers on a given (finite) graph is used in robotics for robot motion planning and we think that specifying a capture vertex and an algorithm to describe a strategy would also be useful to roboticists. Further, we would like to generalise by considering not only the number of cops needed to catch the robber, but also the cost of doing so. Perhaps having a few more cops would cost less? The main problem here is defining the cost. We have considered several possibilities and will continue in this direction. Since finite regular graphs are not cop-win unless complete, Cayley graphs have not been much considered. We think they are worth looking at again, especially in connection with some of the models (vaguely) described above. Last, we wish to study cop-win infinite graphs. We believe that understanding the infinite brings an understanding of the finite. Cops-and-robbers games on infinite graphs are different (there are many cop-win vertex transitive infinite graphs but only complete finite ones). A recent paper by Lehner suggests that we have been looking the problem backwards, overlooking the fact that the reverse of a well-order is a well-order for finite graphs but not for infinite ones. Thus any attempt at characterising infinite cop-win graphs through an ordering like that for finite ones is doomed to failure. This indicates that even for finite graphs we should reconsider our approach. We propose to do just that. A part of the study of infinite cop-win graphs are the implications to structural properties of graphs. Generalising a construction from our 2009 paper we have examples of universal countable graphs that are different from the unique (ultra)homogeneous countable graph (the random, or Rado, graph). We wish to continue studying such structures.