Game Development Reference
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.
The visible cops and robber game on undirected graphs is
As discussed above, the theorem follows immediately from the following
be a search tree of G of width k.
Then there is a monotone search tree of G of width k.
Let G be a graph and
Let m :=
E ( T )
. We define the weight of a search tree
( T,new, search, clear )as
weight ( T ):=
t∈V ( T ) |w ( t ) |
and its badness as
e∈E ( T )
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
2 we say that
1 is tighter than
2 if w (
1 ) <
2 )or w (
1 )= w (
2 ) and bn (
1 ) < bn (
2 ). Clearly, the tighter relation is
Hence, to prove the lemma, we will show that if T := ( T,new, search, clear )
is a non-monotone 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 non-monotone 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 out-going 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 )
form a par-
tition of E ( G ). Furthermore, for all f := ( u, v )
E ( T ) we still have