Lions and Contamination: Triangulated Graph and Regular Graph

Abstract

Pursuit-Evasion Problem is one of the areas being studied in computer science. Pursuit-Evasion Problem is the problem in which Pursuer, which has to catch all the other groups, and Evader, which continues to avoid, move in one graph, and there are variations. Among them, there is Lions and Contamination of the rule that Evader exists on all nodes other than the initial location of Pursuer and increases the population by going to empty nodes. It is proved that when n Pursuers could not hold all of the graph H, n Pursuers could not hold the graph X that only added edge with graph H as the subgraph, and that when graph H has the Grid form or the Regular Graph, n Pursuers could not hold the graph X with vertex added. In addition, if the minimum degree of the graph is n, it is proved that it is impossible with n-1 Pursuers, and the number of Non Catchable Pursuers in the Regular Graph can be set up. Applying the proven theories, it can find the minimum required number of Pursuers for Triangulated Square Grid and Triangular Grid. Keywords: Graph Theory, Pursuit-Evasion Problem, Lions and Contamination|Lions and Contamination: Triangulated Graph and Regular Graph 본 논문은 컴퓨터 과학에서 연구되고 있는 분야 중 하나인 Pursuit-Evasion Problem 에 대해 다룬다. Pursuit-Evasion Problem은 다른 그룹을 모두 잡아야 하는 Pursuer와 계속해서 회피하는 Evader 가 한 그래프에서 움직이는 문제로서 다양한 변형들이 존재하고 그중에서 Evader 가 Pursuer 의 초기 위치 이외의 모든 노드에 존재하며 빈 노드에 가서 개체수를 늘리는 규칙의 Lions and Contamination 을 다룬다. 한 그래프 H 에서 n 개의 Pursuer 로 모두 잡을 수 없을 때, 그래프 H 를 Subgraph 로 가지고 Edge 만 추가한 그래프 X 역시 n 개의 Pursuer 로 잡을 수 없다는 것을 증명했으며, 그래프 H 가 Grid 형태이거나 Regular Graph 를 가질 때, Vertex 를 추가한 그래프 X 도 n 개의 Pursuer 로 잡을 수 없음을 증명했다. 또한 그래프의 Degree 가 n 일 경우 n-1 개의 Pursuer 로는 불가능함을 증명해서 Regular Graph 에서의 불가능한 Pursuer 개수의 Upper Bound 를 설정할 수 있다. 증명한 이론들을 적용해서 Triangulated Square Grid 와 Triangular Grid 의 최소 필요한 Pursuer 의 개수를 구한다. 핵심어: 그래프 이론, 추적-회피 문제, Lions and Contamination