電大 離散數(shù)學(xué) 形成性考核冊(cè) 作業(yè)(三)答案

編號(hào)：時(shí)間：2021年x月x日書山有路勤為徑，學(xué)海無涯苦作舟頁(yè)碼：第8頁(yè) 共8頁(yè)離散數(shù)學(xué)形成性考核作業(yè)（三）集合論與圖論綜合練習(xí)本課程形成性考核作業(yè)共4次，內(nèi)容由中央電大確定、統(tǒng)一布置。本次形考作業(yè)是第三次作業(yè)，大家要認(rèn)真及時(shí)地完成圖論部分的形考作業(yè)，字跡工整，抄寫題目，解答題有解答過程。一、單項(xiàng)選擇題1若集合A2，a， a ，4，則下列表述正確的是( B )Aa， a ÎA B a ÍA C2ÎA DÎA 2設(shè)B = 2, 3, 4, 2，那么下列命題中錯(cuò)誤的是（ B ） A2B B2, 2, 3, 4ÌB C2ÌB D2, 2ÌB3若集合A=a，b， 1，2 ，B= 1，2，則（ B ） AB Ì A，且BÎA BBÎ A，但BËA CB Ì A，但BÏA DBË A，且BÏA 4設(shè)集合A = 1, a ，則P(A) = ( C ) A1, a B,1, a C,1, a, 1, a D1, a, 1, a 5設(shè)集合A = 1，2，3，4，5，6 上的二元關(guān)系R =a , bêa , 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從A到B的二元關(guān)系，R =a , bêaA，bB且則R具有的性質(zhì)為（ ） A自反的 B對(duì)稱的 C傳遞的 D反自反的注意：此題有誤！自反性、反自反性、對(duì)稱性、反對(duì)稱性以及傳遞性指某一個(gè)集合上的二元關(guān)系的性質(zhì)。 7設(shè)集合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(chǔ)自反性，對(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(chǔ)是等價(jià)關(guān)系但不是偏序關(guān)系 B是偏序關(guān)系但不是等價(jià)關(guān)系24135C既是等價(jià)關(guān)系又是偏序關(guān)系 D不是等價(jià)關(guān)系也不是偏序關(guān)系 10設(shè)集合A = 1 , 2 , 3 , 4 , 5上的偏序關(guān)系的哈斯圖如右圖所示,若A的子集B = 3 , 4 , 5，則元素3為B的（ C ） A下界 B最大下界 C最小上界 D以上答案都不對(duì) 11設(shè)函數(shù)f：R R，f (a) = 2a + 1；g：R R，g(a) = a 2則（ C ）有反函數(shù) Ag·f Bf·g Cf Dg 12設(shè)圖G的鄰接矩陣為則G的邊數(shù)為( D )A5 B6 C3 D413下列數(shù)組中，能構(gòu)成無向圖的度數(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 )Adeg(V)=2½E½ Bdeg(V)=½E½C D解；C為握手定理。15有向完全圖D<V，E>， 則圖D的邊數(shù)是( D )A½E½(½E½1)/2 B½V½(½V½1)/2C½E½(½E½1) D½V½(½V½1)agbdfce解：有向完全圖是任意兩點(diǎn)間都有一對(duì)方向相反的邊的圖，其邊數(shù)應(yīng)為D，即 16給定無向圖G如右圖所示，下面給出的結(jié)點(diǎn)集子集中，不是點(diǎn)割集的為（ A ） Ab, d Bd Ca, c Dg, e 17設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( A )Aev2 Bve2 Cev2 Dev218無向圖G存在歐拉通路，當(dāng)且僅當(dāng)( D )AG中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) BG中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)CG連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) DG連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)19設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( A )條邊，才能確定G的一棵生成樹A B C D 20已知一棵無向樹T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為 B A8 B5 C4 D 3二、填空題 1設(shè)集合，則AB= 1，2，3=A ，AB= B ，A B= 3 ，P(A)-P(B )= 3,1,3,2,3,1,2,3 2設(shè)A, B為任意集合，命題A-B=Æ的條件是 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從A到B的二元關(guān)系， R =a , bêaA，bB且2a + b4則R的集合表示式為 6設(shè)集合A=0,1,2,B=0,2,4,R是A到B的二元關(guān)系，則R的關(guān)系矩陣MR7設(shè)集合A=1, 2, 3, 4 ，B=6, 8, 12， A到B的二元關(guān)系R那么R1 8設(shè)集合A=a,b,c，A上的二元關(guān)系R=<a,b>,<c.a>，S=<a,a>,<a,b>,<c,c>則(R·S)1= 9設(shè)集合A=a,b,c，A上的二元關(guān)系R=<a, b>, <b, a>, <b, c>, <c, d>，則二元關(guān)系R具有的性質(zhì)是反自反性 10設(shè)集合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為有限集，且|A|=m，|B|=n,那末A與B間存在雙射，當(dāng)且僅當(dāng) 12設(shè)集合A=1, 2,B=a, b，那么集合A到B的雙射函數(shù)是 a b f ce d圖G 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)割集是 15設(shè)G=<V，E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于 ，則在G中存在一條漢密爾頓路16設(shè)無向圖G<V,E>是哈密頓圖，則V的任意非空子集V1，都有 £½V1½17設(shè)有向圖D為歐拉圖，則圖D中每個(gè)結(jié)點(diǎn)的入度 等于出度68792212318設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng) 時(shí)，K中存在歐拉回路19圖G（如右圖所示）帶權(quán)圖中最小生成樹的權(quán)是 12 20連通無向圖G有6個(gè)頂點(diǎn)9條邊，從G中刪去 4 條邊才有可能得到G的一棵生成樹T三、判斷說明題1設(shè)A、B、C為任意的三個(gè)集合，如果AB=AC，判斷結(jié)論B=C 是否成立？并說明理由解：不一定成立。反例：A=1，2，3，B=1，C=31oo846952772如果R1和R2是A上的自反關(guān)系，判斷結(jié)論：“R-11、R1R2、R1ÇR2是自反的” 是否成立？并說明理由 3設(shè)R，S是集合A上傳遞的關(guān)系，判斷R S是否具有傳遞性，并說明理由 4若偏序集<A，R>的哈斯圖如右圖所示，則acbedf集合A的最小元為1，最大元不存在解：結(jié)論正確。5若偏序集<A，R>的哈斯圖如右圖所示，則 集合A的極大元為a，f；最大元不存在 解：結(jié)論正確。v1v2v3v5v4dbacefghn圖G6圖G(如右圖)能否一筆畫出？說明理由若能畫出，請(qǐng)寫出一條通路或回路 7判斷下圖的樹是否同構(gòu)？說明理由 (a)(b)(c)8給定兩個(gè)圖G1，G2（如下圖所示），試判斷它們是否為歐拉圖、哈密頓圖？并說明理由abcdefg圖G2圖G1 v1v2v3v6v5v4 9判別圖G(如下圖所示)是不是平面圖，并說明理由 10在有6個(gè)結(jié)點(diǎn)，12條邊的簡(jiǎn)單平面連通圖中，每個(gè)面有幾條邊圍成？為什么？ 四、計(jì)算題1設(shè)，求：（1）(AÇB)ÈC； （2）P(A)P(C)； （3）AÅB2設(shè)集合Aa, b, c，B=b, d, e，求（1）BÇA； （2）AÈB； （3）AB； （4）BÅA3設(shè)A=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12，R是A上的整除關(guān)系，B=2, 4, 6（1）寫出關(guān)系R的表示式；（2）畫出關(guān)系R的哈斯圖；（3）求出集合B的最大元、最小元解：（1）解：（2）畫出哈斯圖（見課堂答疑）解：（3）B=2，4，6，B的最小元為2，B沒有最大元。adbc4設(shè)集合Aa, b, c, d上的二元關(guān)系R的關(guān)系圖如右圖所示（1）寫出R的表達(dá)式；（2）寫出R的關(guān)系矩陣； （3）求出R25設(shè)A=0，1，2，3，4，R=<x，y>|xÎA，yÎA且x+y<0，S=<x，y>|xÎA，yÎA且x+y<=3，試求R，S，R°S，R-1，S-1，r(R)，s(R)，t(R)，r(S)，s(S)，t(S)6設(shè)圖G=<V，E>，其中V=a1, a2, a3, a4, a5,E=<a1, a2>，<a2, a4>，<a3, a1>，<a4, a5>，<a5, a2>（1）試給出G的圖形表示； （2）求G的鄰接矩陣；（3）判斷圖D是強(qiáng)連通圖、單側(cè)連通圖還是弱連通圖？7設(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) （1）試給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)（4）畫出圖G的補(bǔ)圖的圖形解：（1）畫出G的圖形8圖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）畫出G的圖形；（2）寫出G的鄰接矩陣；51063478921（3）求出G權(quán)最小的生成樹及其權(quán)值 9已知帶權(quán)圖G如右圖所示試（1）求圖G的最小生成樹；（2）計(jì)算該生成樹的權(quán)值10設(shè)有一組權(quán)為2,3,5,7,11,13,17,19,23,29,31,試（1）畫出相應(yīng)的最優(yōu)二叉樹；（2）計(jì)算它們的權(quán)值 五、證明題 1試證明集合等式：AÈ (BÇC)=(AÈB) Ç (AÈC) 2證明對(duì)任意集合A，B，C，有 3設(shè)R是集合A上的對(duì)稱關(guān)系和傳遞關(guān)系，試證明：若對(duì)任意aÎA，存在bÎA，使得<a, b>ÎR，則R是等價(jià)關(guān)系 4若非空集合A上的二元關(guān)系R和S是偏序關(guān)系，試證明：也是A上的偏序關(guān)系 5若無向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定是連通的 6設(shè)G是連通簡(jiǎn)單平面圖，則它一定有一個(gè)度數(shù)不超過5的結(jié)點(diǎn)（提示：用反證法） 7設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖 8證明任何非平凡樹至少有2片樹葉第 8 頁(yè) 共 8 頁(yè)