Matching Theory
Matching Theory
System of Distinct Representatives (Transversal) system of distinct representatives(SDR) for sets S1,S2,...,Sm distinct x1,c2,·,xm xi∈Si for i=1,2,...m
System of Distinct Representatives system of distinct representatives (SDR) for sets S1, S2,...,Sm distinct x1, x2,...,xm xi Si for i =1, 2, ..., m (Transversal)
Marriage Problem Does there exist an SDR for S1,S2,.,Sm? m girls Si:boys that girl i likes "Is there a way of marrying these m girls?
Marriage Problem Does there exist an SDR for S1, S2,...,Sm ? m girls Si : boys that girl i likes “Is there a way of marrying these m girls?
S1,S2,...,Sm have a SDR dinstinct x1∈S1,c2∈S2,.,cm∈Sm VIC{1,2,.,m, UcS≥|{x|i∈Il≥I. distinct
S1, S2,...,Sm have a SDR ⇥ dinstinct x1 S1, x2 S2,...,xm Sm ⇥I {1, 2,...,m}, ⇥ iI Si |{x |I|. i | i ⇥ I}| distinct
S,S2,.,Sm have a SDR→ VI C{1,2,...,m},Uier S:
S1, S2,...,Sm have a SDR ⇥I {1, 2,...,m}, ⇥ iI Si |I|