北化2009级离散数学考试试卷(II)标准答案(尤枫)

北京化工大学2010——2011学年第一学期《离散数学（II）》期末考试试卷标准答案一、填空题（本题共10分，每题2分）1.设A,B为集合，且|A|=2，|B|=5，则A到B可定义的单射函数有a是G的一个生成元，则20个。G的另一个生2.设G是由六个元素构成的循环群，成元是a5。3.设L是集合，∨和∧是L上的两个二元运算，，则＜L，∨，∧＞是格。有15个结点，若这两个二元运算满足交换律、结合律和吸收律4.设G是完全二元树，5.设G=＜V，E＞是有其中有8片树叶，则G有14条边。r个面，则n个结点，m条边的连通平面图，且有r=2-n+m。二、判断题（本题共中画×。10分，每题2分），正确的在括号中画√，错误的在括号(√)1.设f是X到Y的函数，如果f和g是单射的，则gf是单射的。(√)2.同构的两个代数系统表示两者形式不同而实质相同。g是Y到Z的函数，gf是X到Z的复合函数，(√)3.若二分图G=＜V1，E，V2＞是k-正则图，则G中存在完全匹配。U中的零元和单位元，(×)4.设U是至少有2个元素的含幺元环，0和1分别是则必有(×)5.无向图三、选择题（本题共1.设集合0=1。G是欧拉图，当且仅当10分，每题G的所有结点的度数均为偶数。2分）A={a1,a2,a3,a4}，B={b1,b2,b3}，f：A→B为函数f={<a1,b2>,<a2,b2>,<a3,b1>,<a4,b3>}则f是B函数。A：双射B：满射、非单射第1页C：单射、非满射D：非单射、非满射2.设S={x|x为素数且x<100}，在S上定义二元运算*如下：A：x*y=max(x,y)C：x*y=lcm(x,y)lcm和gcd分别表示最小公倍数和最大公约数）C（或C，D）。B：x*y=min(x,y)D：x*y=gcd(x,y)（其中，则＜S，*＞不能构成代数系统的是3.实数集A。A：0R上定义二元运算*为：r1,r2R，r1*r2=r1+r2-r1r2，则其单位元是B：1C：-1m条边的连通图，D：24.设G是有n个结点，D条边。要确定G的一棵生成树，必须删除G的A：n-15.设图G是具有n-m+r=B：m-1C：n-m+1m条边和D：m-n+1n个结点，C。B：kr个面的简单平面图，它有k个连通分支构成，则A：2C：k+1D：k-1四、简答题（本题共1.对代数系统＜50分，第3题20分，第1,2,4题各10分）N5,×5＞，试写出×5的运算表，并求出单位元和每一个元素的逆元（如果存在）。其中N5={0,1,2,3,4}，×5是N5上的模5乘法运算。解：(5分)运算表如下：×000000101234202413303142404321501234(5分)单位元e=1第2页0无逆元，1逆元为1，2和3互逆，4逆元为42.设S0={a,b,c,d,e,f}，S1={a,b,c,d,e}，S2={a,b,c,e,f}，S3={a,b,c,e}，S4={a,b,c}，S5={a,b}，S6={a,c}，S7={a}，L={S0,S1,S2,S3,S4,S5,S6,S7}，为集合的包含关系。(1)画出偏序集＜L,＞的哈斯图；S0S1(2)判断＜L,＞是否为格，是否为有补格。说明理由。S2解：(5分)偏序关系的哈斯图如图所示。S3S4(3分)此偏序集L,是格。显然任意两个L中元素均有最小上界和最大下界在L中。S5S6(2分)不是有补格，因为S4无补元。S73.设有向图G=<V,E>如图所示，求(1)G的关联矩阵；(2)G的邻接矩阵；(3)G的可达矩阵；1(4)图中所有长度小于等于(5)求G的强分图、单向分图和弱分图。解：(1)(4分)G的关联矩阵为5的通路（包括回路）数目；e1e3e44101100e6e531100102e2MH011001000111(2)(4分)G的邻接矩阵为第3页01000011A10011000(3)(4分)G的可达矩阵为11111111P11111111(4)(4分)图中所有长度小于等于5的通路（包括回路）数目是G。63条。(5)(4分)G的强分图、单向分图和弱分图均是4.设T是无向树，它有40个1度结点，T中有多少个T中有x个4度结点，y个5度结点，则20个2度结点，31个3度结点，且没5度结点？说明理由。有6度或6度以上结点，问4度结点，多少个解：设m=n-12m=2n-2nd(v)=2mii1由此得：40+20×2+31×3+4x+5y=2(40+20+31+x+y)-2即：2x+3y=7由于x和y均是正整数，所以有即T中有2个4度结点和x=2，y=11个5度结点。五、证明题（本题共20分，每小题10分）1.给定群<G,*>，aG，定义映射是群<G,*>到群<G,*>的自同态映射。f如下：对xG，f(x)=a*x*a-1，试证明：f证明：任取x，yG，则f(x)=a*x*a-1G，f(x)=a*x*a-1Gf(x*y)=a*(x*y)*a-1第4页

=a*(x*e*y)*a-1=a*(x*a-1*a*y)*a-1=(a*x*a-1)*(a*y*a-1)=f(x)*f(y)故f是群<G,*>到群<G,*>的自同态映射。2.给定环<R,+,×>，且SR，S定义为：S={a+b2|a,bQ}其中R和Q分别为实数集合和有理数集合，+和×分别为算术加法和乘法。试证明：<S,+,×>是<R,+,×>的子环。SR证明：显然有因为0Q，所以2=0S，所以SR且非空。0+0任取a+b2，c+d2Sa,b,c,dQ，