哈工大深圳研究生院组合数学部分作业题答案习题课6-8.pdfVIP

Homework6

13．LetA={A1,A2,A3,A4,A5,A6}where

A1={1,2}A2={2,3}A3={3,4}

A4={4,5}A5={5,6}A6={6,1}

DeterminethenumberofdifferentSDR’sthatAhas.Generalizeton

sets.

Solution:Whenwechoose1inA,ifwechoose3inA,wecanchoose

12

4onlyinA,wecanchoose5onlyinA,andwecanchoose6onlyinA,

345

however,wecanchoose1onlyinA6，itwillcontractwith1inA1.

Hence,wecanchooseonly2inAifwechoose1inA,3inA,4in

213

A,5inA,6inA

456.

Whenwechoose2inA,wecanonlychoose3inA,4inA,5inA,

1345

1inA1.Hence,thereareonlytwoSDRsinA.

ThatisSDR={1,2,3,4,5,6}andSDR={2,3,4,5,6,1}

12

Similarity,wecangeneralizetonsets.ThereareonlytwoSDRsin

n-setsthesame.

ThatisSDR={1,2,…,n}andSDR={2,3,4,…,n,1}

12

23.Usethedeferredacceptancealgorithmtoobtainboththe

women-optimalandmen-optimalstablecompletemarriageforthe

preferentialrankingmatrix.

Concludethatforthegivenpreferentialrankingmatrixthereisonly

onestablecompletemarriage.

abcd

1,32,33,24,3

�1,44,13,32,2�

2,21,43,44,1

4,12,23,1