Consider the following scenario.
Let A be the vertex moved from Set 1 to Set 2. Which means that A
had more edges within Set1 compared to those in Set 2. Now it is quite
possible that there might be an edge B in Set 2 which now has more
edges in Set2 than it had in Set 1. The increase for B might be more
than increase in A. This means that |E| bound on the number of
iterations is not accurate. if so, what is the criteria for exiting
this algorithm.
Thanks,
Naveen
On Oct 28, 9:46 pm, Gene <[EMAIL PROTECTED]> wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
