Time and motion in graphs

边缘搜索是一种图搜索模型，在这种模型中，一组缓慢的、可见的搜索者在图G的一个顶点到另一个顶点移动，以捕获一个快速的、不可见的入侵者，这个入侵者可能在顶点和边缘上都停了下来。捕获入侵者所需的最小搜索者数量被称为边缘搜索数g。搜索问题可以应用于搜索和救援，视频游戏人工智能，甚至清洁核电站供水管道。***这项研究涉及使用软件代理来捕获恶意移动“入侵者”，如计算机病毒。离散追踪逃避（也称为图搜索）是数学和计算机科学中的一系列问题，其中一个群体试图在一个环境中追踪另一个群体的成员。在这个追逃问题的特殊表述中，环境是一个计算机网络，它被建模为一个图。通常，问题是确定捕获入侵者所需的最小代理数量。这个研究计划是考虑如何移动代理，以便快速捕获入侵者。或者，我们可以考虑如何以最小化所需工时的方式移动代理，而不是最小化所需的代理数量或时间。这些问题即使用计算机也很难解决，因此我们需要理论研究，就像这个研究项目所涉及的那样，“走捷径”，使其更加实用。***由于本研究应用于网络安全问题，所提出的研究可能会对计算机网络的设计和建设产生影响，以尽量减少恶意代理造成的损害，并将有助于推进图搜索和相关问题的数学研究。它还将为研究生和本科生提供培训机会

Edge searching is a graph searching model in which a collection of slow, visible searchers move from vertex to vertex in a graph G to capture a fast, invisible intruder that may stop on both vertices and edges. The minimum number of searchers needed to capture the intruder is known as the edge search number of G. Searching problems have applications to search and rescue, video game artificial intelligence, and even to cleaning nuclear plant water supply pipes.***This research deals with using software agents to capture a malicious mobile "intruder" such as a computer virus. Discrete pursuit-evasion (also called graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. In this particular formulation of the pursuit-evasion problem, the environment is a computer network and it is modeled as a graph. Classically, the problem has been to determine the minimum number of agents needed to capture the intruder. This research program is to consider instead how to move agents in such ways as to quickly capture the intruder. Alternatively, we might consider how to move the agents in such a way as to minimize the number of man-hours required, instead of minimizing the number of agents or time required. These problems are difficult to solve, even with computers, and consequently we need theoretical research, like that involved in this program of research, to "cut corners" and make this more practical.***Because of the applications of this research to network security problems, the proposed research is likely to have impact in the design and construction of computer networks to minimize damage caused by malicious agents, and will contribute to the advancement of mathematical research in graph searching and related problems. It will also provide training opportunities for graduate and undergraduate students.**