2007級(下)離散數(shù)學(xué)標(biāo)準(zhǔn)答案(尤楓)

精選優(yōu)質(zhì)文檔-----傾情為你奉上精選優(yōu)質(zhì)文檔-----傾情為你奉上專心---專注---專業(yè)專心---專注---專業(yè)精選優(yōu)質(zhì)文檔-----傾情為你奉上專心---專注---專業(yè)北京化工大學(xué)2008——2009學(xué)年第一學(xué)期《離散數(shù)學(xué)（II）》期末考試試卷標(biāo)準(zhǔn)答案一、填空題（本題共20分，每題2分）1.設(shè)R是實(shí)數(shù)集合，f：R→R，f(x)=x2-x+2，g：R→R，g(x)=x-3，則：g。f=x2-x-1。2.設(shè)I,Q,R,C分別表示整數(shù)集、有理數(shù)集、實(shí)數(shù)集和復(fù)數(shù)集，在集合I,R-Q,C中，彼此等勢的集合是R-Q與C。3.設(shè)A={1,-1}，則A關(guān)于普通加法、減法、乘法和除法中乘法和除法運(yùn)算是封閉的。4.設(shè)G=<<a>,*>是24階循環(huán)群，則G的生成元有8個。5.設(shè)<S,+,·>是環(huán)，則對任意的a∈S，有a·0=0。6.設(shè)<R,≤>是由實(shí)數(shù)集上的小于等于關(guān)系構(gòu)成的格，對任意的x,y∈R，則x和y的最小上界x∨y=x與y的最小公倍數(shù)。7.設(shè)v是有n個結(jié)點(diǎn)的有向完全圖Kn的一個結(jié)點(diǎn)，則d(v)=2(n-1)。8.具有n個結(jié)點(diǎn)的k-正則圖G的邊數(shù)m=kn/2。9.設(shè)G=<V,E>是有n個結(jié)點(diǎn)和m條邊的無向圖，若G是連通的且m=n-1，則稱G是無向樹。10.設(shè)G*是連通平面圖G的對偶圖，已知G的邊數(shù)m=10，面數(shù)k=3,則G*的面數(shù)k*=9。二、簡答題（本題共30分，每題10分）1.對于給定的整數(shù)集I和自然數(shù)集N，判斷f是否是從I到N的函數(shù)f：I→N，f(x)=x2+1并說明理由。如果是，說明f是否為單射、滿射或雙射。解：（6分）f是從I到N的函數(shù)。因?yàn)閷θ我鈞∈I，有f(x)=x2+1∈N，且唯一，故f是從I到N的函數(shù)。（4分）f不是單射、滿射或雙射。因0∈N，但不存在x∈I，使f(x)=0，所以f不是滿射的。又因?yàn)楫?dāng)x=1或x=-1時，f(x)=2，即1≠-1，而f(1)=f(-1)，故f不是單射的。2.設(shè)R是實(shí)數(shù)集合，判斷R×R關(guān)于·運(yùn)算能否構(gòu)成群<R×R,·>，請說明理由。其中·運(yùn)算定義為：<a,b>·<c,d>=<a+c,b+d>解：（2分）能構(gòu)成群<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分）結(jié)合律。任意<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>。因?yàn)槿我鈱?lt;a,b>∈R×R，有<a,b>·<0,0>=<0,0>·<a,b>=<a,b>(4)（2分）逆元。任意對<a,b>∈R×R，其逆元為<-a,-b>。因?yàn)?lt;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的子格。因?yàn)閧a,b}的最小上界是c，但c不在L1中。（3分）L2是L的子格。因?yàn)長2中任意兩元素的最小上界和最大下界均在L2中。且它是有界格和分配格。（3分）L3是L的子格。因?yàn)長3中任意兩元素的最小上界和最大下界均在L3中。且它是有界格和分配格。（2分）L4不是L的子格。因?yàn)閧c,e}的最大下界是b，但b不在L4中。vv1v2v3v4v5Ge1e2e3e4e5e6e7e2e3v6三、計算題（本題共30分，第1小題20分，第2小題10分）1.設(shè)有向圖G=<V,E>如圖所示，求(1)G的關(guān)聯(lián)矩陣；(2)G的鄰接矩陣；(3)G的可達(dá)矩陣；(4)圖中所有長度小于等于5的通路（包括回路）數(shù)目；(5)求G的強(qiáng)分圖、單向分圖和弱分圖。解：(1)（5分）G的關(guān)聯(lián)矩陣為(2)（5分）G的鄰接矩陣為(3)（5分）G的可達(dá)矩陣為(4)（5分）圖中所有長度小于等于5的通路（包括回路）共35條。(5)（5分）G的強(qiáng)分圖為G[{v1,v2,v5,v6}]，G[{v3}]，G[{v4}]；G的單向分圖為G；G的弱分圖為G。2.設(shè)無向圖T中，有2個2度結(jié)點(diǎn)，2個3度結(jié)點(diǎn)，1個4度結(jié)點(diǎn)，其余結(jié)點(diǎn)均為樹葉，試求T的結(jié)點(diǎn)數(shù)n、邊數(shù)m和樹葉數(shù)t。解：因?yàn)閙=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.設(shè)A={a+bi|a,b∈Q}，其中Q為有理數(shù)集合，i2=-1，運(yùn)算為復(fù)數(shù)的加法+和乘法×，證明A同復(fù)數(shù)的加法+和乘法×構(gòu)成環(huán)<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)結(jié)合律。因((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。因?yàn)?a+bi)+(0+0i)=(0+0i)+(a+bi)=(a+bi)(4)逆元。a+bi的逆元是-a-bi。因?yàn)?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結(jié)合律。((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