Game Development Reference
InDepth Information
from which the claim follows.
Monotonicity of the visible Cops and Robber Game
We are now ready to prove the main result of this section.
Theorem 7.24
The visible cops and robber game on undirected graphs is
monotone.
As discussed above, the theorem follows immediately from the following
lemma.
be a search tree of G of width k.
Then there is a monotone search tree of G of width k.
Lemma 7.25
Let G be a graph and
T
Proof
Let
m
:=

E
(
T
)

. We define the
weight
of a search tree
T
:=
(
T,new, search, clear
)as
weight
(
T
):=
t∈V
(
T
)
w
(
t
)

and its
badness
as
bn
:=
e∈E
(
T
)
e
nonmonotone
m
−dist
(
e
)
where the distance
dist
(
e
) of an edge
e
:= (
s, t
) is defined as the distance of
t
from the root of
T
.
Given two search trees
T
1
,
T
2
we say that
T
1
is
tighter
than
T
2
if
w
(
T
1
)
<
w
(
T
2
)or
w
(
T
1
)=
w
(
T
2
) and
bn
(
T
1
)
< bn
(
T
2
). Clearly, the tighter relation is
a wellordering.
Hence, to prove the lemma, we will show that if
T
:= (
T,new, search, clear
)
is a nonmonotone search tree of
G
then there is tighter search tree of
G
of
the same width as
T
.
Towards this aim, let
e
:= (
s, t
)
∈ E
(
T
) be a nonmonotone edge in
T
.
Case 1.
Assume first that

δ
(
search
(
e
))
≤
δ
(
clear
(
e
))

and let
e
1
,...,e
r
be
T
:= (
T,new
, search
,
clear
) where
new
(
v
):=
new
(
v
)
, clear
(
v
):=
clear
(
v
) for all
v
the outgoing edges of
t
. We define a new search tree
=
t
and
search
(
f
)=
search
(
f
) for all
f
=
e
and
clear
(
t
):=
E
(
G
)
\
search
(
e
)
new
(
t
):=
new
(
t
)
search
(
e
)
search
(
e
i
):=
search
(
e
i
)
∩
∩
search
(
e
)
.
clear
(
t
)
, new
(
t
)
, search
(
e
1
)
,...,search
(
e
r
)
By construction,
{
}
form a par
tition of
E
(
G
). Furthermore, for all
f
:= (
u, v
)
∈
E
(
T
) we still have
Search Nedrilad ::
Custom Search