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 ))