北化2009級離散數(shù)學(xué)考試試卷(II)標(biāo)準(zhǔn)答案(尤楓)

北京化工大學(xué)2010——2011學(xué)年第一學(xué)期《離散數(shù)學(xué)（II）》期末考試試卷標(biāo)準(zhǔn)答案一、填空題（本題共10分，每題2分）1.設(shè)A,B為集合，且|A|=2，|B|=5，則A到B可定義的單射函數(shù)有a是G的一個生成元，則20個。G的另一個生2.設(shè)G是由六個元素構(gòu)成的循環(huán)群，成元是a5。3.設(shè)L是集合，∨和∧是L上的兩個二元運(yùn)算，，則＜L，∨，∧＞是格。有15個結(jié)點(diǎn)，若這兩個二元運(yùn)算滿足交換律、結(jié)合律和吸收律4.設(shè)G是完全二元樹，5.設(shè)G=＜V，E＞是有其中有8片樹葉，則G有14條邊。r個面，則n個結(jié)點(diǎn)，m條邊的連通平面圖，且有r=2-n+m。二、判斷題（本題共中畫×。10分，每題2分），正確的在括號中畫√，錯誤的在括號(√)1.設(shè)f是X到Y(jié)的函數(shù)，如果f和g是單射的，則gf是單射的。(√)2.同構(gòu)的兩個代數(shù)系統(tǒng)表示兩者形式不同而實(shí)質(zhì)相同。g是Y到Z的函數(shù)，gf是X到Z的復(fù)合函數(shù)，(√)3.若二分圖G=＜V1，E，V2＞是k-正則圖，則G中存在完全匹配。U中的零元和單位元，(×)4.設(shè)U是至少有2個元素的含幺元環(huán)，0和1分別是則必有(×)5.無向圖三、選擇題（本題共1.設(shè)集合0=1。G是歐拉圖，當(dāng)且僅當(dāng)10分，每題G的所有結(jié)點(diǎn)的度數(shù)均為偶數(shù)。2分）A={a1,a2,a3,a4}，B={b1,b2,b3}，f：A→B為函數(shù)f={<a1,b2>,<a2,b2>,<a3,b1>,<a4,b3>}則f是B函數(shù)。A：雙射B：滿射、非單射第1頁C：單射、非滿射D：非單射、非滿射2.設(shè)S={x|x為素?cái)?shù)且x<100}，在S上定義二元運(yùn)算*如下：A：x*y=max(x,y)C：x*y=lcm(x,y)lcm和gcd分別表示最小公倍數(shù)和最大公約數(shù)）C（或C，D）。B：x*y=min(x,y)D：x*y=gcd(x,y)（其中，則＜S，*＞不能構(gòu)成代數(shù)系統(tǒng)的是3.實(shí)數(shù)集A。A：0R上定義二元運(yùn)算*為：r1,r2R，r1*r2=r1+r2-r1r2，則其單位元是B：1C：-1m條邊的連通圖，D：24.設(shè)G是有n個結(jié)點(diǎn)，D條邊。要確定G的一棵生成樹，必須刪除G的A：n-15.設(shè)圖G是具有n-m+r=B：m-1C：n-m+1m條邊和D：m-n+1n個結(jié)點(diǎn)，C。B：kr個面的簡單平面圖，它有k個連通分支構(gòu)成，則A：2C：k+1D：k-1四、簡答題（本題共1.對代數(shù)系統(tǒng)＜50分，第3題20分，第1,2,4題各10分）N5,×5＞，試寫出×5的運(yùn)算表，并求出單位元和每一個元素的逆元（如果存在）。其中N5={0,1,2,3,4}，×5是N5上的模5乘法運(yùn)算。解：(5分)運(yùn)算表如下：×000000101234202413303142404321501234(5分)單位元e=1第2頁0無逆元，1逆元為1，2和3互逆，4逆元為42.設(shè)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}，為集合的包含關(guān)系。(1)畫出偏序集＜L,＞的哈斯圖；S0S1(2)判斷＜L,＞是否為格，是否為有補(bǔ)格。說明理由。S2解：(5分)偏序關(guān)系的哈斯圖如圖所示。S3S4(3分)此偏序集L,是格。顯然任意兩個L中元素均有最小上界和最大下界在L中。S5S6(2分)不是有補(bǔ)格，因?yàn)镾4無補(bǔ)元。S73.設(shè)有向圖G=<V,E>如圖所示，求(1)G的關(guān)聯(lián)矩陣；(2)G的鄰接矩陣；(3)G的可達(dá)矩陣；1(4)圖中所有長度小于等于(5)求G的強(qiáng)分圖、單向分圖和弱分圖。解：(1)(4分)G的關(guān)聯(lián)矩陣為5的通路（包括回路）數(shù)目；e1e3e44101100e6e531100102e2MH011001000111(2)(4分)G的鄰接矩陣為第3頁01000011A10011000(3)(4分)G的可達(dá)矩陣為11111111P11111111(4)(4分)圖中所有長度小于等于5的通路（包括回路）數(shù)目是G。63條。(5)(4分)G的強(qiáng)分圖、單向分圖和弱分圖均是4.設(shè)T是無向樹，它有40個1度結(jié)點(diǎn)，T中有多少個T中有x個4度結(jié)點(diǎn)，y個5度結(jié)點(diǎn)，則20個2度結(jié)點(diǎn)，31個3度結(jié)點(diǎn)，且沒5度結(jié)點(diǎn)？說明理由。有6度或6度以上結(jié)點(diǎn)，問4度結(jié)點(diǎn)，多少個解：設(shè)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均是正整數(shù)，所以有即T中有2個4度結(jié)點(diǎn)和x=2，y=11個5度結(jié)點(diǎn)。五、證明題（本題共20分，每小題10分）1.給定群<G,*>，aG，定義映射是群<G,*>到群<G,*>的自同態(tài)映射。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,*>的自同態(tài)映射。2.給定環(huán)<R,+,×>，且SR，S定義為：S={a+b2|a,bQ}其中R和Q分別為實(shí)數(shù)集合和有理數(shù)集合，+和×分別為算術(shù)加法和乘法。試證明：<S,+,×>是<R,+,×>的子環(huán)。SR證明：顯然有因?yàn)?Q，所以2=0S，所以SR且非空。0+0任取a+b2，c+d2Sa,b,c,dQ，