Searching on graphs
LE3 .A278 2009
2009
Clarke, Nancy Mendivil, Franklin
Acadia University
Bachelor of Arts
Honours
Mathematics and Statistics
Mathematics & Statistics
Many real world problems can be modeled with graphs. This thesis examines two dierent areas of graph searching: the game of Cops and Robber with visibility con- straints and search strategies for nding a specied node on a graph. The game of Cops and Robber is fully characterized in the classic case with one cop. After a brief introduction to the game, this thesis looks at the eects of imposing visibility constraints on copwin graphs, specically the case of 2-visibility. Examples of copwin graphs under 2-visibility, as well as relationships between visibility con- straints and graph size for trees and grids are presented. The third chapter of the thesis deals with the problem of searching for a sta- tionary target on a graph with a visibility of 1. This could be useful when dealing with optimization problems which can be modeled by searching a graph structure. A strategy is outlined for nding a minimal walk which guarantees nding the desired vertex. This strategy rst nds a maximally leafy spanning tree for the graph, then prunes the leaves and nds a minimal walk on the remaining subgraph. Preliminary code for implementing this strategy is given in the appendices.
The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.
https://scholar.acadiau.ca/islandora/object/theses:644