A Game of COPS & ROBBERS
first designed by Mostafa Azizi, revised by Fan Chung Graham spring 2002
Description of the Game:
The Cop and Robber game is a very interesting game.
Two players, a cop (C),
and a robber (R), compete on a fixed, finite undirected graph H.
First, the cop
starts by placing himself at a node of his choice; then the robber does the same.
After that, the two players alternate (beginning with the cop) moving to
an adjacent node or choosing not to move.
All moves are seen by both players.
(Here we modified the original rules of Winkler by allowing the robber
"not to move".)
The cop wins the game if he can CAPTURE the robber, that is,
move onto the node that is occupied by the robber or the robber (is forced to) move onto
the node that is occupied by the cop .
The robbers wins if he is
able to avoid being captured indefinitely.
For example,
the Cop can clearly win on PATHS and looses
on CYCLES of length at least 4.
Also, the Cop wins when H has only one node, looped or
not, and on a pair of connected nodes.
If the graph is not connected, then the Robber wins.
Examples & Illusration of the Game:
|
Here we give some examples of graphs:
|
|
One important thing to notice is that all of the above graphs are finite.
In fact all are simple graphs except for #3.
Graph #3 is not simple.
Also notice that graph #5 is in two "pieces" so it is not connected. With this
game, we will concentrate on connected graphs with only one "piece", that means
graphs 1-4. (Unlike the orignial game of Winkler, the loops or multiple edges do not make a
difference in our game.)
Now let us illustrate the cop and robber game. Given a finite simple connected graph,
the cop starts at one vertex, the robber at another. At his turn each must move along
an edge to an adjacent vertex or choose not to move. They alternate turns. The cop tries to land on the
robber (or have the robber land on him!) while,
the robber tries to get away.
|
Now for a questions!
What is the smallest graph (i.e: smallest number of vertices) so that a single
robber can always evade a single cop, no matter where they start?
Well, Graph #1 is too small. Graph #5 depends on the starting position. It seems
that graph #2 is just right!.
A tree is a special kind of graph. Our graph #4 is an example of a tree. If a
graph is a TREE, then the cop will ALWAYS catch the robber.
Structural Description:
Suppose that i and j are adjacent nodes of a graph H such that any other node ajacent to i is
adjacent to j.
Then the map taking i to j, and every other node of H to itself, is a
homomorphism from H to H\{i}. We call this a fold of the graph H.
A finite graph H is dismantlable if there is a sequence of folds reducing H to
a graph with one node (looped or not). The name is chosen (in preference to
"cop-win") in order to stress the structure.
Try to prove the following theorem:
Theorem:
A graph is cop-win if and only if the graph is dismantlable.
This leads to an efficient algorithm for this rather complex game!
Describe an algorithm to decide if an input graph is cop-win or robber-win.
If the graph is cop-win, describe an algorithm for the cop to always catch
the robber.
More questions and more cops:
-
For a given cop-win graph, what is the number of steps required for the cop to catch the robber
(even in the worst case)?
- What happens if we can have more cops?
-
The cop number of a graph is defined to be the minimum number of cops needed to catch a robber.
For
a given graph, how do we determine its cop number?
References:
1.
Richard Nowakawski and
Peter Winkler,
Vertex-to-vertex pursuit in a graph, Discrete Math 43 (1983), 235-239.
2. Graham Brightwell and
Peter Winkler,
Gibbs measures and dismantlable graphs, J. Comb.
Theory (Series B) 78 (2000), pp. 141-169.
PostScript file
3. Bondy and Murty, Graph Theory with Applications, North Holland, 1976.
4. Harary, Graph Theory, Addison-Wesley, 1969.
5. Tero Harju: http://users.utu.fi/harju/exercises.ps.gz
6. H. Jem: http://hjem.get2net.dk/policeshooting/images/div.grafik/
7. M. Aigner and M. Fromme, A game of cops and robbers, Discrete Applied Math 8 (1984), 1-12. (This paper includes a proof that 3 cops suffice for planar graphs.)