Game Development Reference
In-Depth Information
T is less than the
Arguing as in the previous case, we see that the weight of
weight of
T
. This concludes the proof.
We demonstrate the construction in the proof by the search tree in Fig-
ure 7.5. Let s be the root of that tree, with new ( s ):=
and t be the
successor of s with new ( t ):=∅. Let e := ( s, t ). Thus, search ( e ):= { 12 , 13 , 24 }
and clear ( t ):= { 35 , 36 ,X} , where X := { 56 , 57 , 67 } .
Clearly, the edge e is non-monotone as
{
34 , 36 , 46
}
search ( e )
clear ( t ):=
{
12 , 13 , 24 , 35 , 36 , 56 , 57 , 67
}
E ( G ) .
For instance the edge 34
search ( e )
clear ( t ).
and therefore
we are in Case 1 of the proof above. Let e 1 be the edge from t to the node
labelled { 34 , 46 } and let e 2 be the other out-going edge from t .
We construct the new search tree which is exactly as the old one except
that now
Now, δ ( search ( e )) :=
{
3 , 4
}⊆
V ( G )and δ ( clear ( t )) :=
{
3 , 6
}
clear ( t ):= E ( G )
\
search ( e )=
{
34 , 35 , 36 , 46 , 56 , 57 , 67
}
new ( t ):= new ( t )
search ( e ):=
search ( e 1 ):= search ( e 1 )
search ( e ):=
{
24
}
search ( e 2 ):= search ( e 2 )
search ( e ):=
{
12 , 13
}
.
The new search tree is shown in Figure 7.6. Note that guard ( t )isnow
guard ( t ):= V [ new ( t )]
δ ( clear ( e ))
δ ( search ( e 1 ))
δ ( search ( e 2 ))
=
∪{
3 , 4
}∪{
2 , 4
}∪{
2 , 3
}
=
{
2 , 3 , 4
}
.
That is, in the new search tree the cops start on the vertices 3 , 4 , 6 as before
but now, if the robber moves into the component { 1 , 2 } , then they go to
{ 2 , 3 , 4 } as might be expected. Continuing in this way we would gradually
turn the search tree into a monotone search tree corresponding to a monotone
strategy.
Further applications of sub-modularity
Sub-modularity has been used in numerous results establishing monotonicity
of graph searching games. A very general application of this technique
has been given by Fomin and Thilikos [2003] where it was shown that all
invisible graph searching games defined by a sub-modular border function
are monotone. The proof presented above has been given by Mazoit and