《電大 離散數(shù)學 形成性考核冊 作業(yè)(三)答案.》由會員分享，可在線閱讀，更多相關《電大 離散數(shù)學 形成性考核冊 作業(yè)(三)答案.（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、8 離散數(shù)學形成性考核作業(yè)（三） 集合論與圖論綜合練習 本課程形成性考核作業(yè)共4次，內(nèi)容由中央電大確定、統(tǒng)一布置。本次形考作業(yè)是第三次作業(yè)，大家要認真及時地完成圖論部分的形考作業(yè)，字跡工整，抄寫題目，解答題有解答過程。 一、單項選擇題 1．若集合A＝{2，a，{ a }，4}，則下列表述正確的是( B )． A．{a，{ a }}?A B．{ a }íA C．{2}?A D．?A 2．設B = { {2}, 3, 4, 2}，那么下列命題中錯誤的是（ B

2、 ）． A．{2}B B．{2, {2}, 3, 4}ìB C．{2}ìB D．{2, {2}}ìB 3．若集合A={a，b，{ 1，2 }}，B={ 1，2}，則（ B ）． A．B ì A，且B?A B．B? A，但B?A C．B ì A，但B?A D．B? A，且B?A 4．設集合A = {1, a }，則P(A) = ( C )． A．{{1}, {a}}

3、 B．{,{1}, {a}} C．{,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 5．設集合A = {1，2，3，4，5，6 }上的二元關系R ={a , bêa , bA , 且a +b = 8}，則R具有的性質(zhì)為（ B ）． A．自反的 B．對稱的 　　C．對稱和傳遞的　 D．反自反和傳遞的 6．設集合A = {1，2，3，4，5 }，B = {1，2，3}，R從A到B的二元關系，

4、 R ={a , bêaA，bB且} 則R具有的性質(zhì)為（ ）． A．自反的 B．對稱的 C．傳遞的 D．反自反的 [注意]：此題有誤！自反性、反自反性、對稱性、反對稱性以及傳遞性指 某一個集合上的二元關系的性質(zhì)。 7．設集合A={1 , 2 , 3 , 4}上的二元關系 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．對稱

5、 D．以上都不對 8．非空集合A上的二元關系R，滿足( A )，則稱R是等價關系． A．自反性，對稱性和傳遞性 B．反自反性，對稱性和傳遞性 　　C．反自反性，反對稱性和傳遞性　 D．自反性，反對稱性和傳遞性 9．設集合A={a, b}，則A上的二元關系R={，}是A上的( C )關系． A．是等價關系但不是偏序關系　　 B．是偏序關系但不是等價關系 2 4 1 3 5 　　C．既是等價關系又是偏序關系　　 D．不是等價關系也不是偏序關系 10．設集合A = {1 , 2

6、 , 3 , 4 , 5}上的偏序關系 的哈斯圖如右圖所示,若A的子集B = {3 , 4 , 5}， 則元素3為B的（ C ）． A．下界 B．最大下界 C．最小上界 D．以上答案都不對 11．設函數(shù)f：R R，f (a) = 2a + 1；g：R R，g(a) = a 2．則（ C ）有反函數(shù)． A．g·f B．f·g C．f D．g 12．設圖G的鄰接矩陣為 則G的邊數(shù)為( D )． A．5 B．6

7、 C．3 D．4 13．下列數(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．設圖G＝，則下列結(jié)論成立的是 ( C )． A．deg(V)=2?E? B．deg(V)=?E? C． D． 解；C為握手定理。 15．有向完全圖D＝， 則圖D的邊數(shù)是( D )．

8、 A．?E?(?E?－1)/2 B．?V?(?V?－1)/2 C．?E?(?E?－1) D．?V?(?V?－1) a g b d f c e 解：有向完全圖是任意兩點間都有一對方向相反的邊的 圖，其邊數(shù)應為D，即 16．給定無向圖G如右圖所示，下面給出的結(jié)點 集子集中，不是點割集的為（ A ） A．{b, d} B．kywiwiy4em C．{a, c} D．{g, e} 17．設G是連通平面圖，有v個結(jié)點，e條

9、邊，r個面，則r= ( A )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 18．無向圖G存在歐拉通路，當且僅當( D )． A．G中所有結(jié)點的度數(shù)全為偶數(shù) B．G中至多有兩個奇數(shù)度結(jié)點 C．G連通且所有結(jié)點的度數(shù)全為偶數(shù) D．G連通且至多有兩個奇數(shù)度結(jié)點 19．設G是有n個結(jié)點，m條邊的連通圖，必須刪去G的( A )條邊，才能確定G的一棵生成樹． A． B． C． D． 20．已知一棵無向樹T中有8個結(jié)點，4度，3度，2度的分支點

10、各一個，T的樹葉數(shù)為 B ． A．8 B．5 C．4 D． 3 二、填空題 1．設集合，則AB= {1，2，3}=A ，AB= B ，A – B= {3} ，P(A)-P(B )= {{3},{1,3},{2,3},{1,2,3} } ． 2．設A, B為任意集合，命題A-B=?的條件是 ． 3．設集合A有n個元素，那么A的冪集合P(A)的元素個數(shù)為 ． 4．設集

11、合A = {1，2，3，4，5，6 }，A上的二元關系且}，則R的集合表示式為 ． 5．設集合A = {1，2，3，4，5 }，B = {1，2，3}，R從A到B的二元關系， R ={a , bêaA，bB且2a + b4} 則R的集合表示式為 ． 6．設集合A={0,1,2},B={0,2,4},R是A到B的二元關系， 則R的關系矩陣MR＝ 　　　　　　　　　　　　　　　　?。? 7．設集合A={1, 2, 3, 4 }，B={6, 8, 12}， A到B的二元關系 R＝ 那么R－1＝

12、 8．設集合A={a,b,c}，A上的二元關系 R={,}，S={,,} 則(R·S)－1=　　　　　　　　　　?。? 9．設集合A=｛a,b,c｝，A上的二元關系R={, , , }，則二元關系R具有的性質(zhì)是　反自反性　　　　　　　?。? 10．設集合A = {1 , 2 , 3 , 4 }上的等價關系 R = {1 , 2，2 , 1，3 , 4，4 , 3}IA． 那么A中各元素的等價類為 [1]=[2]={1,2}, [3]=[4]={3,4}

13、 ． 11．設A，B為有限集，且|A|=m，|B|=n,那末A與B間存在雙射，當且僅當 ． 12．設集合A={1, 2},B={a, b}，那么集合A到B的雙射函數(shù)是 ． a　 b f 　 c e d 圖G 13．已知圖G中有1個1度結(jié)點，2個2度結(jié)點，3個3度結(jié)點，4個4度結(jié)點，則G的邊數(shù)是 15 ． 14．設給定圖G(如由圖所示)，則圖G的點 割集是 {} ．

14、 15．設G=是具有n個結(jié)點的簡單圖，若在G中每一對結(jié)點度數(shù)之和大于等于 ，則在G中存在一條漢密爾頓路． 16．設無向圖G＝是哈密頓圖，則V的任意非空子集V1，都有 　 　 ￡?V1?． 17．設有向圖D為歐拉圖，則圖D中每個結(jié)點的入度 　等于出度?。? 6 8 7 9 2 2 1 2 3 18．設完全圖K有n個結(jié)點(n≥2)，m條 邊，當 時，K中存在歐拉回路． 19．圖G（如右圖所示）帶權(quán)圖中最小生 成樹的

15、權(quán)是 12 20．連通無向圖G有6個頂點9條邊，從 G中刪去 4 條邊才有可能得到G的一棵生成樹T． 三、判斷說明題 1．設A、B、C為任意的三個集合，如果A∪B=A∪C，判斷結(jié)論B=C 是否成立？并說明理由． 解：不一定成立。反例：A={1，2，3}，B={1}，C={3} 1 o o 8 4 6 9 5 2 7 7 2．如果R1和R2是A上的自反關系，判斷結(jié)論：“R-11、R1∪R2、R1?R2是自反的” 是否成立？并說明理由． 3．設R，S是集合A上傳遞的關系，判斷 R S是否具有傳遞性，并說明理由．

16、 4．若偏序集的哈斯圖如右圖所示，則 a c b e d f 集合A的最小元為1，最大元不存在． 解：結(jié)論正確。 5．若偏序集的哈斯圖如右圖所示，則 集合A的極大元為a，f；最大元不存在． 解：結(jié)論正確。 v1 v2 v3 v5 v4 d b a c e f g h n 圖G 6．圖G(如右圖)能否一筆畫出？說明理由． 若能畫出，請寫出一條通路或回路． 7．判斷下圖的樹是否同構(gòu)？說明理由． (a) (b) (c)

17、 8．給定兩個圖G1，G2（如下圖所示），試判斷它們是否為歐拉圖、哈密頓圖？并說明理由． a b c d e f g 圖G2 圖G1 v1 v2 v3 v6 v5 v4 9．判別圖G(如下圖所示)是不是平面圖，并說明理由． 10．在有6個結(jié)點，12條邊的簡單平面連通圖中，每個面有幾條邊圍成？為什么？ 四、計算題 1．設，求：　 （1）(A?B)è~C； （2）P(A)－P(C)； （3）A?B． 2．設集合A

18、＝{a, b, c}，B={b, d, e}，求 （1）B?A； （2）AèB； （3）A－B； （4）B?A． 3．設A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R是A上的整除關系，B={2, 4, 6}． （1）寫出關系R的表示式； （2）畫出關系R的哈斯圖； （3）求出集合B的最大元、最小元． 解：（1） 解：（2）畫出哈斯圖（見課堂答疑） 解：（3）B={2，4，6}，B的最小元為2，B沒有最大元。 a d b c 4．設集合A＝{a, b, c, d}上的二元關

19、系R的 關系圖如右圖所示． （1）寫出R的表達式； （2）寫出R的關系矩陣； （3）求出R2． 5．設A={0，1，2，3，4}，R={|x?A，y?A且x+y<0}，S={|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．設圖G=，其中V={a1, a2, a3, a4, a5}, E={，，，，} （1）試給出G的圖形表示； （2）求G的鄰接矩陣； （3）判

20、斷圖D是強連通圖、單側(cè)連通圖還是弱連通圖？ 7．設圖G=，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）求出每個結(jié)點的度數(shù) （4）畫出圖G的補圖的圖形． 解：（1）畫出G的圖形 8．圖G=，其中V={a, b, c, d, e, f }，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f),

21、(e, f) }，對應邊的權(quán)值依次為5，2，1，2，6，1，9，3及8． （1）畫出G的圖形； （2）寫出G的鄰接矩陣； 5 10 6 3 4 7 8 9 2 1 （3）求出G權(quán)最小的生成樹及其權(quán)值． 9．已知帶權(quán)圖G如右圖所示．試 （1）求圖G的最小生成樹； （2）計算該生成樹的權(quán)值． 10．設有一組權(quán)為2,3,5,7,11,13,17,19,23,29,31,試 （1）畫出相應的最優(yōu)二叉樹； （2）計算它們的權(quán)值． 五、證明題 1．試證明集合等式：Aè (B?C)=(AèB) ? (AèC)． 2．證明對任意集合A，B，C，有． 3．設R是集合A上的對稱關系和傳遞關系，試證明：若對任意a?A，存在b?A，使得?R，則R是等價關系． 4．若非空集合A上的二元關系R和S是偏序關系，試證明：也是A上的偏序關系． 5．若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定是連通的． 6．設G是連通簡單平面圖，則它一定有一個度數(shù)不超過5的結(jié)點．（提示：用反證法） 7．設連通圖G有k個奇數(shù)度的結(jié)點，證明在圖G中至少要添加條邊才能使其成為歐拉圖． 8．證明任何非平凡樹至少有2片樹葉． 8