Bipartite graph

general
,
1

http://discuss.codechef.com/questions/26248/kmhamha-editorial

I am reading this editorial for solving vertex cover problem for bipartite graph. I am getting problem in a line where he divide edges in two set of vertex to reduce problem to a bipartite graph.
For example, if we have 4 demons standing at (1, 8), (5, 6), (3, 8), (5, 4), we will end with the following bipartite graph:

R = {1, 3, 5}
C = {4, 6, 8}
E = {(1, 8), (5, 6), (3, 8), (5, 4)}

What will happen if we have one more demon at position (4,6) ? Now how can we divide them into two different set of bipartite graph. Also how can we assign demon at position (0,0) in two set of bipartite graph.

Please help me to understand. Thanks! in advance.

2

It seems you have misunderstood the way in which we are going to apply the concept of bipartite graph in kmhamha. All rows are from 1 to max_vertex count and columns from 1 to max_vertex count. Then if we have a demon at (a, b) then what we do is create an edge from row vertex named a to column vertex named b (That is indirectly we are dividing the vertices into two sets and the edges are always between one element from one set to other element from the other set. There are no edges between vertices of the same set. Hence it’s a bipartite graph). Then the rest of the editorial is pretty much straight forward you can go on with it. Feel free to ask in case you are struck at any other point.

1 Like
3

If you have one more demon at position (4,6), you should add the node {4} to SET R **(**Since, node {4} is not present in first SET ie; (SET R)). So, now you have 4 nodes in SET R, 3 nodes in SET C & 5 bipartite edges. Since, node 4 is now present in both the sets ie; (SET R & SET C), obviously you have to give unique numbering to them. You can use map for this. Numbers in the same set can repeat, so do the numbering by using separate map for SET R and SET C.

For instance the above graph (before & after mapping) would look like this:

Before: SET R = {1,3,4,5}, SET C = {4,6,8}, E = {(1,8),(5,6),(3,8),(5,4),(4,6)};

After: SET R = {1,2,3,4}, SET C = {5,6,7}, E = {(1,7), (4,6), (2,7), (4,5), (3,6)}

Same thing can be with (0,0).

1 Like
4

Thanks that’s helps a lot.