Why we use max-flow method to solve maximum bipartite matching?

Question

for example

there is A[0] and A[1] and B[0] and B[1]

LINK(A[0], B[0])

LINK(A[0], B[1])

LINK(A[1], B[0])

The maximum match is (A[0].B[1]) and (A[1],B[0])

but for max-flow finding method that we build a source behind A and sink after B

and the method will find a path every time it tries out there is a path

that: it first get A[0] pair with B[0]

then for Path B[0] to sink is used, that no path for A[1] pair B[0]

it definitely cannot solve this but I find textbooks, wikis, blogs and website just say that its result is the same as Maximum Bipartite Matching

PS

Let C(x,y) be x->y 's value,

by applying the alg,

1st iteration: set C(s,A[0]) = 0 ; set C(A[0],s) = 1 (reversing the flow)

and also, A[0] with B[0] , B[0] with t

2nd iteration: it find routes from s to t, only C(B[1],t) = 1

so, 2nd iteration find no point for connecting B[1]

Answer 1

Actually max-flow will be able to link the things correctly. There will be a second iteration where the flow from A[1] could go to B[0] while reversing the flow going in the link from A[0] to B[0].

You can look up the Ford-Fulkerson algorithm it can do that.

EDIT :

Assuming you start with a source node S (LINK(S,A0) and LINK(S,A1)) (and an ending node F) if you apply the algorithm on the first iteration you will end up with A0->B0 like you said. I'll go into details for the second iteration.

1) "S" ; T = {S} ; E = {}

• Label(A1) = {S+, 1}, T = {S A1}
• E = {S}

2) "A1" ; T = {S A1} ; E = {S}

• Label(B0) = {A1+, 1}, T = {S A1 B0}
• E = {S A1}

3) "B0" ; T = {S A1 B0} ; E = {S A1}

• Label(A0) = {B0-, 1} ; T = {S A1 B0 A0}
• E = {S A1 B0}

4) "A0" ; T = {S A1 B0 A0} ; E = {S A1 B0}

• Label(B1) = {A0+, 1} ; T = {S A1 B0 A0 B1}
• E = {S A1 B0 A0}
• Don't inspect "S" because it is already in T!

5) "B1" ; T = {S A1 B0 A0 B1}

• Label(F) = {B1+, 1} ; T = {S A1 B0 A0 B1 F}
• E = {S A1 B0 A0 B1}

And it's over, the flow is now maximised.