Theorem (Konig 1931,Egervary 1931) In a bipartite graph,the size of a maximum matching equals the size of a minimum vertex cover. B vertex cover: rows/columns covering all 1s A B A
1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. Theorem (König 1931, Egerváry 1931) A B A B rows/columns covering all 1s vertex cover: 1 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 0 0
Theorem (Konig 1931,Egervary 1931) In a bipartite graph,the size of a maximum matching equals the size of a minimum vertex cover. Konig-Egervary Theorem(matrix form) For any 0-1 matrix,the maximum number of independent 1's equals the minimum number of rows and columns required to cover all the 1's
In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. Theorem (König 1931, Egerváry 1931) For any 0-1 matrix, the maximum number of independent 1's equals the minimum number of rows and columns required to cover all the 1's. König-Egerváry Theorem (matrix form)
A:m×n0-1 matrix s:min of rows/columns covering all 1's r:max of independent 1's r≤S any r independent 1's requires r rows/columns to cover
A : m × n 0-1 matrix r : max # of independent 1’s s : min # of rows/columns covering all 1’s r ≤ s s r any r independent 1’s requires r rows/columns to cover
A:m×nO-1 matrix s min of rows/columns covering all 1's r:max of independent 1's r≥S min covering:s a rows b columns b A= Baxb Cax(n-b) D(m-a)xb 0 C has a independent 1's D has b independent 1's
A : m × n 0-1 matrix r ≥ s a b min covering: s = a rows + b columns A = Ba⇥b Ca⇥(nb) D(ma)⇥b 0 ⇥ C has a independent 1’s D has b independent 1’s r : max # of independent 1’s s : min # of rows/columns covering all 1’s
A has min covering:s a rows b columns Cax(n-b) 0 C has a independent 1's S:={0|C=1} S2 10 S1,S2,...Sa have a SDR otherwise 1≤II|≤a,UerS<IIl(Hal) C can be covered by (a-I)rows +Uier S columns
(a |I|) rows + ⇥ iI Si columns min covering: s = a rows + b columns A = Ba⇥b Ca⇥(nb) D(ma)⇥b 0 ⇥ C has a independent 1’s A has Si = {j | Cij = 1} S2 1 0 1 S1, S2, ..., Sa have a SDR otherwise ⇥1 |I| a, ⇥ iI Si < |I| C can be covered by (Hall)