离散数学结构试题集

[6]

[5]

[4]

[1]

[4]

[4]

[5]

[3]

[5]

[4]

[6]

[2]

[6]

[3]

[1]

4. 考察代数系统，以下定义在I上的二元关系R是同余关系吗？如不是，找出反例。 1) ?R当且仅当（x<0∧y<0）∨(x?0∧y?0) 2) ?R当且仅当|x-y|<10

5. 考察代数系统，以下定义在I上的二元关系R是同余关系吗？如不是，找出反例。

1) ?R当且仅当（x=y=0）∨(x≠0∧y≠0) 2) ?R当且仅当x?y

五.证明题

1. 设A=｛a，b｝，〈A，*〉为半群，且a*a=b。证明：a*b=b*a 。

2. 定义I+上的两个二元运算为：

a*b=ab

a○b=ab a,b?I+ 证明：*对○是不可分配的。

3. 如果是半群，且*是可交换的，称是可交换半群。证明：如果S中有元素a,b， 使得a*a=a和b*b=b,则（a*b）*(a*b)=a*b。

4. 设是群，且|S|=2n，n?I+。证明：在S中至少存在a≠e，使得a*a=e，其中e为么元 。

5. 证明：如果f是由到的同态映射，g是由到的同态映射，那么，g 。f是由到的同态映射。

6. 设f是从群到的同态映射,则f是入射当且仅当Ker(f)={e}。其中e是G1中 的么元。

7. 设是一个独异点，且对于G中的每一个元素x都有x*x=e，其中e是么元，证明 是一个阿贝尔群。

8. 设是一个代数系统，且对于任意的a?A,有a★b=a,证明二元运算*对★时可分 配的。 第6章

一.填空题 二.选择题 三.判断题 四.计算题 五.证明题 第7章

一.填空题

1. 把（ ）的图叫做简单图。

2. 无向图具有一条欧拉路，当且仅当图是联通的，而且（ ）。

3. 把（ ）的图叫做完全图。

4. 把（ ）的图叫做连通图。

5. 如果一个连通图有m个结点，则它的完全关联矩阵的秩为（ ）。

6. 含有平行边的任何一个图叫做（ ）。

7. 给定图G,若存在一条路（ ），这条路叫做汉密 尔顿路。

8. 在一个含有n个节点的图中，度数为奇数节点的个数必为（ ）个。

9. 在含有n个节点的完全图中，其边数为（ ）。

10. 若图G只有一个连通分支，则G叫作（ ）。

11. 无回路的连通图又叫做（ ）。

12. 给定一个无孤立节点的图G，若存在一条路，经过图中每边一次仅且一次，则这条路叫做

（ ）。

13. G是具有n个节点的简单图，如果G中每对节点度数之和大于等于n，则G中存在一条（

）。

14. 设G=是一个无向图，如果能够把G的所有节点和边画在平面上，且使得任何两条边

出了端点之外没有其他的交点，就称G为（ ）。

15. 还有v个节点，e条边,r个面的连通平面图G,满足欧拉公式（ ）。

二.选择题

1. 如果一个连通图有m个结点，则它的完全关联矩阵的秩为（ ） A)m B)m+1 C)m-1 D)m/2

2. 一个有n个节点连通图至少有（ ）条边。 A)n B)n-1 C)n+1 D)(n-1)n/2