Game Development Reference
In-Depth 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 right-hand
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 right-hand 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 left-hand side. This concludes the proof.
X j
Y 1 , for some j> 1. But then v
We will primarily use the sub-modularity 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 sub-modularity 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 )
|
δ (
{
|−|
δ (
{
}
)