离散试卷及答案
(3) 求G的可达矩阵P； (4) 求G的强连通分图。 2. 求群?N8,?8?的所有子群及由元素5确定的各子群的左陪集，其中N8?{0,1,???,7}，?8是模8加法。
四、证明题（每小题10分，共40分）
1. 证明布尔恒等式：(a?b)?(a??c)?(b??c)?(a?b)?c。
2. 设R为实数集合，?和?为数的加法和乘法运算，对?a,b?R，a*b?a?b?a?b，
证明：?R,??为独异点。
3. 证明：若(n,m)简单无向图G满足m?1(n?1)(n?2)，则图G是连通图。 2f:G?G，使得对于?x?G有f(x)?a?x?a?1；
4. 设?G,??是一个群，a?G；定义一个映射
证明：
f是?G,??
安徽大学2007— 2008学年第 2 学期 《离散数学（下）》考试试卷（A卷）
一、单项选择题（每小题2分，共20分）
1.A； 2.C； 3.D； 4.D； 5.C； 6.B； 7.B； 8.B； 9.A； 10.A。 二、填空题（每小空2分，共20分）
1.0，1； 2.2，5； 3.3，5； 4.a，b； 5.n?1，n(n?1)/2。 三、解答题（第1小题12分，第2小题8分，共20分）
?0?01. (1) G的邻接矩阵A???0??0?0?0???0??0111??010?； 2分
101??010?222??0??020?0(4)；A???0202???020??0242??202?； 5分
040??202?(2)
A(2)121??0??101?0(3)；A???0020???101??0从v1到v4的长为2,3,4的路径的条数分别为1,2,2； 8分
?0?0(3) G的可达矩阵为P???0??0?0?0T(4) 因P?P???0??0111??111?； 10分
111??111?000??111?，故G的强连通分图的结点集为{v1}，{v2,v3,v4}。 12分
111??111?第 11 页 共 12 页
离散试卷及答案
2. ?N8,?8?的子群为：?{0},?8?，?{0,2,4,6},?8?，?{0,4},?8?，?N8,?8?； 4分
元素5确定的各子群的左陪集对应为：{5}，{1,3,5,7}，{1,5}，N8。 8分 四、证明题（每小题10分，共40分）
1. (a?b)?(a??c)?(b??c)?(a?b)?((a??b?)?c) 2分
?(a?b)?((a?b)??c)?((a?b)?(a?b)?)?((a?b)?c) 6分 ?1?((a?b)?c)?(a?b)?c。 10分
2. 因R对?和?运算封闭，故R对?运算封闭；对?x,y,z?R， 2分
(x*y)*z?(x?y?x?y)*z?x?y?xy?z?(x?y?xy)z?x?y?z?xy?xz?yz?xyz, x*(y*z)?x*(y?z?y?z)?x?y?z?yz?x(y?z?yz)?x?y?z?xy?xz?yz?xyz
故(x?y)?z?x?(y?z)，从而R上的?运算满足结合律； 6分
因对?x?R，0*x?0?x?0?x?x，x*0?x?0?x?0?x，故0为?运算的么元；
R,??为独异点。 10分
综合以上，?为R上的可结合的二元运算，且R关于?运算有么元，所以?3. 假设G有k(k因为k?2)个连通分图，则因G为简单无向图，故m?12(n?k)(n?k?1)， 4分
?2，所以0?n?k?n?2，0?n?k?1?n?1， 8分
121(n?k)(n?k?1)?12(n?1)(n?2)，这与m?2(n?1)(n?2)矛盾！
所以m?所以图G是连通图。 10分 4. 对?x1,x2?G，若
f(x1)?f(x2)，则a?x1?a?1?a?x2?a?1，故x1?x2，从而f为单射； 3分
?y?G，a?1?y?a?G且f(a?1?y?a)?y，因此?x?G，使f(x)?y，所以f为满射； 6分
?x,y?G，f(x?y)?a?(x?y)?a?1?(a?x?a?1)?(a?y?a?1)?f(x)?f(y)，故f所以
为同态； 9分
f是?G,??的群自同构。 10分
第 12 页 共 12 页