Matching Theory
Matching Theory
System of Distinct Representatives (Transversal) system of distinct representatives(SDR) for sets S1,S2,...,Sm distinct 1,22,...,m xi∈Sa 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 S;: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,.,xm∈Sm 曼 I{1,2,.,m}, UerS≥|{x|i∈IH≥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
S1:S2,...,Sm have a SDR VI C{1,2,...,m),Uier Si
S1, S2,...,Sm have a SDR ⇥I {1, 2,...,m}, ⇥ iI Si |I|. S1, S2,...,Sm have a SDR ⇥I {1, 2,...,m}, ⇥ iI Si |I|