两门课程，则这两点间有边（其图如右），问至少需几天？
83
f离散数学试卷（十三）
2、用washall方法求图
的可达矩阵，并判断图的连通性。分）（8
3、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分）4、用Huffma
算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。若传递a，b，c，d，e，f的频率分别为2，3，5，7，8，9求传输它的最佳前缀码。分）（8
一、填空10（每小题2分）（1、1，不存在；2、e≠θ；3、ab∈G有ababaabb；4、
e1v1v2
v3
1100
e2
1010
e3
1001
e4
0011
e5
0110
v4
5、它不包含与K33或K5在2度结点内同构的子图。
二、选择10（每小题2分）（题目答案1A，D2B3C4D5A
三、判断10题目答案1Y2Y3N4N5N
84
f离散数学试卷（十三）
四、证明381、分）证明：（8（1）设abc∈A，b是a的右逆元，c是b的右逆元，由于babbeb，
ebcbabcbabcbaeba
所以b是a的左逆元。（2）设元素a有两个逆元b、c，那么
bbebacbacecc
a的逆元是唯一的。2、（12分）证明：乘Q∨，∧，在A上封闭，群abc∈A
∴
运算☆在A上也封闭。
a☆b☆ca∧b∨a∧b☆ca∧b∨a∧b∧c∨a∧b∨a∧b∧ca∧b∧c∨a∧b∧c∨a∨b∧a∨b∧ca∧b∧c∨a∧b∧c∨a∧b∨a∧b∧ca∧b∧c∨a∧b∧c∨a∧b∧c∨a∧b∧c同理可得a☆b☆ca∧b∧c∨a∧b∧c∨a∧b∧c∨a∧b∧c
∴a☆b☆ca☆b☆c
即☆满足结合性。
幺a∈Aa☆00☆a0∧a∨0∧a0∨1∧a0∨aa故全下界0是A中关于运算☆的幺元。逆a∈Aa☆aa∧a∨a∧a0∨00即A中的每一个元素以其自身为逆元。交a☆ba∧b∨a∧bb∧a∨b∧ab☆a即运算☆具有可交换性。所以A☆是Abel群。3、10分证明设A是一环且fA是关于同态映射f的同态象。
85
f离散数学试卷（十三）
由A是Abel群，易证fA也是Abel群。
A是半群，易证fA也是半群。
现只需证：r