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

精选优质文档-----倾情为你奉上精选优质文档-----倾情为你奉上专心---专注---专业专心---专注---专业精选优质文档-----倾情为你奉上专心---专注---专业北京化工大学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，且唯一，故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+d>R×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>。1eb0acd3.格L的哈斯图如下图所示，问下述子集中哪些是L1eb0acdL1={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中。（3分）L2是L的子格。因为L2中任意两元素的最小上界和最大下界均在L2中。且它是有界格和分配格。（3分）L3是L的子格。因为L3中任意两元素的最小上界和最大下界均在L3中。且它是有界格和分配格。（2分）L4不是L的子格。因为{c,e}的最大下界是b，但b不在L4中。vv1v2v3v4v5Ge1e2e3e4e5e6e7e2e3v6三、计算题（本题共30分，第1小题20分，第2小题10分）1.设有向图G=<V,E>如图所示，求(1)G的关联矩阵；(2)G的邻接矩阵；(3)G的可达矩阵；(4)图中所有长度小于等于5的通路（包括回路）数目；(5)求G的强分图、单向分图和弱分图。解：(1)（5分）G的关联矩阵为(2)（5分）G的邻接矩阵为(3)（5分）G的可达矩阵为(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+tt=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。因为(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