Bipartite matching: existence of a perfect matching.
Questions: does there exist a perfect matching? Find a perfect matching
or argue that none exists.
Graph as a 0-1 matrix (actually part of the adjacency matrix).
There are two definitions: definition of permanent and definition of determinant.
No perfect matching Þ zero determinant
(not viceversa). Hence a non zero determinant implies existence of perfect
matching. What if det=0?
|