1、【最新卓越管理方案您可自由編輯】（績(jī)效考核）電大離散數(shù)學(xué)形成性考核冊(cè)作業(yè)（三）答案20XX年XX月多年的企業(yè)咨詢顧問(wèn)經(jīng)驗(yàn)r經(jīng)過(guò)實(shí)戰(zhàn)險(xiǎn)證可以落地執(zhí)行的卓越管鹿方素，信得您不戟擁有離散數(shù)學(xué)形成性考核作業(yè)（三）集合論和圖論綜合練習(xí)本課程形成性考核作業(yè)共4次，內(nèi)容由中央電大確定、統(tǒng)壹布置。本次形考作業(yè)是第三次作業(yè)，大家要認(rèn)真及時(shí)地完成圖論部分的形考作業(yè)，字跡工整，抄寫(xiě)題目，解答題有解答過(guò)程。壹、單項(xiàng)選擇題1 .若集合A=2,a,a,4,則下列表述正確的是（B）.Aa，aABaAC2ADA2 設(shè)B=2,3,4,2，那么下列命題中錯(cuò)誤的是（B）A2BB2,2,3,4BC2BD2,2B3 若集合A=a，b，

2、1，2，B=1，2，則（B）ABA，且BABBA，但BACBA，但BADBA，且BA4 .設(shè)集合A=1,a,則P（A）=（C）.A1,aB,1,aC,1,a,1,aD1,a,1,a5 .設(shè)集合A=1,2,3,4,5,6上的二元關(guān)系R=a,ba,bA,且a+b=8,則R具有的性質(zhì)為（B）A.自反的B.對(duì)稱的C.對(duì)稱和傳遞的D.反自反和傳遞的6 .設(shè)集合A=1,2,3,4,5,B=1,2,3,R從AUB的二元關(guān)系，R=a,baA，bB且則R具有的性質(zhì)為（）A.自反的B.對(duì)稱的C.傳遞的D.反自反的注意：此題有誤！自反性、反自反性、對(duì)稱性、反對(duì)稱性以及傳遞性指某壹個(gè)集合上的二元關(guān)系的性質(zhì)。7 設(shè)集合

3、A=1,2,3,4上的二元關(guān)系R=1,1，2,2，2,3，4,4，S=1,1，2,2，2,3，3,2，4,4，則S是R的(C)閉包.A.自反B.傳遞C.對(duì)稱D.之上均不對(duì)8 .非空集合A上的二元關(guān)系R,滿足(A),則稱R是等價(jià)關(guān)系.A.自反性，對(duì)稱性和傳遞性B.反自反性，對(duì)稱性和傳遞性C.反自反性，反對(duì)稱性和傳遞性D.自反性，反對(duì)稱性和傳遞性9 .設(shè)集合A=a,b,則A上的二元關(guān)系R=<a,a>,<b,b>是A上的(C)關(guān)系.A.是等價(jià)關(guān)系但不是偏序關(guān)系B.是偏序關(guān)系但不是等價(jià)關(guān)系C.既是等價(jià)關(guān)系又是偏序關(guān)系D.不是等價(jià)關(guān)系也不是偏序關(guān)系10 .設(shè)集合A=1,2,3,4

4、,5上的偏序關(guān)系的哈斯圖如右圖所示，若A的子集B=3,4,5,則元素3為B的(C).A.下界B.最大下界C.最小上界D.之上答案均不對(duì)11.設(shè)函數(shù)f:RR,f(a)=2a+1；g：RR,g(a)=a2.則(C)有反函數(shù).A.g?fB.f?gC.fD.g12 .設(shè)圖G的鄰接矩陣為則G的邊數(shù)為(D).A.5B.6C.3D.413 .下列數(shù)組中，能構(gòu)成無(wú)向圖的度數(shù)列的數(shù)組是(C).A.(1,1,2,3)B.(1,2,3,4,5)C.(2,2,2,2)D.(1,3,3)14 .設(shè)圖G=<V,E>,則下列結(jié)論成立的是(C).A.deg(V)=2EB.deg(V尸EC.D.解；C為握手定理。1

5、5 .有向完全圖D=<V,E>,則圖D的邊數(shù)是(D).A.E(E1)/2B.V(V1)/2C.E(E1)D.V(V-1)解：有向完全圖是任意倆點(diǎn)問(wèn)均有壹對(duì)方向相反的邊的圖，其邊數(shù)應(yīng)為D,即16 .給定無(wú)向圖G如右圖所示，下面給出的結(jié)點(diǎn)集子集中，不是點(diǎn)割集的為(A)A.b,dB.dC.a,cD.g,e17 .設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r=(A).A.ev+2B.v+e2C.ev2D.e+v+218 .無(wú)向圖G存于歐拉通路，當(dāng)且僅當(dāng)(D).A. G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)B. G中至多有倆個(gè)奇數(shù)度結(jié)點(diǎn)C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)D. G連通且至多有倆個(gè)奇數(shù)

6、度結(jié)點(diǎn)19 .設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的(A)條邊，才能確定G的壹棵生成樹(shù).A.B.C.D.20.已知壹棵無(wú)向樹(shù)T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各壹個(gè)，T的樹(shù)葉數(shù)為B.A.8B.5C.4D.3二、填空題1 .設(shè)集合,MAB=1,2,3=A,AB=B,A由=®,P(A)-P(B)=3,1,3,2,3,1,2,3.2 .設(shè)A,B為任意集合，命題AB的條件是.3 .設(shè)集合A有n個(gè)元素，那么A的幕集合P(A)的元素個(gè)數(shù)為.4 .設(shè)集合A=1,2,3,4,5,6,A上的二元關(guān)系且，則R的集合表示式為.5 .設(shè)集合A=1,2,3,4,5,B=1,2,3,R從A1JB的

7、二元關(guān)系，R=a,baA,bB且2a+b4則R的集合表示式為.6 .設(shè)集合A=0,1,2,B=0,2,4,R是A到B的二元關(guān)系，則R的關(guān)系矩陣Mr=7 .設(shè)集合A=1,2,3,4,B=6,8,12,A到B的二元關(guān)系R=那么RT=8 .設(shè)集合A=a,b,c,A上的二元關(guān)系R=<a,b>,<c.a>,S=<a,a>,<a,b>,<c,c>則(R?S)-=.9 .設(shè)集合A=a,b,c,A上的二元關(guān)系R=<a,b>,<b,a>,<b,c>,<c,d>,則二元關(guān)系R具有的性質(zhì)是反自反性.10 .設(shè)

8、集合A=1,2,3,4上的等價(jià)關(guān)系R=1,2,2,1,3,4,4,3Ia.那么A中各元素的等價(jià)類為1=2=1,2,3=4=3,4.11 .設(shè)A,B為有限集，且m,n,那末A和B間存于雙射，當(dāng)且僅當(dāng).12 .設(shè)集合A=1,2,B=a,b,那么集合A到B的雙射函數(shù)是13 .已知圖G中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)點(diǎn)，則G的邊數(shù)是15.14 .設(shè)給定圖G(如由圖所示)，則圖G的點(diǎn)b割集是.15 .設(shè)G=<V,E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若于G中每壹對(duì)結(jié)點(diǎn)度數(shù)之和大于等于,則于G中存于壹條漢密爾頓路.16 .設(shè)無(wú)向圖G=<V,E>是哈密頓圖，則V的任意非

9、空子集Vi,均有一Vi.17 .設(shè)有向圖D為歐拉圖，則圖D中每個(gè)結(jié)點(diǎn)的入度等于出度.18 .設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n>2)m條邊，當(dāng)時(shí)，k中存于歐拉回路.%彳、19 .圖g(如右圖所示)帶權(quán)圖中最小生Z/成樹(shù)的權(quán)是1267-8，,20 .連通無(wú)向圖G有6個(gè)頂點(diǎn)9條邊，從G中刪去4條邊才有可能得到G的壹棵生成樹(shù)T.三、判斷說(shuō)明題1 .設(shè)A、B、C為任意的三個(gè)集合，如果AUB=AUC,判斷結(jié)論B=C是否成立？且說(shuō)明理由.解：不壹定成立。反例：A=1,2,3,B=1,C=32 .如果Ri和R2是A上的自反關(guān)系，判斷結(jié)論：“R-1i、R1UR2、RiR2是自反的”是否成立？且說(shuō)明理由.3 .設(shè)R

10、,S是集合A上傳遞的關(guān)系，判斷RS是否具有傳遞性，且說(shuō)明理由.4 .若偏序集A,R的哈斯圖如右圖所示，則集合A的最小元為1,最大元不存于.解：結(jié)論正確。5 .若偏序集，R的哈斯圖如右圖所示，則集合A的極大元為a,f;最大元不存于.解：結(jié)論正確6 .圖G（如右圖）能否壹筆畫(huà)出？說(shuō)明理由.若能畫(huà)出，請(qǐng)寫(xiě)出壹條通路或回路.7 .判斷下圖的樹(shù)是否同構(gòu)？說(shuō)明理由.8 .給定倆個(gè)圖Gi, G2 （如下圖所示）,試判斷它們是否為歐拉圖、哈密頓圖？且說(shuō)明理由.9 .判別圖G(如下圖所示)是不是平面圖，且說(shuō)明理由.10 .于有6個(gè)結(jié)點(diǎn)，12條邊的簡(jiǎn)單平面連通圖中，每個(gè)面有幾條邊圍成？為什么？四、計(jì)算題1 .設(shè)，

11、求：(1)(AB)C;(2)P(A)P(C);(3)AB.2.設(shè)集合A=a,b,c,B=b,d,e,求BA;(2)AB;(3)A-B;(4)BA.3.設(shè)A=1,2,3,4,5,6,7,8,9,10,11,12,R是A上的整除關(guān)系，B=2,4,6.(1)寫(xiě)出關(guān)系R的表小式；（2）畫(huà)出關(guān)系R的哈斯圖；（3）求出集合B的最大元、最小元解：（1）解：（2）畫(huà)出哈斯圖（見(jiàn)課堂答疑）解：（3）B=2，4，6，B的最小元為2，B沒(méi)有最大元。4.設(shè)集合A=a,b,c,d上的二元關(guān)系R的關(guān)系圖如右圖所示（ 1）寫(xiě)出R的表達(dá)式；（ 2）寫(xiě)出R的關(guān)系矩陣；（ 3）求出R2（ .設(shè)人=0,1,2,3,4,R=<

12、x,y>|xA,yA且x+y<0,S=<x,y>|xA，yA且x+y<=3，試求R，S，RS，R-1，S-1，r（R），s（R），t（R），r（S），s（S），t（S）（ 設(shè)圖GV，E，其中Va1,a2,a3,a4,a5,Ea1,a2，a2,a4，a3,a1，a4,a5，a5,a2（ 1）試給出G的圖形表示；（ 2）求G的鄰接矩陣；（ 3）判斷圖D是強(qiáng)連通圖、單側(cè)連通圖仍是弱連通圖？( 設(shè)圖G=<V，E>，V=v1，v2，v3，v4，v5，E=（v1,v2），（v1,v3），（v2,v3），（v2,v4），（v3,v4），（v3,v5），（v4,v5）

13、（ 1）試給出G的圖形表示；（ 2）寫(xiě)出其鄰接矩陣；（ 3）求出每個(gè)結(jié)點(diǎn)的度數(shù)（ 4）畫(huà)出圖G的補(bǔ)圖的圖形解：（1）畫(huà)出G的圖形( 圖G=<V,E>，其中V=a,b,c,d,e,f，E=(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(d,f),(e,f),對(duì)應(yīng)邊的權(quán)值依次為5,2,1，2，6，1，9，3及8( 1)畫(huà)出G的圖形；( 2)寫(xiě)出G的鄰接矩陣；( 3)求出G權(quán)最小的生成樹(shù)及其權(quán)值9 已知帶權(quán)圖G如右圖所示試( 1)求圖G的最小生成樹(shù)；( 2)計(jì)算該生成樹(shù)的權(quán)值10 設(shè)有壹組權(quán)為2,3,5,7,11,13,17,19,23,29,31,試( 1)畫(huà)出相應(yīng)的最優(yōu)二叉樹(shù)；( 2)計(jì)算它們的權(quán)值五、證明題1 試證明集合等式：A(BC)=(AB)(AC)2 .證明對(duì)任意集合A,B,C,有.3 設(shè)R是集合A上的