Graph searching and applications

图搜索及应用

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

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.

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