On Oct 29, 8:26 pm, "[EMAIL PROTECTED]"
<[EMAIL PROTECTED]> wrote:
> 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!- Hide quoted text -
I think you're counting edges in the wrong place. Think only about
the edges that go from some vertex in Set1 to another vertex in Set2.
Each vertex move must increase the total number of such edges by at
least one (by definition of how you pick a vertex to move). Since you
can't increase this number more than |E| times (because at that point
_all_ the edges are between the 2 sets), you must eventually get to a
state where no more vertex moves are possble
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
