CODEWITHSUNDEEP
graphbipartite
user3080029
user3080029

Reputation: 563

How to remove edges to make a graph bipartite?

I have a graph which may ( or may not ) contain a set of edges that make it bipartite. How can I discover if such a set exists?

http://tinypic.com/view.php?pic=28ama2h&s=5#.Uspc5uLcPu0

Will removing all edges in a particular level during BFS traversal help?

Upvotes: 2

Views: 1796

Answers (1)

Draugr
Draugr

Reputation: 436

Since any bipartite graph is also 2-colourable you can use any algorithm that checks for this trait. You could e.g. do it with BFS using a backtracking based algorithm. Generally speaking it could look like this:

Assume if the graph is bipartite the vertexes can be divided into groups A and B. Choose a source vertex, colour it red (group A). Then colour all neighbouring vertices blue (group B), and then those neighbours' neighbours red. If during the colouring process you find a neighbour that has the same colour as the current vertex it is not 2-colourable and thus not bipartite. This might not cover all specifics, but you should get the idea.

Upvotes: 1

Related Questions