Graph searching - structural properties

图搜索-结构特性

• 批准号: RGPIN-2017-05065
• 负责人: Hahn, Gena
• 金额: $ 1.46万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=652810
• 关键词: Graph; searching; structural; properties

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.***

自20世纪80年代以来，人们就开始研究警察与强盗游戏，特别是在发现各种图形宽度之间的联系之后。算法和复杂性问题似乎主导了该领域，因为优化等方面的应用，但一些基本问题仍未得到解答：图的cop-number， k-cop-win图的特征，最优博弈的长度等。我们希望研究由Nowakowski和Winkler以及Quillot定义的博弈的这些基本问题，并考虑新的模型。我们的图论小组（两名研究人员，最多五名学生）一直在研究循环对所需警察数量的影响（有些图在警察获胜之间交替，而不是从无循环图开始一个接一个地添加循环）。在2016年夏天，我们制作了一个版本的游戏，其中警察必须在指定的顶点抓住强盗（这不再是一个完全的知识游戏，强盗不知道顶点）。我们希望继续研究这些已经有了初步结果的变体。我们决定k个警察能否在给定的*（有限）图上抓住r个劫匪的算法用于机器人运动规划，我们认为指定捕获顶点和描述策略的算法对机器人专家也很有用。此外，我们不仅要考虑到抓捕抢劫犯所需的警察数量，还要考虑到这样做的成本。也许多几个警察*会花费更少？这里的主要问题是定义成本。我们考虑了几种可能性，并将继续朝这个方向发展。由于有限正则图除非是完全的，否则不是双赢的，所以Cayley图没有被考虑太多。我们认为它们值得再看一遍，特别是与上面（模糊地）描述的一些模型联系在一起。****最后，我们希望研究cop-win无限图。我们相信，理解无限会带来对有限的理解。无限图上的抢抢游戏是不同的（有许多抢赢的顶点传递无限图，但只有完全有限图）。Lehner最近的一篇论文表明，我们一直在向后看这个问题，忽略了一个事实：对于有限图，而不是无限图，良序的逆是良序。因此，任何试图通过对有限图的排序来表征无限的非双赢图的尝试都注定要失败。这表明，即使对于有限的图，我们也应该重新考虑我们的方法。我们正打算这样做。****无限双赢图研究的一部分是图的结构性质的含义。推广我们2009年论文中的构造，我们有不同于唯一（超）齐次可数图（随机，或Rado，图）的全称可数图的例子。我们希望继续研究这种结构