计算机应用数学-（组合数学）-答案哈工大

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

附加题：