I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me it seems trivial.
The method of solving the problem says to convert the original bipartite graph into a network, by creating a Source and Sink vertices, directing all edges towards the Sink and setting all edges' capacity to 1. Then I should run Ford-Fulkerson. Fair enough.
My question is, can't I just do this linearly? (Obviously not, but I don't see why). The goal of the problem seems to be to find a maximum matching in a complete bipartite graph - i.e. the maximum number of edges between the two "sections" of the graph that do not share any vertices.
To illustrate, see this picture
- In the first graph the maximum matching will be 2 - any of the two vertices on the right may only be connected to a single vertex on the left. Since the edges are unweighted, it doesn't really matter which?
- Similarly in the second graph, the matching will again be just 2.
Can you tell me where am I thinking wrong? I don't understand where the complexity of the problem comes from.
And sorry if any of the terms were used incorrectly, I am not studying CS in English. Thanks