Given a network with a source $A$, a sink $B$, and capacities on directed edges, define a cut. What is meant by the capacity of a cut? State the max-flow min-cut theorem. If the capacities of edges are integral, what can be said about the maximum flow?

Consider an $m \times n$ matrix $A$ in which each entry is either 0 or 1 . We say that a set of lines (rows or columns of the matrix) covers the matrix if each 1 belongs to some line of the set. We say that a set of 1 's is independent if no pair of 1 's of the set lie in the same line. Use the max-flow min-cut theorem to show that the maximal number of independent 1's equals the minimum number of lines that cover the matrix.