Graph searching - structural properties

图搜索-结构特性

• 批准号: RGPIN-2017-05065
• 负责人: Hahn, Gena
• 金额: $ 1.46万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=677172
• 关键词: 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定义的博弈的这些基本问题，并考虑新的模型。我们的图论 * 小组（两名研究人员，最多五名学生）一直在研究循环对所需的cops数量的影响（有一些图在cop-win* 之间交替，而不是从一个无环图开始一个接一个地添加循环）。* 在2016年夏天 *，我们开发了一个版本的游戏，在这个版本中，警察必须在指定的顶点抓住 * 强盗（这不再是一个完全的知识游戏，强盗不知道顶点）。我们希望继续 * 研究这些变种，我们有一些初步的结果。我们的算法，以决定是否k个警察可以抓住r个强盗在一个给定的 *（有限）图是用于机器人的机器人运动规划，我们认为，指定一个捕获顶点和算法来描述一个战略也将是有用的机器人专家。此外，我们不仅要考虑抓住劫匪所需的警察数量，还要考虑这样做的成本。也许多几个警察 * 会花更少的钱？这里的主要问题是确定成本。我们已经考虑了几种可能性，并将继续朝着这个方向努力。由于有限正则图只有在完备的情况下才是cop-win的，因此Cayley图并没有得到太多的考虑。我们认为它们 * 值得再次研究，特别是与上面描述的一些模型（模糊）有关。最后，我们希望研究cop-win无限图。我们相信，理解无限带来了对有限的理解。无限图上的Cops-and-Robbers博弈是不同的（有许多Cops-win顶点传递无限图，但只有完全有限图）。Lehner最近的一篇论文表明，我们一直在向后看这个问题，忽略了一个事实，即良序的逆对于有限图是良序，但对于无限图不是良序。因此，任何试图通过类似于有限图的排序来刻画无限cop-win图的尝试都注定要失败。这表明，即使对于 * 有限图，我们也应该重新考虑我们的方法。我们建议这样做。无限cop-win图的研究的一部分是图的结构性质的影响。从我们2009年的论文中推广一个 * 构造，我们有泛可数图的例子，它们 * 不同于唯一（超）齐次可数图（随机或Rado图）。我们希望继续研究这种结构。*