Hello everyone,I have just learnt bipartite graph and I thought to solve this question with that only.Before this I have never ever solved graph problems and this is my very first.Can anybody tell me whether my approach is right or wrong ?And if wrong what should I do to correct it.
P.S- I have seen people saying,It is classical DP problem and so.But I don't know single word about DP.So please help me with this using graphs only.Thank you
You're dividing the graph in levels, painting them alternately black and white, and then outputting the minimum among number of white nodes and black nodes. That approach is incorrect. Consider the following graph: 1->2, 1->3, 1->4, 4->5, 4->6, 4->7, 4->8. In your solution, there would be 5 black nodes and 3 white nodes, but the correct answer is 2 nodes (1 and 4).
A tree is a bipartite graph, so the minimum vertex cover is equivalent to the maximum flow (König's theorem). If you really want to solve this problem using bipartite matching (I find the DP version easier), first run a DFS to determine the color of each node, then add 2 extra nodes (the source and the sink), connect the source to all black nodes, the sink to all white nodes and set all edges' capacities to 1. Finally, perform a maximum flow algorithm and you're done.
I don't know maximum flow algorithm.Still I would love to know the reason for adding 2 extra nodes(source to black and sink to white).Thanks for your reply.Really appreciate that.
Flow always needs a source and a sink. If you're just learning graph theory, I don't recommend trying to learn max flow now. I'd recommend you to learn BFS and DFS first, then Dijkstra, MST, etc.. Flow should be among the last algorithms you learn, because it's one of the most complex.
Please point out the error int his approach. Solution