Graph searching and applications

警察与强盗游戏在对各种图形宽度进行建模时很有用，而这些图形宽度又有助于设计有效的算法。它们通过对机器人在实际情况中可能遇到的不同问题进行建模，在机器人学中也很有用。这项建议涉及后一种应用的数学问题。 在这种情况下，警察和强盗在给定的图上玩耍，通过交替从一个顶点移动到它的一个邻居，直到警察占据与强盗相同的顶点。因此，机器人可以尝试在网络或迷宫中定位入侵者。特别是，对于警察有获胜策略的图，我们调查了每个参与者智能移动的游戏的持续时间，即警察试图尽可能快地抓住抢劫犯，而抢劫犯试图尽可能长地生存。我们还考虑了一个新的更一般的博弈，在这个博弈中，许多警察在一个图G上博弈，试图在另一个图H上抓获一些强盗。G和H之间的抓获关系支配着博弈。例如，这可以模拟一个机器人在一个房间里移动，而他的位置被转换到其他地方的情况(与计算机一起使用的垫上的鼠标的离散版本，当然机器人不是由人控制的)。作为扩展，我们研究无限图上的博弈，因为它们的博弈性质是完全不同的。虽然这是一个纯粹的数学努力，但其中一些结果可能适用于Web图，因为有些人喜欢将其建模为无穷大的一个。 请注意，从事图形搜索的众多人员已经为行业协作做好了准备。

Cops-and-robbers games are useful in modelling various graph widths, which in turn are useful in the design of efficient algorithms. They are also useful in robotics by modelling different problems that robots used in practical situation may encounter. This proposal is concerned with the mathematics of the latter applications. In this case, a cop and a robber play on a given graph, by alternating moves from a vertex to one of its neighbours, until the cop occupies the same vertex as the robber. Thus a robot can attempt to locate an intruder in a network or in a maze. In particular, we investigate, for graphs on which the cop has a winning strategy, the length of games in which each player moves intelligently, that is, the cop tries to catch the robber as fast as possible while the robber tries to survive as long as possible. We also consider a new and more general game, in which a number of cops play on one graph G, trying to capture a number of robbers on another graph H. The capture relation between G and H governs the game. This can model, for example, a robot moving in one room, while his position is translated to a situation elsewhere (a discrete version of a mouse on a pad one uses with a computer, except of course the robot is not controlled by a human). As an extension, we look at the games on infinite graphs since their gaming properties are quite different. While this is a purely mathematical endeavour, some of the results could be applicable to the web graph as some people like to model it by an in infinite one. Note that the numerous people that work on graph searching are ready for industrial collaboration.