Hall's Theorem(marriage theorem) VI C {1,2,...,m},Uier Si. S1,S2,...,Sm have a SDR case.2: there is a critical family in S1,S2,...,Sm say Sm-k+1U...USm=k k<m due to I.H.Sm-+1,...,Sm have a SDR X=x1,...,xx S-SX i=1,2,,m-k I∈{1,2，，m-kh,JiEI S≥II due to I.H. S1,...,Smk have a SDR Y={y1,...,Um-k X and Y form a SDR for S1,S2,...Sm
S1, S 2,...,Sm have a SDR have a SDR Hall’s Theorem (marriage theorem) ⇥I {1, 2,...,m}, ⇥ iI Si |I|. case.2: there is a critical family in S1, S2, ..., Sm say k < m due to I.H. |Smk+1 ⇥ ··· ⇥ Sm| = k ⇤I ⇥ {1, 2,...,m k}, |I| ⇥ i⇥I S i due to I.H. X and Y form a SDR for S1, S2, ..., Sm Sm-k+1,..., Sm have a SDR X={x1, ..., xk} Si ’ = Si\X i = 1, 2, ..., m-k S⇥ 1,...,S⇥ mk have a SDR Y = {y1,...,ymk}
Hall's Theorem(marriage theorem) S1,S2,.,Sm have a SDR→ I{1,2,,m以，UerS≥II
S1, S 2,...,Sm have a SDR have a SDR Hall’s Theorem (marriage theorem) ⇥I {1, 2,...,m}, ⇥ iI Si |I|
Min-Max Theorems Konig-Egervary theorem:in bipartite graph min vertex cover max matching Menger's theorem:in graph min vertex-cut max vertex-disjoint paths Dilworth's theorem:in poset min chain-decomposition max antichain
Min-Max Theorems • König-Egerváry theorem: in bipartite graph min vertex cover = max matching • Menger’s theorem: in graph min vertex-cut = max vertex-disjoint paths • Dilworth’s theorem: in poset min chain-decomposition = max antichain