Game Development Reference
In-Depth 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 non-monotone
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 well-ordering.
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 )
By construction,
{
}
form a par-
tition of E ( G ). Furthermore, for all f := ( u, v )
E ( T ) we still have
Search Nedrilad ::




Custom Search