König-Egervary theorem

The König-Egervary theorem states that in a finite matrix of 0’s and 1’s, the maximum numbers of 1’s such that no two are in a line, equals the minimum number of lines which collectively contain all the 1’s. Here line means row or column.

Take this matrix, for example,

\begin{bmatrix}1&0&0&0&0&1\\ 1&0&0&0&0&1\\ 0&1&0&0&0&1\\ 0&1&0&0&0&1\\ 1&0&1&1&1&0\\ \end{bmatrix}

Here the max and min numbers (always equal) are 4.

References

1 A. Chandra Babu, P. V. Ramakrishnan, “New Proofs of Konig-Egervary Theorem And Maximal Flow-Minimal Cut Capacity Theorem Using O. R. Techniques” Indian J. Pure Appl. Math. 22(11) (1991): 905 - 911

Title	König-Egervary theorem
Canonical name	KonigEgervaryTheorem
Date of creation	2013-03-22 16:33:47
Last modified on	2013-03-22 16:33:47
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	4
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 05A19
Synonym	Konig-Egervary theorem