R00110001
五、（10分）设A、B、C和D为任意集合，证明A－B×C＝A×C－B×C。
证明：因为x，y∈A－B×Cx∈A－B∧y∈Cx∈A∧xB∧y∈Cx∈A∧y∈C∧xB∨x∈A∧y∈C∧yCx∈A∧y∈C∧xB∨yCx∈A∧y∈C∧x∈B∧y∈Cx，y∈A×C∧x，yB×C
第2页共26页
f离散试卷及答案
x，y∈A×C－B×C所以，A－B×C＝A×C－B×C。
六、（10分）设f：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f、g和h。
－1－1－1
解因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。由hgf＝IA，得f＝hg；由fhg＝IB，得g＝fh；由gfh＝IC，得h＝gf。七、（15分）设G，是一代数系统，运算满足交换律和结合律，且ax＝ayx＝y，证明：若G有限，则G是一群。
－1－1－1
证明因G有限，不妨设G＝a1，a2，，a
。由ax＝ayx＝y得，若x≠y，则ax≠ay。于是可证，对任意的a∈G，有aG＝G。又因为运算满足交换律，所以aG＝G＝Ga。令e∈G使得ae＝a。对任意的b∈G，令ca＝b，则be＝cae＝cae＝ca＝b，再由运算满足交换律得eb＝b，所以e是关于运算的幺元。对任意a∈G，由aG＝G可知，存在b∈G使得ab＝e，再由运算满足交换律得ba＝e，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。八、（20分）（1）证明在
个结点的连通图G中，至少有
－1条边。
证明不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。设G中结点为v1、v2、、v
。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、、v
中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，v
必与v1、v2、、v
1中的某个结点相邻，得新边e
1，由此可见G中至少有
－1条边。
2（2）给定简单无向图G＝V，E，且V＝m，E＝
。试证：若
≥Cm1＋2，则G是哈密尔顿图。
2证明若
≥Cm。1＋2，则2
≥m－3m＋6（1）
2
若存在两个不相邻结点u、v使得du＋dv＜m，则有2
＝
wV
dw＜m＋m－2m－3＋m＝m－3m
2
＋6，与（1）矛盾。所以，对于G中任意两r