3）无人收到自己帽子的情况数为，恰有一人收到自己帽子的情况数为
C(7,1)
。所以，至少有两人收到自己帽子的情况数为
第九章：
9、考虑带有禁止位的n*n棋盘，其中一个正整数p，使每一行和每一列恰有p个放个允许放车，证明，在棋盘上能够放置n个非攻击车
答：可写出这个棋盘对应的车-二分图G，显然G是p阶正则的，故由定理1可知，存在完美匹配。因此，在棋盘上能够放置n个非攻击车。
12、令$=（
问$有SDR么？如果没有，具有SDR的族中集合的最大个数是多少？ 答：因为|
故由定理2知$不存在SDR。 由于|
|+6-4=5
|=5<6 ），其中
根据定理3可知，族中有SDR的集合的最大个数是5。
26、应用延迟认可算法得出下列评定矩阵的稳定婚姻。
答：（1）女士优先：
1
P>=1阶正则的二分图G=（X,?,Y）总有完美匹配。 2
集族A=（）有SDR的充要条件是：对于任意k(1<=k<=n)以及从（1,2,…,n）中任意k个互异指标的选择，都有||>=k。 3
令A=（）为集Y的子集族，A中有SDR的最大子集个数等于表达式||+n-k对于任意k(1<=k<=n)以及从（1,2,…,n）中任意k个互异指标的选择的最小值。
1） A选a，B选a，C选b，D选c；a拒绝B。 2） B选b，b拒绝C。 3） C选c，c拒绝D。 4） D选a；a拒绝A。 5） A选b；b拒绝B。 6） B选c，c拒绝C。 7） C选a，a拒绝D。 8） D选b，b拒绝A。 9） A选c，c拒绝B。
10） B选d，没有拒绝发生。
故：稳定婚姻为：A??c, B??d, C??a, D??b （2）男士优先：
1）a选C，b选D，c选A，d选D；D拒绝b。 2）d选C，C拒绝d。 3）d选A，A拒绝d。
4）d选B，没有拒绝发生。
故：稳定婚姻为：a??C, b??D, C??A, b??D
附加题：
相关推荐：
loading