We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates.
example
0 0 1 0
0 1 0 1
0 0 1 0
0 0 1 0
cover 3rd column and 2nd raw. so two plates.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $R=\{r_1, \cdots, r_n\}$ be the set of all rows. Let $C=\{c_1, \cdots, c_m\}$ be the set of all columns. If and only if the matrix entry at row $i$ and column $j$ is 1, we connect $r_i$ with $c_j$ with an edge. Now we have a bipartite graph $G=((R,C), V)$, since there is no edge between two rows nor between two columns.
A vertex cover of $G$ corresponds to a set of selected rows and columns such that each matrix entry of 1 is in at least one of selected rows or columns. So, the problem to find minimum number of covering plates is the same as determining the minimum vertex cover for graph $G$.
Thanks to Kőnig's theorem, for bipartite graph $G$, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover. So, the problem is shifted to find a a maximum-cardinality matching of $G$.
There are many efficient algorithms that finds a maximum-cardinality matching in a bipartite graph, such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. There are many existing implementations of them in various programming languages that can be easily searched.