Game Development Reference

In-Depth Information

Figure 7.4 Non-monotone strategy tree for the graph in Figure 7.3

plus the edges joining this component to the cop positions guarding the

robber space. We will next define the notion of a border for a set of edges.

Definition 7.15

Let
E
be a set. We denote the set of partitions

P

:=

(
X
1
,...,X
k
)of
E
by

P

(
E
), where we do allow degenerate partitions, i.e.,

X
i
=

∅

for some
i
.

Definition 7.16

E
(
G
). By
δ
(
F
) we denote

the
border
of
F
, i.e., the set of vertices incident to an edge in
F
and also to

an edge in
E
(
G
)

Let
G
be a graph and let
F

⊆

F
.

We extend the definition to partitions
P
:=

\

{

X
1
,...,X
r
}∈P

(
E
(
G
)) by

setting

δ
(
P
):=
v

.

there are edges
e

∈

X
i
and
f

∈

X
j
,

∈

V
(
G
):

for some 1

≤

i<j

≤

r
, s.t.
v

∈

e
and
v

∈

f

The intuition behind a border is that if the robber controls the edges in
F

and the cops want to prevent the robber from escaping then they need to

guard the vertices in
δ
(
F
). For a partition
P
of the edge set, this means that if

the cops want to split the graph into the sub-graphs defined by the individual

sets of edges, they have to put cops on
δ
(
P
). For example, in the graph in

Figure 7.3 we get
δ
{
12
,
13
},{
24
,
34
,
46
},{
35
,
36
,
56
,
57
,
67
}
=
{
2
,
3
,
6
}
.

Definition 7.17

Let
G
be a graph. A
search-tree
of
G
is a tuple

(
T,new, search, clear
)

where

• T
is finite a directed tree

•

clear, new
:
V
(
T
)

→

Pow(
E
(
G
))

Search Nedrilad ::

Custom Search