離散數(shù)學(xué)(下)A卷和習(xí)題與講解及評(píng)分標(biāo)準(zhǔn)

第2學(xué)期《離散數(shù)學(xué)（下）》考試試卷（A卷）----------------------------------------線（閉卷時(shí)間120分鐘）題號(hào)得分一二三四五總分號(hào)學(xué)閱卷人------------一、單項(xiàng)選擇題（每小題2分，共20分）得分---名線----姓----1.設(shè)I為整數(shù)集，下列系統(tǒng)中不是代數(shù)系統(tǒng)的有()。訂-------裝---A.<I,>B.<I,+>C.<I,>D.都不是。---超---訂-勿-2.下面的代數(shù)系統(tǒng)(G,*)中，()不是群。----題-業(yè)專-----A.G為整數(shù)集合，*為加法；C.G為有理數(shù)集合，*為加法；B.G為偶數(shù)集合，*為加法；--答---------D.G為有理數(shù)集合，*為乘法。----------按矩陣的加法和乘法構(gòu)成R上的二階方陣環(huán),這個(gè)級(jí)年-a0-----------裝a,bR,R為實(shí)數(shù)域b0方陣環(huán)是()------------------------------A.有幺元的交換環(huán)C.無幺元的交換環(huán)B.無幺元的非交換環(huán)D.有幺元的非交換環(huán)系院4.下列說法不正確的是（）/A．兩個(gè)域的直接乘積是域B.有限整環(huán)是域C．次對(duì)稱群S的階是n!D.域只有平凡理想nn5.下列整數(shù)集對(duì)于整除關(guān)系都構(gòu)成偏序集，而能構(gòu)成格的是（）A．{l，2，3，4，6}B．{1，2，3，6，12}1C．{2，3，6}D．{l，2，3}6．記N是自然數(shù)集，≤是小于等于關(guān)系，則<N,≤>是(A.有界格B.有補(bǔ)格C.分配格).D.有補(bǔ)分配格7.在布爾代數(shù)B,,,,0,1上定義的n元布爾表達(dá)式所對(duì)應(yīng)的不同主析取范式總個(gè)數(shù)為（）A．2nB.BBnC.B2nD.Bn8.無向圖的關(guān)聯(lián)矩陣中“關(guān)聯(lián)”指的是(A.結(jié)點(diǎn)與結(jié)點(diǎn)的關(guān)聯(lián))。B.邊與邊的關(guān)聯(lián)D.都不是C.邊與結(jié)點(diǎn)的關(guān)聯(lián)9.設(shè)G是具有n個(gè)結(jié)點(diǎn)m條邊，k個(gè)面的連通平面圖，其中m成立。）2，則有（A．nmkC．mnB．m3n6D．m2n42110.設(shè)G是由5個(gè)結(jié)點(diǎn)組成的無向完全圖，則從G中刪去（樹。）條邊可以得到A．4B．5C．6D．10得分二、判斷題（對(duì)的打√，錯(cuò)的打×，每小題2分，共10分）1.若群G的每個(gè)元素都滿足方程x2=e，其中e為幺元，則G為交換群。（））2.若群G的階為n，d為n的一個(gè)因子，則G一定有階為d的子群。3.如果環(huán)R滿足左消去律，則R必定沒有右零因子。（（）4.設(shè)G=<V,E>是無向簡單圖,G的極小支配集都是G的極大獨(dú)立集。（）25.設(shè)G是有10個(gè)結(jié)點(diǎn)的無向圖，對(duì)于G中任意兩個(gè)不鄰接的結(jié)點(diǎn)u和v,均有degudegv9，則G是哈密爾頓圖。（）----------------得分-三、填空題（每小空2分，共20分）---------1.設(shè)G是由12個(gè)元素構(gòu)成的循環(huán)群，a是G的一個(gè)生成元素，則G有_______個(gè)非---------平凡子群。G的生成元素集合是_________。-----線---2.設(shè)H是群G的子群，a,bG，則HaHb的充要條件是___________________。-------------3.設(shè)a,b分別是群G的3階和5階元，且ab=ba，則ab的階為__________。線-------訂-----4.整數(shù)環(huán)有__________個(gè)可逆元。--裝------超----5.如果一個(gè)格中存在全上界和全下界，則這個(gè)格是________________。訂勿-----題---6．所有模格組成的集合_________（填--,或）所有分配格組成的集合。---答----------7．設(shè)G是(p,p)連通圖，則G的生成樹的個(gè)數(shù)至多為____________。------------8．含5個(gè)結(jié)點(diǎn)、3條邊的不同構(gòu)的無向簡單圖個(gè)數(shù)為________。----------裝9．設(shè)無向圖G有12條邊，有6個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù)均小于3，則G中結(jié)點(diǎn)數(shù)--------至少為______。-------------得分---四、解答題（每小題10分，共30分）------1.給出一個(gè)含有四個(gè)四元置換的集合G,,,,其中,123412341234123412344,,,3,123412432134214312G在合成運(yùn)算下組成的群G,，試求G,的所有正規(guī)子群，并且求G,關(guān)于每個(gè)正規(guī)子群的商群及各商群中的運(yùn)算表。32.設(shè)B,,,,0,1為一布爾代數(shù)，a,b,cB，試化簡布爾表達(dá)式4aab(cab)。3.給定彼得森(Petersen)圖G如右圖所示。試求圖G的支配數(shù)(G)、點(diǎn)覆蓋數(shù)(G)、邊覆蓋數(shù)(G)、001獨(dú)立數(shù)(G)、匹配數(shù)(G)、點(diǎn)連通度(G)、010邊連通度(G)、點(diǎn)色數(shù)(G)、邊色數(shù)(G)，101以及鄰接矩陣A（結(jié)點(diǎn)與自身鄰接，結(jié)點(diǎn)次序按字母順序）。001(G)1(G)(G)(G)1(G)(G)(G)(G)(G)00015----------------------------------------線-----------------------線訂-------裝------得分超-五、證明題（每小題10分，共20分）---訂勿---1.設(shè)G是群，a,b是G中任意兩個(gè)元素，則ab的階與ba的階相同。--題--------答--------------------------------裝------------------------------62.設(shè)T是一棵樹且(T)k，證明：T中至少有k個(gè)結(jié)點(diǎn)的度為1。78安徽大學(xué)2009—2010學(xué)年第2學(xué)期《離散數(shù)學(xué)（下）》考試試題（A卷）參考答案及評(píng)分標(biāo)準(zhǔn)一、單選題（每小題2分，共20分）1.A；2.D；3.B；4.A；5.B；6.C；7.C；8.C；9.A；10.C。二、判斷題（每小題2分，共10分。對(duì)的打√，錯(cuò)的打×）1.√；2.×；3.√；4.×；5.×。三、填空題（每小空2分，共20分）1.4;{a,a3,a5,a7,a11};2.ab1H（或ba1H）;3.15;2;4.5.有界格;6.;7.p;8.4;9.9.四、計(jì)算題（每小題10分，共30分）1.解：G,的正規(guī)子群有,、G,、,,、,,、11213,,。（5分）14,的商群為,*，其中*運(yùn)算表為：（6分）,,,231141243*34112221433341232144G,的商群為G,*，其中*運(yùn)算表為：（7分）G*GG的商群為,*，其中*運(yùn)算表為：（8分）,,,,,121234,*,1234,12,,4123,,34,2341的商群為,*，其中*運(yùn)算表為：（9分）,,,,,131324《離散數(shù)學(xué)（下）》參考答案第1頁共2頁*,,1324,,,131324,,2,4,,,,*，其中*運(yùn)算表為：（10分）1342的商群為,,1414*23,,1423,,1,41423,,,2323142.解：（共10分）aab(cab)＝aabcaab＝aab(2分)(6分)(10分)＝(aa)(ab)ab3.解:（每空1分，共10分）(G)01(G)1(G)(G)(G)(G)(G)1(G)(G)10000365453334鄰接矩陣:11001100001110001000最小支配集：{b,f,e},最小點(diǎn)覆蓋：{b,d,e,f,g,h},01110001000011100010最小邊覆蓋：{(a,b),(c,d),(e,j),(f,h),(g,i)}，最大獨(dú)立集：{b,e,h,i}，1001100001A1000010110最大匹配：{(a,b),(c,d),(e,j),(f,h),(g,i)}，最小點(diǎn)割：{b,f,e},010000101100100101010001011010最小割集：{(a,b),(a,f),(a,e)}，點(diǎn)正常著色：{b,e,h,i},{a,c,j},{d,f,g}.邊正常著色：{(a,b),(c,d),(e,j),(f,h),(g,i)},{(b,c),(d,e),(a,f),(h,j)},0000101101{(a,e),(f,i),(g,j),(c,h)},{(b,g),(d,i)}.五、證明題（每小題10分，共20分）《離散數(shù)學(xué)（下）》參考答案第2頁共2頁1.證：設(shè)ab的階等于n，即。abe(2分)n于是babbbabb。，(5分)