Editing Maximum flow problem (section)

===Maximum cardinality bipartite matching===
[[File:Maximum bipartite matching to max flow.svg|thumb|right|Fig. 4.3.1. Transformation of a maximum bipartite matching problem into a maximum flow problem]]
Given a [[bipartite graph]] <math>G = (X \cup Y, E)</math>, we are to find a [[maximum cardinality matching]] in <math>G</math>, that is a matching that contains the largest possible number of edges. This problem can be transformed into a maximum flow problem by constructing a network <math>N = (X \cup Y \cup \{s,t\}, E')</math>, where
# <math>E'</math> contains the edges in <math>G</math> directed from <math>X</math> to <math>Y</math>.
# <math>(s,x) \in E'</math> for each <math>x \in X</math> and <math>(y,t) \in E'</math> for each <math>y \in Y</math>.
# <math>c(e) = 1</math> for each <math>e \in E'</math> (See Fig. 4.3.1).

Then the value of the maximum flow in <math>N</math> is equal to the size of the maximum matching in <math>G</math>, and a maximum cardinality matching can be found by taking those edges that have flow <math>1</math> in an integral max-flow.