离散数学结构试题集(10)

[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

3. 关联同一节点的两条边叫做（ ）。 A）环 B)回路 C)圈 D）邻接边

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

A）欧拉图 B）汉米尔顿图 C）连通图 D）多重图

5. 在一个含有n个节点的图中，度数为奇数节点的个数必为（ ）个。 A）2 B）n-1 C）偶数 D）奇数

6. 在任何有向图中，所有节点的出度之和等于（ ）。

A)所有节点的入度之和 B）所有节点入度之和的2倍 C）所有节点入度之和的一半 D）没有必然联系

7. 在含有n个节点的完全图中，其边数为（ ）。 A)n B)n-1 C)n+1 D)(n-1)n/2

8. 在含有n个节点的图，它有（ ）个补图。 A)1 B)n C) (n-1)n/2 D)0

9. .如果两个图是同构的，那么下面那条是错误的.( )

A)节点数相等 B)边数相等 C)度数相同的节点数相等 D)连通的

10. 在具有n个节点的图中，如果两个节点之间有路，则必有一条路的长度（ ）。 A)至少为n B)至少为n-1 C)至多为n-1 D)n

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

A)连通图 B)强连通图 C）欧拉图 D）平面图

12. 含有m个节点的简单图，其边数不会多于（ ）。

A）1 B）m C)m-1 D)m(m-1)/2

13. 含有n个节点的图，至少生成（ ）棵生成树。 A)1 B)n C) (n-1)n/2 D)0

14. 连通图必然有（ ）。

A）欧拉路 B)汉米尔顿路 C)欧拉回路 D)通过各节点的路

15. 如果一个连通图有m个结点，则它的邻接矩阵的秩为（ ）

A)m B)m+1 C)m-1 D)不确定

三.判断题

1. 在任何图中，度数为偶数的节点必有奇数个。( )

2. 在任何有向图中，所有节点的入度之和等于所有节点的出度之和。（ ）

3. 每个图中，边数等于节点度数的两倍。（ ）

4. 连通图必有欧拉回路。（ ）

5. 有汉米尔顿路的图必有欧拉路。（ ）

6. 含有欧拉回路的图中每个节点的度数必为偶数。（ ）

7. 含有欧拉回路的图必有汉密尔顿路。（ ）

8. 一个图的边连通度一定大于等于其点连通度。（

四.计算题

1. 画出下图的完全补图。

2. 给一个含有5个节点的自补图。

3. 求下图中 1）从A到F所有通路。 2）从A到F的所有迹。

4. 求下图的邻接矩阵，并求出可达性矩阵。

）