2024年4月1日发(作者：查惜)
Homework 6
13．Let A={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}
Determine the number of different SDR’s that A has. Generalize to n
sets.
Solution: When we choose 1 in A
1
, if we choose 3 in A
2
, we can choose
4 only in A
3
, we can choose 5 only in A
4
, and we can choose 6 only in A
5
,
however, we can choose 1 only in A
6
，
it will contract with 1 in A
1
.
Hence, we can choose only 2 in A
2
if we choose 1 in A
1
, 3 in A
3
, 4 in
A
4
, 5 in A
5
, 6 in A
6.
When we choose 2 in A
1
, we can only choose 3 in A
3
, 4 in A
4
, 5 in A
5
,
1 in A
1
. Hence, there are only two SDRs in A.
That is SDR
1
={1,2,3,4,5,6}and SDR
2
={2,3,4,5,6,1}
Similarity, we can generalize to n sets. There are only two SDRs in
n-sets the same.
That is SDR
1
={1,2,…,n} and SDR
2
={2,3,4,…,n,1}
23. Use the deferred acceptance algorithm to obtain both the
women-optimal and men-optimal stable complete marriage for the
preferential ranking matrix.
Conclude that for the given preferential ranking matrix there is only
one stable complete marriage.
a b c d
2024年4月1日发(作者：查惜)
Homework 6
13．Let A={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}
Determine the number of different SDR’s that A has. Generalize to n
sets.
Solution: When we choose 1 in A
1
, if we choose 3 in A
2
, we can choose
4 only in A
3
, we can choose 5 only in A
4
, and we can choose 6 only in A
5
,
however, we can choose 1 only in A
6
，
it will contract with 1 in A
1
.
Hence, we can choose only 2 in A
2
if we choose 1 in A
1
, 3 in A
3
, 4 in
A
4
, 5 in A
5
, 6 in A
6.
When we choose 2 in A
1
, we can only choose 3 in A
3
, 4 in A
4
, 5 in A
5
,
1 in A
1
. Hence, there are only two SDRs in A.
That is SDR
1
={1,2,3,4,5,6}and SDR
2
={2,3,4,5,6,1}
Similarity, we can generalize to n sets. There are only two SDRs in
n-sets the same.
That is SDR
1
={1,2,…,n} and SDR
2
={2,3,4,…,n,1}
23. Use the deferred acceptance algorithm to obtain both the
women-optimal and men-optimal stable complete marriage for the
preferential ranking matrix.
Conclude that for the given preferential ranking matrix there is only
one stable complete marriage.
a b c d