Editing Maximum flow problem (section)

===Minimum path cover in directed acyclic graph===
Given a [[directed acyclic graph]] <math>G = (V, E)</math>, we are to find the minimum number of [[Path (graph theory)|vertex-disjoint paths]] to cover each vertex in <math>V</math>. We can construct a bipartite graph <math>G' = (V_\textrm{out} \cup V_\textrm{in}, E')</math> from <math>G</math>, where
# <math>V_\textrm{out} = \{ v_\textrm{out} \mid v \in V \land v \text{ has outgoing edge(s)} \}</math>
# <math>V_\textrm{in} = \{ v_\textrm{in} \mid v \in V \land v \text{ has incoming edge(s)} \}</math>
# <math>E' = \{(u_\textrm{out}, v_\textrm{in}) \in V_{out} \times V_{in} \mid (u, v) \in E \}</math>.

Then it can be shown that <math>G'</math> has a matching <math>M</math> of size <math>m</math> if and only if <math>G</math> has a vertex-disjoint path cover <math>C</math> containing <math>m</math> edges and <math>n-m</math> paths, where <math>n</math> is the number of vertices in <math>G</math>. Therefore, the problem can be solved by finding the maximum cardinality matching in <math>G'</math> instead.

Assume we have found a matching <math>M</math> of <math>G'</math>, and constructed the cover <math>C</math> from it. Intuitively, if two vertices <math>u_\mathrm{out}, v_\mathrm{in}</math> are matched in <math>M</math>, then the edge <math>(u, v)</math> is contained in <math>C</math>. Clearly the number of edges in <math>C</math> is <math>m</math>. To see that <math>C</math> is vertex-disjoint, consider the following:
# Each vertex <math>v_\textrm{out}</math> in <math>G'</math> can either be ''non-matched'' in <math>M</math>, in which case there are no edges leaving <math>v</math> in <math>C</math>; or it can be ''matched'', in which case there is exactly one edge leaving <math>v</math> in <math>C</math>. In either case, no more than one edge leaves any vertex <math>v</math> in <math>C</math>.
# Similarly for each vertex <math>v_\textrm{in}</math> in <math>G'</math> – if it is matched, there is a single incoming edge into <math>v</math> in <math>C</math>; otherwise <math>v</math> has no incoming edges in <math>C</math>.
Thus no vertex has two incoming or two outgoing edges in <math>C</math>, which means all paths in <math>C</math> are vertex-disjoint.

To show that the cover <math>C</math> has size <math>n-m</math>, we start with an empty cover and build it incrementally. To add a vertex <math>u</math> to the cover, we can either add it to an existing path, or create a new path of length zero starting at that vertex. The former case is applicable whenever either <math>(u,v) \in E</math> and some path in the cover starts at <math>v</math>, or <math>(v,u) \in E</math> and some path ends at <math>v</math>. The latter case is always applicable. In the former case, the total number of edges in the cover is increased by 1 and the number of paths stays the same; in the latter case the number of paths is increased and the number of edges stays the same. It is now clear that after covering all <math>n</math> vertices, the sum of the number of paths and edges in the cover is <math>n</math>. Therefore, if the number of edges in the cover is <math>m</math>, the number of paths is <math>n-m</math>.