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