离散数学综合练习及答案(2)

解：g 是双射，有反函数，就是 g 自己。g?1：a?b，b?a，c?d，d?c

g?g(x)：a?a，b?b，c?c，d?d h?g(x)：a?a，b?d，c?a，d?d

3、A、B都是有n个元素的集合，f：A?B的函数。 证明：f是单射 ? f是满射。

证明：?设f是单射，由于?x1?x2?A，f(x1)?f(x2)，所以ranf 有n 个元素， 又 ranf?B，而 B 也只有 n 个元素，所以 ranf?B

? 设f是满射，若 f 不是单射，则 ?x1?x2?A，f(x1)?f(x2)， 由于 A 中只有 n 个元素，所以 ranf?B，与 ranf?B 矛盾。

《离散数学》综合练习?三?参考答案

代数系统

一、判断题 1、｛0，?1，?2，…，?n｝对普通加法封闭。 （F） 2、在非负整数集Z+上定义运算·，x·y = min｛x，y｝，1是运算的幺元。（T） 3、实数集与普通乘法构成的代数系统中每个元素都有逆元素。 （F） 4、在代数系统?Z，+，0?中，0是零元。 （F） 5、非负整数集Z+与普通加法?构成的代数系统是群。 （F） 6、M是n阶可逆矩阵的集合，×是矩阵乘法，?M，×?是群。 （T） 7、循环群的子群是循环群。 （T） 8、代数系统?Z，+?是代数系统?R*，+?的子代数。 （F） 二、填空题

1、A =｛x | x = 3n ，n?N｝，对 乘法 运算封闭。 2、?R*，+?构成的代数系统是 半群 。 3、在代数系统?Z，+，0?中，0是 单位 元。 4、F =｛f | f：A?A｝，o为函数的复合运算，?F，o?的单位元是 恒等函数 。 5、f、g都是从A到A的双射，(fog)－1 = g－1of－1 。

6、在代数系统?S，*?中，元素a、b都有逆元，则?a－1?－1= a ，?a*b?－1=b－1*a－1 。 7、循环群有 生成 元，使循环群中元素都是该元素的方幂。

8、V1=?S1，o?，V2=?S2，*?都有幺元，?是V1到V2的同态，则?把V1中的单 位元映射到 V2中的单位元 。 三、解答题

＋

1、Q是正有理数集，×是普通乘法，?Q+，×?是否是半群、独异点、群？ 解：普通乘法有结合律，单位元是 1 ，但 0 没有逆元，?Q+，×?是独异点。 2、实数集R上的运算 * ，a*b=a＋b＋a×b，＋是普通加法，×是普通乘法。

验证：?R，*?只能是独异点。

解： ?a，b，c? R ?a*b?*c = ?a＋b＋a×b? * c = ?a＋b＋a×b?＋c＋?a＋b＋a×b?×c = a＋b＋c＋a×b＋a×c＋b×c＋a×b×c a*?b*c? = a* ?b＋c＋b×c? = a+?b＋c＋b×c?+a×?b＋c＋b×c? = a＋b＋c＋a×b＋a×c＋b×c＋a×b×c 运算 * 有结合律

由于运算 * 有交换律，设 e 是单位元。?a ? R a*e = a＋e＋a×e = a，?1+ a ?×e = 0 ，e = 0

－1－1

设 a 是 * a 的逆元，a * a = a－1 + a + a－1 × a = 0

－1

?1+ a ?a =－a ，当 a ? －1时，a 有逆元。 a = －1 无逆元，所以 ?Q+，×?是独异点。

3、实数集R上的运算 * ，a*b=a＋b －2，＋是普通加法，?是普通减法。

?R，*?是否是群？

解： ?a，b，c ? R，

?a*b?*c = ?a＋b－2? * c = ?a＋b－2?＋c－2 = a＋b＋c－4 a*?b*c? = a * ?c＋b－2? = a＋?b＋c－2?－2 = a＋b＋c－4 运算 * 有结合律

由于运算 * 有交换律，设 e 是单位元。?a ? R a*e = a＋e－2 = a，e－2 = 0 ，e = 2

设 a－1 是 * a 的逆元，a－1 * a = a－1 + a －2 = 2 a－1 = 4－a

所以 ?R，*? 是群。

四、求8阶循环群｛e，a，a2，…，a7｝的各阶子群。 解：一阶子群｛e｝

二阶子群｛e，a4｝

四阶子群｛e，a2，a4，a6｝ 八阶子群｛e，a，a2，…，a7｝

五、设代数系统〈A ，*〉有单位元，代数系统〈B ，?〉无单位元。 证明：这两个代数系统不同构。 证明：若〈A ，*〉，〈B ，?〉同构，则存在同构映射?，又设 e 是〈A ，*〉 的单位元，则 ?? e ? 是〈B ，?〉中的单位元，与〈B ，?〉无单位元矛盾。

《离散数学》综合练习?四?参考答案

图论

一、判断题

1、?2，2，5，2，1，3?可以构成图的度数序列。 （ F ） 2、n阶无向完全图的边数为n?n－1?。 （ F ） 3、生成子图与母图有相同的边集。 （ F ） 4、最小生成树是不唯一的。 （ T ） 5、有向完全图是强连通图。 （ T ） 二、填空题

1、顶点和边都不相同的通路，称为 初级通路 。 2、无向树有m个树枝，则顶点数为 m +1 。

3、无向图顶点之间的连通关系具有自反性、 对称 性、 传递 性， 是 等价 关系。

(3) 4、A是有向图D的邻接矩阵，若A3中的元素aij?2，则

顶点vi到vj 长度为 3 的通路有 2 条 。

5、A是有向图D的邻接矩阵，Bk=A+A2+…+Ak中元素bij?0，则顶点vi到 vj 可达 。 三、解答题 1、在图1中

（1）求邻接矩阵A；

（2）计算A2、A3、A4； （3）求B4=A+A2+A3+A4；

（4）v1到v2长度为2、3的通路各有多少条？ （5）v1到v2长度小于等于4的通路有多少条？ 解：

??0101?（1）A??0011???

?0101

? ???0100??

??0111??0212??（2）A2??0201????01??0?0111?，A3??22??，A4??0???0011???0212????0201?0?????0??0747?（3）B0747?4=A+A2+A3+A4?????0747?

??0434???（4）v1到v2长度为2、3的通路分别有1、2条 （5）v1到v2长度小于等于4的通路有7条

323?413??323? 122????0100????0011?

2、有向图G的邻接矩阵A?? ?1101

???1000???

（1）画出这个有向图； （2）求A2；

（3）G中长度为2的回路有多少条？

（4）G中v2到v1长度小于等于2的通路有多少条？

(2)（5）A2中的元素a31说明什么？

解：（1）画出这个有向图；

（2）

?0?02?A?AA??1??1?101001000??0??1??01??1??0????1101001000??0??1??2??1?1???0???0011110101??1?1??0??

（3）G中长度为2的回路有2条

（4）G中v2到v1长度小于等于2的通路有2条

(2)（5）A2中的元素a31说明v3到v1长度等于2的通路有1条

四、特殊图

判别下列各图是否是欧拉图和哈密尔顿图，说明理由。

（1） （2） （3） 解：

?1? 只是哈密尔顿图，aefbcghda 是哈密尔顿回路 ?2??3?是欧拉图，顶点度数都是偶数

?2??3?也是哈密尔顿图 abcgdfea、abcdefghija 分别是哈密尔顿回路

五、树

1、求下列各图的最小生成树。

解：

w = 1+1+2+3 = 7 w = 1+2+4+4 = 11

2、求下列带权的最优二叉树，并求权数。 （1）3，4，5，6，7，8，9 （2）1，2，4，6，9，12 解：（1）3，4，5，6，7，8，9 3，4，5，6，7，8，9

5，6，7，7，8，9

7，7，8，9，11

8，9，11，14

11，14，17

17，25

42W =7+11+14+25+42=119

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学综合练习及答案(2)在线全文阅读。