CODEWITHSUNDEEP
algorithmgraphgraph-theorybipartite
Yahooo C9Wuxii
Yahooo C9Wuxii

Reputation: 87

Graph to bipartite graph by removing edges (not more than edges/2) - algorithm?

so lets say we're given a graph and you're allowed to remove edges (not more than (original graph's edges)/2) until it's a bipartite graph.

Lets say we're given:

E={ (4, 1),( 1 ,2), (2 ,3),( 7, 2),( 1 ,5),( 8 ,4), (5 ,8),( 8, 9)}

and set of vertices:

V= { 1,2,3,4,5,6,7,8}

How one should solve this problem ? Is there any kind of algorithm that does this? Any kind of explanation would be appreciated.

Upvotes: 1

Views: 2039

Answers (1)

mcdowella
mcdowella

Reputation: 19601

Pick an arbitrary node as the first member of set A. If there is any node linked to it, pick one as the first member of set B. If not, pick any other node as the first member of set B.

Now you have two sets of nodes, A and B. Repeatedly pick a node not in either set. Count the number of edges linking that node to nodes in A and B. If there are more edges linking it to set A, erase the edges linking it to nodes in set B and put it in set B. Otherwise erase the edges linking it to nodes in set A and put it in set A. Note that you erase no more than half the edges linked to that node.

Upvotes: 1

Related Questions