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

Search Nedrilad ::

Custom Search