2007级(下)离散数学标准答案(尤枫)

第1页北京化工大学2008——2009学年第一学期《离散数学（II）》期末考试试卷标准答案一、填空题（本题共20分，每题2分）1.设R是实数集合，f：R→R，f(x)=x2-x+2，g：R→R，g(x)=x-3，则：g。f=x2-x-1。2.设I,Q,R,C分别表示整数集、有理数集、实数集和复数集，在集合I,R-Q,C中，彼此等势的集合是R-Q与C。3.设A={1,-1}，则A关于普通加法、减法、乘法和除法中乘法和除法运算是封闭的。4.设G=a,*是24阶循环群，则G的生成元有8个。5.设S,+,·是环，则对任意的a∈S，有a·0=0。6.设R,≤是由实数集上的小于等于关系构成的格，对任意的x,y∈R，则x和y的最小上界x∨y=x与y的最小公倍数。7.设v是有n个结点的有向完全图Kn的一个结点，则d(v)=2(n-1)。8.具有n个结点的k-正则图G的边数m=kn/2。9.设G=V,E是有n个结点和m条边的无向图，若G是连通的且m=n-1，则称G是无向树。10.设G*是连通平面图G的对偶图，已知G的边数m=10，面数k=3,则G*的面数k*=9。二、简答题（本题共30分，每题10分）1.对于给定的整数集I和自然数集N，判断f是否是从I到N的函数f：I→N，f(x)=x2+1并说明理由。如果是，说明f是否为单射、满射或双射。解：（6分）f是从I到N的函数。因为对任意x∈I，有f(x)=x2+1∈N，且唯一，故第2页f是从I到N的函数。（4分）f不是单射、满射或双射。因0∈N，但不存在x∈I，使f(x)=0，所以f不是满射的。又因为当x=1或x=-1时，f(x)=2，即1≠-1，而f(1)=f(-1)，故f不是单射的。2.设R是实数集合，判断R×R关于·运算能否构成群R×R,·，请说明理由。其中·运算定义为：a,b·c,d=a+c,b+d解：（2分）能构成群R×R,·。(1)（2分）封闭性。任意的a,b,c,d∈R×R,有a,c∈R,b,d∈R，a+c∈R,b+d∈R，故a,b·c,d=a+c,b+d，所以a+c,b+dR×R(2)（2分）结合律。任意a,b,c,d,e,f∈R×R则(a,b·c,d)·e,f=(a+c)+e,(b+d)+f=a+(c+e),b+(d+f)=a,b·(c,d·e,f)(3)（2分）单位元为0,0。因为任意对a,b∈R×R，有a,b·0,0=0,0·a,b=a,b(4)（2分）逆元。任意对a,b∈R×R，其逆元为-a,-b。因为a,b·-a,-b=-a,-b·a,b=0,0。3.格L的哈斯图如下图所示，问下述子集中哪些是L的子格，请说明理由。对于L的子格说明是否是有界格、分配格。L1={0,a,b,1}L2={0,a,1}L3={a,c,d,1}L4={0,c,e,1}解：（2分）L1不是L的子格。因为{a,b}的最小上界是c，但c不在L1中。1eb0acd第3页（3分）L2是L的子格。因为L2中任意两元素的最小上界和最大下界均在L2中。且它是有界格和分配格。（3分）L3是L的子格。因为L3中任意两元素的最小上界和最大下界均在L3中。且它是有界格和分配格。（2分）L4不是L的子格。因为{c,e}的最大下界是b，但b不在L4中。三、计算题（本题共30分，第1小题20分，第2小题10分）1.设有向图G=V,E如图所示，求(1)G的关联矩阵；(2)G的邻接矩阵；(3)G的可达矩阵；(4)图中所有长度小于等于5的通路（包括回路）数目；(5)求G的强分图、单向分图和弱分图。解：(1)（5分）G的关联矩阵为110000010110000001100000011001000110010001M(2)（5分）G的邻接矩阵为010000001001000000001000100100000010A(3)（5分）G的可达矩阵为v1v2v3v4v5Ge1e2e3e4e5e6e7e2e3v6第4页111111111111001000001100111111111111P(4)（5分）图中所有长度小于等于5的通路（包括回路）共35条。(5)（5分）G的强分图为G[{v1,v2,v5,v6}]，G[{v3}]，G[{v4}]；G的单向分图为G；G的弱分图为G。2.设无向图T中，有2个2度结点，2个3度结点，1个4度结点，其余结点均为树叶，试求T的结点数n、边数m和树叶数t。解：因为m=n-12m=2×2+3×2+1×4+t×1t=n-5解得2m=9+n故2(n-1)=9+n所以得n=11，m=10，t=6四、证明题（本题共20分，每小题10分）1.设A={a+bi|a,b∈Q}，其中Q为有理数集合，i2=-1，运算为复数的加法+和乘法×，证明A同复数的加法+和乘法×构成环A,+,×。证明：A,+是交换群。（5分）任取a+bi，c+di，e+fi∈A,则a,b,c,d,e,f∈Q。(1)封闭性。因a+c,b+d∈Q，故(a+c)+(b+d)i∈A。(2)结合律。因((a+bi)+(c+di))+(e+fi)=(((a+c)+(b+d)i)+(e+fi))=((a+c)+e)+((b+d)+f)i=(a+(c+e))+(b+(d+f))i=(a+bi)+((c+e)+(d+f)i)=(a+bi)+((c+di))+(e+fi))(3)单位元为0+0i。第5页因为(a+bi)+(0+0i)=(0+0i)+(a+bi)=(a+bi)(4)逆元。a+bi的逆元是-a-bi。因为(a+bi)+(-a-bi)=(-a-bi)+(a+bi)=0+0i(5)交换律。(a+bi)+(c+di)=(a+c)+(b+d)i=(c+a)+(d+b)i=(c+di)+(a+bi)A,×是半群。（3分）(1)封闭性。(a+bi)(c+di)=(ac-bd)+(bc+ad)i∈A结合律。((a+bi)(c+di))(e+fi)=((ac-bd)+(bc+ad)i)(e+fi))=(ace-bde-bcf-adf)+(bce+ade+acf-bdf)i(a+bi)((c+di)(e+fi))=(a+bi)((ce-df)+(de+cf)i)=(ace-bde-bcf-adf)+(bce+ade+acf-bdf)i故((a+bi)(c+di))(e+fi)=(a+bi)((c+di)(e+fi))×对+的分配律。(a+bi)((c+di)+(e+fi))=(a+bi)((c+e)+(d+f)i)=(ac+ae-bd-bf)+(bc+be+ad+af)i(a+bi)(c+di)+(a+bi)(e+fi)=((ac-bd)+(ad+bc)i)+((ae-bf)+(be+af)i)=(ac+ae-bd-bf)+(bc+be+ad+af)i故(a+bi)((c+di)+(e+fi))=(a+bi)(c+di)+(a+bi)(e+fi)同理可证((c+di)+(e+fi))(a+bi)=(c+di)(a+bi)+(e+fi)(a+bi)故A同复数的加法+和乘法×构成环A,+,×。2.设V=S,⊙是半群，对任意的a,b,c∈S，如果a,b都与c可交换（即a⊙c=c⊙a，b⊙c=c⊙b），证明：a⊙b与c也是可交换的。证明：任取a,b,c∈S，有(a⊙b)⊙c=a⊙(b⊙c)=a⊙(c⊙b)=(a⊙c)⊙b=(c⊙a)⊙b=c⊙(a⊙b)