Game Development Reference
InDepth Information
Proof
Let
P
:=
{
X
1
,...,X
r
}
and
Q
:=
{
Y
1
,...,Y
s
}
be partitions of
E
:=
E
(
G
). Let 1
s
. By rearranging the sets
P
and
Q
we can
assume w.l.o.g. that
i
=
j
= 1. We want to show that
≤
i
≤
r
and
q
≤
j
≤
φ
(
P
)+
φ
(
Q
)
≥
φ
(
P
X
1
↑Y
1
)+
φ
(
Q
Y
1
↑X
1
)
Y
1
,X
2
∩
=

δ
(
X
1
∪
Y
1
,...,X
r
∩
Y
1
}
+
X
1
,Y
2
∩

δ
(
Y
1
∪
X
1
,...,Y
S
∩
X
1
}
.
V
(
G
)is
contained in one of the sets
δ
(
P
X
1
↑Y
1
)
,δ
(
Q
Y
1
↑X
1
) occurring on the righthand
side, i.e., is contributing to a term on the right, then the vertex is also
contributing to a term on the left. And if this vertex contributes to both
terms on the right then it also contributes to both on the left.
Towards this aim, let
v
We will prove the inequality by showing that if a vertex
v
∈
V
(
G
) be a vertex. Suppose first that
v
is
contained in exactly one of
δ
(
P
X
1
↑Y
1
)or
δ
(
Q
Y
1
↑X
1
), i.e., contributes only to
one term on the righthand side. W.l.o.g. we assume
v
∈
∈
δ
(
P
X
1
↑Y
1
). If there
is 1
≤
i<j<r
such that
v
is contained in an edge
e
1
∈
X
i
and
e
2
∈
X
j
,
Y
1
and also to
then
v
∈
δ
(
P
). Otherwise,
v
must be incident to an edge
e
∈
an edge
f
δ
(
Q
) as the edge
f
occurs
in
Y
1
and the edge
e
must be contained in one of the
Y
l
,
l>
1.
Now, suppose
v ∈ δ
(
P
X
1
↑Y
1
) and
v ∈ δ
(
Q
Y
1
↑X
1
). But then,
v
is incident
to an edge in
e ∈ X
i
∩ Y
1
, for some
i>
1, and also to an edge
f ∈ Y
j
∩ X
1
,
for some
j>
1. Hence,
f ∈ X
1
and
e ∈ X
i
and therefore
v ∈ δ
(
P
) and,
analogously,
e ∈ Y
1
and
f ∈ Y
j
and therefore
v ∈ δ
(
Q
). Hence,
v
contributes
2 to the lefthand side. This concludes the proof.
∈
X
j
∩
Y
1
, for some
j>
1. But then
v
∈
We will primarily use the submodularity of
φ
in the following form.
Lemma 7.23
Let G be a graph and P
:=
{
X
1
,...,X
k
}∈P
(
E
(
G
))
be a
partition of E
(
G
)
.LetF
⊆
E
(
G
)
such that F
∩
X
1
=
∅
.
If

δ
(
F
)
≤
δ
(
X
1
)

then

δ
(
P
X
1
↑F
)
≤
δ
(
P
)

If

δ
(
F
)

<

δ
(
E
1
)

then

δ
(
P
X
1
↑F
)

<

δ
(
P
)

.
Proof
By submodularity of
φ
(
P
):=

δ
(
P
)

we know that
δ
(
P
)

+
δ
(
{F, F
c
}
)
≥δ
(
P
X
1
↑F
)

+
δ
(
{F ∪ X
1
,F
c
∩ X
1
)
.
But, as
F ∩ X
1
= ∅ we have
F ∪ X
1
=
X
1
and
F
c
∩ X
1
=
X
1
. Hence, we
have
F, F
c
X
1
,X
1
)

δ
(
P
)

+

δ
(
{
}
)
≥
δ
(
P
X
1
↑F
)

+

δ
(
{

and therefore
+


X
1
,X
1
)
F, F
c

δ
(
P
)
≥
δ
(
P
X
1
↑F
)

δ
(
{
−
δ
(
{
}
)
Search Nedrilad ::
Custom Search