168
Appendix B. NCut consistency with multiple versions of each node
Similarly by moving x V 1 to A, we get
NCut(A − x V 1 , A + x V 1 ) =
cut(A − x V 1 , A + x V 1 ) ∗ vol(V )
vol(A − x V 1 )vol(A + x V 1 )
=
cut(A, A) − d V 2x − 2p
∗ vol(V )
(vol(A) − 2d V 1x − d V 2x )(vol(A) + 2d V 1x + d V 2x )
.
Since the NCut(A, A) is the minimum,
NCut(A, A) ≤ NCut(A + x V 2 , A − x V 2 )
=⇒
cut(A, A)
vol(A)vol(A)
≤
cut(A, A) − d V 1x − 2q
(vol(A) + d V 1x + 2d V 2x )(vol(A) − d V 1x − 2d V 2x )
(B.1)
and
NCut(A, A) ≤ NCut(A − x V 1 , A + x V 1 )
=⇒
cut(A, A)
vol(A)vol(A)
≤
cut(A, A) − d V 2x − 2p
(vol(A) − 2d V 1x − d V 2x )(vol(A) + 2d V 1x + d V 2x )
.
(B.2)
Let cut(B, B) be any cut where every pair of V1 and V2 copies are in the same group.
Thus,
cut(B, B) ≤





∑
i∈B
(d V 1i + d V 2i )
∑
i∈B
(d V 1i + d V 2i )
and vol(B) = ∑
i∈B
(t V 1i + t V 2i ) = ∑
i∈B
3 ∗ (d V 1i + d V 2i ),
vol(B) = ∑
i∈B
(t V 1i + t V 2i ) = ∑
i∈B
3 ∗ (d V 1i + d V 2i ).
Thus, NCut(B, B) =
cut(B, B)
vol(B)
+
cut(B, B)
vol(B)
≤
2
3
.
Since the NCut(A, A) is the minimum,
NCut(A, A) =
cut(A, A) ∗ vol(V )
vol(A)vol(A)
≤
2
3
,
vol(V ) ≥ 6 ∗ (d V 1x + d V 2x )
=⇒ 9cut(A, A)(d V 1x + d V 2x ) ≤ vol(A)vol(A).
(B.3)
(B.1) implies
cut(A, A)
vol(A)vol(A)
≤
cut(A, A) − d V 1x
(vol(A) + d V 1x + 2d V 2x )(vol(A) − d V 1x − 2d V 2x )
,
=⇒ d V 1x vol(A)vol(A)
≤ cut(A, A)
vol(A)(d V 1x + 2d V 2x ) − vol(A)(d V 1x + 2d V 2x ) + (d V 1x + 2d V 2x )
2
.