Game Development Reference
In-Depth Information
the strategy as a set of connected sub-graphs. This form of winning strategies
is known as a bramble .
Definition 7.32 Let G be a graph and B, B ⊆ V ( G ). B and B touch if
B ∩ B = ∅ or there is an edge {u, v}∈E ( G ) with u ∈ B and v ∈ B .
A bramble in a graph G is a set B := {B 1 ,...,B l } of sets B i ⊆ V ( G )
such that
1 each B i induces a connected sub-graph G [ B i ] and
2 for all i, j , B i and B j touch.
The order of
B
is
min
{|
X
|
: X
V ( G ) s.t. X
B
=
for all B
∈B}
.
The bramble width bw( G )of G is the maximal order of a bramble of G .
We illustrate the definition by giving a bramble of order 3 for the graph
depicted in Figure 7.1. In this graph, the set
:= {
}
B
1 , 2 , 3
}
,
{
7 , 8 , 9
}
,
{
4 , 5 , 6
forms a bramble of order 3.
It is easily seen that the existence of a bramble of order k yields a winning
strategy for the robber against k cops.
To give a more interesting example, consider the class of grids . A grid is a
graph as indicated in Figure 7.7 depicting a 4
×
5-grid.
(1,1) 1,2) 1,3) 1,4) 1,5)
(2,1)
(2,2)
(2,3)
(2,4)
(2,5)
(3,1)
(3,2)
(3,3)
(3,4)
(3,5)
(4,1) 4,2) 4,3) 4,4) 4,5)
Figure 7.7 4
×
5-grid
More generally, an n × m -grid is a graph with vertex set { ( i, j ):1 ≤ i ≤
n, 1 ≤ j ≤ m} and edge set
{ i, j ) , ( i ,j ) :
i |
j |
|
i
+
|
j
=1
}
.
If G is an n
×
m -grid then its i -th row is defined as the vertices
{
( i, j ):1
j
m
}
and its j -th column as
{
( i, j ):1
i
n
}
.A cross in a grid is the
union of one row and one column. For any n
×
n -grid we can define a bramble