Game Development Reference
InDepth Information
the strategy as a set of connected subgraphs. 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 subgraph
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
×
5grid.
(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
×
5grid
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
Search Nedrilad ::
Custom Search