Game Development Reference
In-Depth Information
search : E ( T )
Pow( E ( G ))
such that
1if t ∈ V ( T ) and e 1 ,...,e r are the out-going edges of t then
{
new ( t ) , clear ( t ) , search ( e 1 ) ,...,search ( e r )
}
form a (possibly degenerated) partition of E ( G ) and
2 search ( e )
clear ( t )=
for every edge e := ( s, t )
E ( T ).
Let t
V ( T ) be a node with out-going edges e 1 ,...,e r . We define
guard ( t ):= V [ new ( t )] ∪ δ search ( e 1 ) ,...,search ( e r ) , clear ( t )
and the width w ( t ) of a node t as w ( t ):=
|
guard ( t )
|
. The width of a search
tree is max
{
w ( t ): t
V ( T )
}
.
An edge e := ( s, t )
V ( T ) is called monotone if search ( e )
clear ( t )= E ( G ).
Otherwise it is called non-monotone . We call
T
monotone if all edges are
monotone.
It is not too di cult to see that any strategy tree ( T,cops, robber ) cor-
responds to a search tree ( T,new, search, clear ) over the same underlying
directed tree T , where
}
search ( s, t ):= {e = {u, v}∈E ( G ): u ∈ robber ( e )or v ∈ robber ( e ) }
clear ( t ):= E ( G )
new ( t ):=
{
e =
{
u, v
}∈
E ( G ): u, v
cops ( t )
\ new ( t )
search ( t, t ) .
( t,t ) ∈E ( T )
Figure 7.5 shows the search tree corresponding to the strategy tree in Fig-
ure 7.4. Here, the node labels correspond to new ( t ), e.g., the label '34,36,46'
of the root corresponds to the edges (3 , 4) , (3 , 6) and (4 , 6) cleared by initially
putting the cops on the vertices 3 , 4 , 6. The edge label in brackets, e.g.,
(35,36,X) corresponds to the clear label of their endpoint. Here, X is meant
to be the set 56, 57, 67 of edges and is used to simplify presentation. Finally,
the edge labels with a grey background denote the search label of an edge.
Note that for each node t ∈ V ( T ) the cop position cops ( t ) in the strategy
tree is implicitly defined by guard ( t ) in the search tree. While every strategy
tree corresponds to a search tree, not every search tree has a corresponding
strategy tree. For instance, if there is an edge e := ( s, t )
V ( T ) in the search
tree such that search ( e )
= E ( G ) then this means that initially the
cops are guard ( s ) with the robber being somewhere in search ( e ) and from
there the cops move to guard ( t ). By doing so the cops decide to give up some
part of what they have already searched and just consider clear ( t )tobe
clear ( t )