南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Matching Theory

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}, ￾ ￾ ⇥ i￾I 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}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|. S1, S2,...,Sm have a SDR ⇥I ￾ {1, 2,...,m}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|

Hall's Theorem (marriage theorem) S,S2,,Sm have a SDR←→ IC{1,2,,m,UerS≥lI

S1, S 2,...,Sm have a SDR have a SDR Hall’s Theorem (marriage theorem) ⇥I ￾ {1, 2,...,m}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|

Hall's Theorem(graph theory form) A bipartite graph G(U,V,E)has a matching of U lW(S)l≥ISI for all SCU matching:edge independent set MCE with no el,e2e M share a vertex W(S)={v|]u∈S,uweE V

Hall’s Theorem (graph theory form) A bipartite graph G(U,V,E) has a matching of U |N(S)| ≥ |S| for all S⊆U U V matching: edge independent set M⊆E with no e1,e2∈M share a vertex N(S) = {v | ∃u∈S, uv∈E}

Hall's Theorem (marriage theorem) I{1,2,,m},UerS≥I S1,S2:...,Sm have a SDR critical family:S1,S2,...,Sk<m k U i =k 2=1 Induction on m: m =1,trivial case.I:there is no critical family in S1,S2,...,S case.2:there is a critical family in S1,S2,...,Sm

S1, S 2,...,Sm have a SDR have a SDR Hall’s Theorem (marriage theorem) ⇥I ￾ {1, 2,...,m}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|. Induction on m : m =1, trivial case.1: there is no critical family in S1, S2, ..., Sm case.2: there is a critical family in S1, S2, ..., Sm critical family: S1, S2,...,Sk ￾ ￾ ￾ ￾ ￾ ⇥ k i=1 Si ￾ ￾ ￾ ￾ ￾ = k k < m

Hall's Theorem(marriage theorem) VI C {1,2,...,m},UierSi. S1,S2,...,Sm have a SDR case.I:there is no critical family in S1,S2,...,Sm I∈{1,2，，m}that |IlI take an arbitrary xE Sm as representative of Sm remove Si and x S;'=Sx}i=1,2,,m-1 I≤{1,2，，m-1},UerS≥I due to I.H.S1,...,Sm-1 have a SDR {1,...,m-1) 1,....m-1 and form a SDR for S1,S2,...,Sm

case.1: there is no critical family in S1, S2, ..., Sm take an arbitrary x∈Sm as representative of Sm remove Sm and x Si ’ = Si\{x} i = 1, 2, ..., m-1 ⌅I ⇥ {1, 2,...,m ￾ 1}, ￾ ￾ ⇥ i⇥I S￾ i ￾ ￾ ⇤ |I| ⇥I ￾ {1, 2,...,m} that |I| |I| due to I.H. S1, S 2,...,Sm have a SDR have a SDR Hall’s Theorem (marriage theorem) ⇥I ￾ {1, 2,...,m}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|. S⇥ 1,...,S⇥ m￾1 have a SDR {x1,...,xm￾1} x1,...,xm￾1 and x form a SDR for S1, S2, ..., Sm

Hall's Theorem(marriage theorem) Ic{1,2,.,m},UeS≥lI: S1,S2,...,Sm have a SDR case.2: there is a critical family in S1,S2,...Sm say|Sm-k+1U·USml=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-k}, Um-k+1S:UUieI Sik+ Uier S?≥II|

S1, S 2,...,Sm have a SDR have a SDR Hall’s Theorem (marriage theorem) ⇥I ￾ {1, 2,...,m}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|. case.2: there is a critical family in S1, S2, ..., Sm say k < m due to I.H. Sm-k+1,..., Sm have a SDR X={x1, ..., xk} |Sm￾k+1 ⇥ ··· ⇥ Sm| = k ⇤I ⇥ {1, 2,...,m ￾ k}, ￾ ￾ ⇥m i=m￾k+1 Si ￾ ⇥ i⇥I Si ￾ ￾ ￾ k + |I| ￾ |I| ￾ ￾ ⇥ i⇥I S￾ i ￾ ￾ Si ’ = Si\X i = 1, 2, ..., m-k