173
By using k = 1 and k ≥ 2, we can show that the above inequality is not true.
If vol(A) ≤ vol(A) and d Ax < d Ax , the inequality (B.6) implies
vol(A) ≥ vol(A) − kd Ax − (c + k − 1)d Ax .
By applying it to (B.8), we get
(2c − 1)
2 (d Ax + d Ax )
(2k − 1)d Ax + (2k − 1)d Ax
≤
− kd Ax − (c + k − 1)d Ax )(c − 1)(d Ax − d Ax )
+
kd Ax + (c + k − 1)d Ax
2
+
kd Ax + (c + k − 1)d Ax
2
≤
kd Ax + (c + k − 1)d Ax
2
+
kd Ax + (c + k − 1)d Ax
(c + k − 1)d Ax + kd Ax
≤
(c + 2k − 1)d Ax + (c + 2k − 1)d Ax
kd Ax + (c + k − 1)d Ax
.
(B.10)
Similarly, the above inequality is not true either. Thus, if vol(A) ≤ vol(A), the inequality (B.8) does not hold. Similarly we can prove that, if vol(A) ≥ vol(A), the
inequality (B.8) is not true either. Thus, by contradiction, the assumption is not true.
In other words, there does not exist a minimum NCut which separates the versions
of any node into two different groups.
Similarly, there does not exist a minimum NCut which separates the versions
of any node into more than two different groups, since the variables in the unrelated
groups are constant. In more detail, considering the case that the versions of a node
x are separated into three groups – A 1 , A 2 and A 3 . The NCut value for group A 3 is
unchanged if we move any version of node between groups A 1 and A 2 . Based on the
above proof, when we move the versions of the node x from A 1 to A 2 or from A 2 to
A 1 , the NCut value will be reduced. Now the versions of the node x are separated
only in groups A 1 and A 3 , or A 2 and A 3 . Again, the NCut value will be reduced if
versions of the node are in a same group.
Therefore, there does not exist a minimum NCut which separates the different
versions of any node into different groups.