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: 0 0 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 natrix s:min of rows/columns covering all 1's r:max of independent 1's 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×n0-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 4=b%。。 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 A- 0 C has a independent 1's S:={0|C=1} S2 S1,S2,....Sa have a SDR otherwise 1≤II|≤a,UcuS<I1(Hall) 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)