= Solution
A cut is a partition $(S,T)$ of the vertices with the source in $S$ and sink in $T$; its capacity is the sum of capacities of directed edges from $S$ to $T$. The <max-flow min-cut theorem> says that maximum flow value equals minimum cut capacity. With integral capacities, there is an <integral max-flow theorem> attaining the maximum.
Construct a <bipartite graph> with one vertex for each row and column and an edge $r_i\to c_j$ whenever $A_{ij}=1$. Add source-to-row and column-to-sink edges of capacity $1$, and give row-to-column edges infinite capacity. An integral flow is precisely a set of independent $1$s, so its maximum value is the largest such set.
A finite-capacity cut places some rows on the sink side and some columns on the source side; these lines cover every $1$, since an uncovered row-to-column edge would cross the cut with infinite capacity. Its capacity is the number of selected lines. Conversely every line cover defines such a cut. Max-flow min-cut therefore proves \b[the maximum number of independent $1$s equals the minimum number of covering lines], the matrix form of <Kőnig's theorem for bipartite matching>.
Back to article page
