离散数学复习题

34．设集合B={a,b,c}上的二元关系R的关系矩阵

?110?MR??001? ????000??则R具有的性质是________,MS(R)=________。

35．设集合A={1,2,3,4}上的等价关系R={<1,2>, <2,1>,<3,4>,<4,3>}∪IA，那么A中各元素的等价类为________。

36．设集合A={a,b}，B={1,2}，则从A到B的所有函数是________，其中双射的是________。

37．设集合A={1,2,3}上的函数分别为f={<1,2>,<2,1>, <3,3>},g={<1,3>,<2,2>,<3,2>}，则f?g=____________, f?f=____ ________。

38．图G有15条边，每个结点的度数均为2，则G有________个结点。

39．图G有21条边，3个四度结点其余均为三度结点，则G有________个结点。

40．图G有24条边，每个结点的度数均相同，则G有

________个结点。

41．图G为有n个结点、m条边的简单图，结点v的度数为k，e为G的一条边。

(1)G-v中有________个结点和________条边； (2)G-e中有________个结点和________条边。

42．设有向图D=，V={v1,v2,…vn},A(D)=(aij)n×n为的邻接矩阵，则

(1)D中结点vi的出度记作________，vi的入度记作________，vi的度数为________

(2)D中所有结点的出度之和为________，所有结点入度之和为________，所有度数之和为________。 43．设有向图D=， (1)已知邻接矩阵

?0?1A(D)???0??0001?000?? 100??010?则P(D)=________，D的图形为________。 (2) 已知邻接矩阵

?0?1A(D)???0??0001?010?? 000??010?则P(D)=________，D的图形为________。 (3) 已知邻接矩阵

?0?1A(D)???0??1000?010?? 000??010?则P(D)=________，D的图形为________。 44．n=________，无向完全图Kn是欧拉图；

n=________，无向完全图Kn仅存在欧拉通路而不存在欧拉回路。

45．构造一个欧拉图，其结点数和边数满足：?V?,?E?的奇偶性一样的图为________；?V?,?E?的相反的图为_______. 46．给定平面图如图G所示，则G的面数为________。 47．若连通平面图有4个结点,3个面，则它有_____条边。 48．无向完全图Kn，仅当n________时是平面图。 49．设A为非空集合，映射________，称为集合A上的二元运算。

50．非空集合A上的二元运算?，满足________，则称运算?是可交换的；满足________，则称运算?是可结合的。 51．e称为集合A上的二元运算?的单位元，则e既是________，又是________，即________。 52．把置换??123456?表示成互不相交轮换或对换??463125?的积是________，??123456?表示成互不相交轮换??326154?或对换的积是________。

53．设四元置换???，??1?________。 ??2314?54．代数系统同构具有________性和________性。 55．在环中，(a?b)3?________________________。 56．设(G，+，?)是环，若________运算满足________，则称(G，+，?)是交换环。

57．集合L上的两个二元运算∧和∨满足________律、________律和________律。则(L，∧，∨)是格。 58．在布尔代数中，有a?(a?b)?a?b，则其对偶式________成立。

59．设(L，gcd，lcm，0，1)是有界格，a是L中的一个元素，如果存在b使得________,________，则称b是a的余元素。

60．?设(B，+，?，0，1)是布尔代数，?a,b,c?B,则

(a?b)?(a?b?c)?(a?b?c)?(a?b?c)?________________.

?1234?二． 选择题：

1.下面联结词不具有交换律的是( )

(A)? (B) ? (C) ? (D)? 2.下面语句是真命题的为( )