
Hi,
I have got a problem like this:
We are given a bipartite graph. For e.g.
A1 B1 A2 B2 A3 B3 A4
And here is the adjacency list representation (assume graph is bidirectional)
B1 > A2, A3 B2 > A2, A3, A4 B3 > A1
Final result should be that all nodes in the left side (As) have exactly 1 incoming edge and at the same time  we need to minimize the maximum number of edges that need to go out of individual Bs nodes. In this case the answer would be:
B3 can connect to A1 B2 can connect to A2, A4 B1 can connect to A3
So here the maximum number of edges that need to out of a single Bs node is 2. We cannot cover all As and at the same time have a B node not having 2 edges going out of it to cover As.
Another example:
A1 B1 A2 B2 A3 B3 A4 B4
B1 > A1, A2, A3 B2 > A1, A2, A3, A4 B3 > A1, A2, A3 B4 > A1, A2, A3
In this case the answer would be:
B1 can connect to A1 B2 can connect to A4 B3 can connect to A3 B2 can connect to A2
This way we will cover all the As exactly once and at the same time we have minimized the maximum number of edges that need to go out of individual B's. So here the maximum number of edges that need to out of a single Bs node is 1.
Another example:
A1 B1 A2 B2 A3 B3 A4 A5 A6
B1 > A6 B2 > A1, A2, A3, A4, A5 B3 >
In this case the answer would be 5 i.e. the maximum number of edges that need to go out of a single Bs is 5. Can't do less than that.
I have implemented basic ford fulkerson algorithm and I know this is also network flow but don't know how to relate to it.
It will be great if someone can give some hint about the graph.
Thanks 