离散复习试题.PPT

1、一、填空题 5小题 每题2分 共10分 二、判断题 5个小题 每题2分 共10分 三、选择题5个小题 每题2分 共10分 四、计算与简答题 3个题 共40分 四、证明题 3个题 共30分,考试题型,2 0 1 0 复习,复习内容,第六章 代数系统 代数系统定义；同态与同构；子代数,复习内容,第七章 函数半群与群 半群（独异点，循环半群，交换半群）；半群同态与同构；子半群。 群（有限群，无限群，交换群，循环群）；子群及判断；群的同态与同构。 第八章 环和域 环（整环，除环 ）的定义；子环；域；模加与模乘运算。 第九章 格与布尔代数 偏序集定义的格；代数系统定义的格；有补格，分配格；子格；布尔代数

2、,复习内容,第十章 图 图的基本概念；边、结点及结点度之间的关系；图的连通性（强连通，单向连通，弱连通；强分图，单向分图，弱分图）；图的矩阵表示（邻接矩阵，关联矩阵，可达矩阵）。 第十一章 欧拉图与哈密尔顿图 欧拉图与哈密尔顿图及其判定。 第十二章 特殊图 平面图及判定；对偶图；二分图及判定；二分图的应用,1.设A,B为集合，f：AB为一满射函数，则当A为无限集时，B （一定/不一定）是无限集,一、填空题（10分）参考答案,不一定,2.设I是正数集合，定义运算为：对任意的a,bI, ab=a+b-1。任取aI,则a的逆元a-1=,2-a,3.设是一个环，且对于任意的xS，有x*x = x，则对

3、于任意的xS，有x+x =,0,4.对完全二分图Km,n，若Km,n是哈密尔顿图，则n和m须满足的条件为,n=m (n2,5.在有n个结点的连通图中，其边数至少有 条,n-1,) 1.设有集合A,B,C和D，若AB，CD，则ACBD,二、判断题（10分）参考答案,) 2. 设有代数系统,S中的元素个数多于1个，若其存在运算*的单位元e和零元，则二者必相等,) 3.设是代数系统，其中,是二元运算，且这两个二元运算满足交换律、结合律、吸收律和幂等律，则称代数系统是格,) 4. K3,3是边数最少的非平面图，K5是结点数最少的非平面图,) 5.无向图G中的边e是割边的充分必要条件是e不包含在G的某一

4、回路中,2 0 1 0 试题,1、(10分)设G , *是一个群，u为G 中一个元素( uG )，在G内定义运算“ ”为：对任意的a,bG有 a b= a * u -1 * b 证明：G对于运算 构成一个群。其中u -1为u在群G , *中的逆元,证明：(1) 封闭性 显然对于任意的a , bG，有a b= a * u -1*bG 封闭性成立,2) 结合律 (ab)c =(ab)u-1c=(au-1b)u-1c =au-1(bu-1c)= a(bu-1c)=a(bc) 结合律成立,三、证明题参考答案,3) 单位元为u。 对任意的aG，有 ua= uu-1a= a，au= au-1u= a,4)

5、 对任意的aG，逆元为 ua-1u。 因为对任意的aG，有 a(ua-1u)= au-1(ua-1u)= u (ua-1u)a= (ua-1u)u-1a=u 综上可知，G 对于运算构成一个群,参考答案,2 0 1 0 试题,2、(20分)设A ,+,为一个环，其加法单位元记为0，乘法单位元记为1 。对于任意的a, bA，定义运算和为：ab=a+b+1，ab= ab + a+b，试证明A , , 也为环，并进一步证明环A , , 和环A , +,是同构的（即在两者之间存在同构映射,2 0 1 0 试题,参考答案,证明：(1) 对，任取a,b,c A ab=a+b+1 A，封闭性成立； ab=a+

6、b+1= b+a+1= ba，交换律成立； (ab)c = ( a+b+1)c = a+b+1+c+1 = a+(b+c+1)+1=a(bc) 结合律成立,单位元是-1（-1为1的加法逆元） 因为(-1)a = a(-1)= a+(-1)+1=a+0=a，因此单位元是-1,参考答案,2 0 1 0 试题,a的逆元是(-a)+(-1)+(-1)=(-a)+2(-1) 因为 a(-a)+(-1)+(-1)= a+(-a)+(-1)+(-1)+1 = (a+(-a)+(-1)+(-1)+1) =0+(-1)+0=-1 由的可交换性知(-a)+(-1)+(-1)是a的逆元。 故是交换群,2) 对A ,

7、 ，任取a,b,c A ab = ab + a+b A，封闭性成立； (ab)c = (ab)c+(ab)+c = (ab+a+b)c+(ab+a+b)+c =abc+ab+ac+bc+a+b+c a(bc)= a(bc)+a+(bc) =a(bc+b+c)+a+(bc+b+c) = abc+ab+ac+bc+a+b+c 所以(ab)c = a(bc)，结合律成立。 故是半群,参考答案,2 0 1 0 试题,3) 对的分配律，任取a,b,c A a(bc)= a(bc)+ a+(bc) =a( b+c+1)+a+( b+c+1) (ab)(ac)=(ab+a+b)( ac+a+c) =(ab+

8、a+b)+( ac+a+c)+1 =a( b+c+1)+a+( b+c+1) 故：a(bc)= (ab)(ac) 同理可证(bc)a = (ba)(ca)，分配律成立。 故A , , 是交换环,参考答案,2 0 1 0 试题,4) 定义 f：AA，使任取a A, f(a)=a+(-1)=a -1 对于任意a A，存在元素a+1 A，使 f(a+1)=(a+1)+(-1)=a 因此 f 是满射的； 设a1, a2 A，且a1a2，若f(a1)= f(a2)，即若a1-1= a2-1， 则a1-1+1= a2-1+1，于是a1= a2，与a1a2矛盾， 因此当a1a2， f(a1)f(a2)，故

9、f 是单射的。所以 f 是双射的,参考答案,2 0 1 0 试题,任取a,b A f(a+b)=a+b-1 f(a)f(b)=(a-1)(b-1)=(a-1)+(b-1)+1= a+b-1 因此 f(a+b) = f(a)f(b) 又 f(ab)=ab-1 f(a)f(b)=(a-1)(b-1)=(a-1)(b-1)+ (a-1)+(b-1)= ab-1 因此f(ab)= f(a)f(b) 由上可知，f 是环A , +,到环A , , 的同构，环A , , 和环A , +,是同构的,参考答案,2 0 1 0 试题,1、(20分)设有向图G=如图所示，求 (1) G的关联矩阵； (2) G的邻接

10、矩阵； (3) G的可达矩阵； (4) 图中所有长度小于等于5的通路（包括回路）数目； (5) 求G的强分图、单向分图和弱分图,解：(1) G的关联矩阵为,2 0 1 0 试题,四、简答与计算题参考答案,参考答案,2 0 1 0 试题,3) G的可达矩阵为,2) G的邻接矩阵为,4) 图中所有长度小于等于5的通路（包括回路）数目为30条。 (5) G的强分图为Gv1, v2, v4、Gv3和Gv5； G的单向分图为G本身； G的弱分图为G本身,参考答案,2 0 1 0 试题,2、(10分) 设图G=，其中边数m =21，3个4度结点，其余的均为3度结点，求此图的结点数,参考答案,2 0 1 0 试题,解：对图G=，由图中边数与结点度数之间的关系：有：34+3(n-3)=221 即：3n=39 n=13,一、设G=Q-1(Q为有理数集合)，定义G上的二元运算为ab=a