结论：r?s
2、证明一个关系R的对称闭包的自反闭包和它的自反闭包的对称闭包是相同的，即
r(s(R))?s(r(R))，
其中r(R)，s(R)分别表示关系R的自反闭包和传递闭包。
3、设n阶m条边的无向图G中，m?n?1，证明G中存在顶点v：d(v)≥3。 4、若?G,??是群，u?G，定义G中的运算“?”为：a?b?a?u?1?b，对?a,b?G
证明?G,??为含幺半群。
四、应用题（共4分，任选一题，多选不加分）
1、一个商人骑一头驴要穿越1000公里长的沙漠，去卖3000根胡萝卜。已知驴一次性可驮1000根胡萝卜，但每走1公里又要吃掉1根胡萝卜。问：商人最多可卖出多少胡萝卜？(4分)
得分 2、一个多米诺骨牌是一个由两个正方体组成的长方体，每个正方体上用数字0，1，?，6标注，一套多米诺骨牌如下图所示。一个多米诺骨牌的两个正方体上可以有相同的数字，请说明一套多米诺骨牌可以放在一个回路里，并且相邻两张骨牌连接处数字相同。(4分)
6
装订线
解： （1）R的集合表达式： R?{?3,1?,?4,1?,?4,2?}
R的关系图： R的关系矩阵:
??0000??0000??1?1000?? 2 3 4
?1100??
（2）R的自反闭包r(R)关系图： 对称闭包s(R)关系图：
1 2 3 4
1 2 3 4
传递闭包t(R)关系图：
1 2 3 4
解：首先将各边的权重按小到大排序：1,2,3,4,5,6,7,8,9,10
然后使用避圈法得到如下最小生成树，其总权重为1+2+4+6+8+10=31
V2 V4 1 8 V1 2 4 V10 6 V7 V3 6 V5
华南农业大学期末考试参考答案（A卷）
2012-2013学年第 一 学期 考试科目： 离散结构
7
一、选择题（本大题共 25 小题，每小题 2 分，共 50 分）
1 6 11 16 21
二、计算题：（本大题共 5 个小题，每题 5 分，共 25 分） 1、解： （1）R的集合表达式： R?{?3,1?,?4,1?,?4,2?}
R的关系图： R的关系矩阵:
得分 A D A A C 2 7 12 17 22 D B A D B 3 8 13 18 23 C B B B D 4 9 14 19 24 D B D D B 5 10 15 20 25 C C B C B 得分 1
2 3 4
?0?0??1??1000100000?0?? 0??0?
（2）R的自反闭包r(R)关系图： 对称闭包s(R)关系图：
1 2 3 4
1 2 3 4
传递闭包t(R)关系图：
1 2 3 4
2、 解：(1)用Huffman算法求以频率(乘以100)为权的最优2元树. 将权按小到大顺序
8
排列：
wg=5,wf=5,we=10,wd=10,wc=15,wb=20,wa=35.得到如下最优2元树：
0
40
装100
1
60
0 20 0 10
1 we=10
1
wf=5
1 wb=20
0 wd=10
25
0 1 wa=35
1 wc=15
订0 wg=5
线(2)如上图所示，得到各字母的前缀码：a:11,b:01,c:101,d:100,e:001,f:0001,g:0000 总权重W(T)＝255
3、解：首先将各边的权重按小到大排序：1,2,3,4,5,6,7,8,9,10
然后使用避圈法得到如下最小生成树，其总权重为1+2+4+6+8+10=31
1 V1 V2 2 V3 4 6 V4 8 V6 10 V7 V5
4、
5、
v a b c d e 9 f g z r 0 1 2 3 4 5 6 7 8
三、证明题：（6+5+5+5，共 21 分）
1、证明：①r （前提引入） ②p??r （前提） ③p （①②析取三段论） ④p?(q?s) （前提） ⑤(q?s) （③④假言推理） ⑥q （前提） ⑦ s （⑤⑥假言推理）
2、证明：对于任意A上关系R来说，都有r(R)?R?IA，s(R)?R?R 左边=r(R?R)?(R?R)?IA 右边=s(R?IA)=(R?IA)?(R?IA)?1?1?1?10 0 4 4 4/a 4 3 3/a 3 ∞ 6 6 6/c 6 ∞ 9 9 7 7/d 7 ∞ ∞ ∞ 11 11 11/d 11 ∞ ∞ ∞ ∞ 12 12 12/e 12 ∞ ∞ ∞ ∞ ∞ 18 16 16/g 16 得分
?(R?IA)?(IA)?1?R?1=(R?IA)?IA?R?1?(R?R?1)?IA=左边
3、证：用反证法，假设不存在顶点度数大于等于3，则?v?V(G),均有d(v)?2，由
握手定理有：
2m?2(n?1)?2n?2??d(vi)?2n，矛盾！所以G中存在顶点v：d(v)≥3
10
华南农业大学 离散数学 期末考试2012试卷 2013-01-08
