Game Development Reference
InDepth Information
•
search
:
E
(
T
)
→
Pow(
E
(
G
))
such that
1if
t ∈ V
(
T
) and
e
1
,...,e
r
are the outgoing 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 outgoing 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
nonmonotone
. 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
)
Search Nedrilad ::
Custom Search