On Oct 28, 2:02 pm, "[EMAIL PROTECTED]"
<[EMAIL PROTECTED]> wrote:
> I am trying to find the proof for the following problem from CLR.
>
> Prove that a undirected graph with no self edges can be divided into
> two groups such that for every node,atleast half of the nodes it is
> adjacent to, are in a different group than the node itself.
>
> Solutions/hints will be appreciated.

One proof is to show the following algorithm must work:  Put the
vertices arbitrarily into two sets.  As long as you can move a vertex
from one set to the other and increase the number of edges between the
two sets, do that.  This criterion for moving a vertex is equivalent
to saying that the vertex thas more neighbors in its own set than in
the other.  After moving, the situation is reversed: more neighbors
are in the opposite set.  Now the algorithm must terminate after
moving vertices at most |E| times.  This is because you are increasing
the number of edges between sets by one with each move, and you can't
do better than getting all the edges!


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to