北京工業(yè)大學2012017第一學期集合與圖論A卷

1、北京工業(yè)大學20162017學年第1學期集合與圖論考試試卷A卷考試說明：承諾：本人已學習了北京工業(yè)大學考場規(guī)則和北京工業(yè)大學學生違紀處分條例，承諾在考試過程中自覺遵守有關規(guī)定，服從監(jiān)考教師管理，誠信考試,做到不違紀、不作弊、不替考。若有違反，愿接受相應的處分。承諾人：學號：班號：。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。

2、。 。 。 。 。 。 。 。 。 。 。注：本試卷共也大題，共 10 頁，滿分 100 分，考試時必須使用卷后附加的統(tǒng)一答題紙和草稿紙。卷面成績匯總表（閱卷教師填寫）一、選擇題（8分）1、設人=1,2,3,則A上的二元關系有（C）個A.23;B.32;C.23D.32、設集合A=1,2,3,4,5上偏序關系的哈斯圖為（A）題號一一三四五滿分得分六七八九十總成績則子集B=2,3,4的最大元（極大元（）;極小元（）；上界（）；上A、無，4,2、3,4,1,1,4,4;B、無，4、5,2、3,4、 5,1,1,4,4;C、無，4,2、3,4、5,1,1,4,4;D、無，4,2、3,4,1,1,4,

3、無。上的關系R=|x+y=10且x,y-A,則R的性質為().A.自反的BC.傳遞且對稱的D二、判斷題(8分)1. (F)若R1、R2是非空集合A上的傳遞關系，則R1UR2是A上的傳遞關系。2. (F)設f是A到B的函數(shù)，g是B到C的函數(shù)，若gf是單射，則f是單射。3. (F)設正則5叉樹的樹葉數(shù)為17,則分支數(shù)為i=3(T)如果一個有向圖D是歐拉圖，則D是強連通圖B確界()；下界()；下確界().對稱的.反自反且傳遞的4.集合A=1,2,3,4,5,6,7,8(10分)證明:(AUB)-(AAB)=(B-A)U(A-B)證明：(AUB)-(AnB)=(AUB)n(AnB)根據(jù)De.Morga

4、n定律：(AnB)=AUB.(AUB)n(AnB)=(AUB)n(AUB)3分將(AUB)當作一個整體，利用分配律可知：(AUB)n(AUB)=(AUB)nA)U(AUB)nB)5分再次利用分配律：(AUB)nA)U(AUB)nB)=(AnA)U(BnA)U(AnB)U(BnB)=(U(BnA)U(AnB)U()7分=(BnA)u(AnB)=(B-A)U(A-B)10分|得分|四、(10分)R是A上一個二元關系，證明：若R是A上一個II等價關系，則S也是A上的一個等價關系，其中S描述如下：(1)SS=ca,bA|(a,bwA)人(對于某一個 cwA 有父 a,cwRMcc,bwR)I反的VaW

5、A,由R自反，J.(wR)/(a,aR),a,aS3分(2)S對稱的-a,bAa,bS=(wR)八(c,b*R)S 定義二(a,cwR)A(=R)R 對稱 nb,awSR 傳遞6分(3)S傳遞的_a,b,cA:a,bS:b,cS=(：a,dR)(:二 d,bR)(:二 b,eR)(：e,cR)二(a,bR)A(=R)R 傳遞=wSS 定義由(1)、(2)、(3)得；S是等價關系。10分I得分I.一一-七、（10分）用Dijkstra徑及路長最短路。算法求圖中起點V1-V7的最短路|得分|五、（10分）是從Af:ATB到B的函數(shù)，定義一個函數(shù)I|對任意有證明：bwB若g（b）=x|（xwA）A（

6、f（x）=b）f是A至UB的滿射，則g是從B到2A的單射。證明：Vbjd 三B,(b1*)f?兩射 a1,a2-A使 f(a1)=b,f(az)=b2,且 f(a1)#2),由于是函數(shù)，二 a1#a2又 g(bj=x|(xA)(他)電),g(bz)=x|(xA)(W 二 awg(b1),a?g(bj 但 a1年gQ),a?筆 g(b1)二 g(bO豐gM)由 b1,b2任意Tt知，g 為單射解）分析：方程右邊為2 2n n特征根：q=2（二重根），.*特解：a an n=An2An n2 22 2n n4A(n-1)n-1)2 22 2n n* *+4A(n-2f2n=2n6分2n n22n

7、n2、2nn,nn,展開：An2 2-2A(n-2n+1)2 2+A(n-4n+4)2=22=28分整理：2A2 2n n=2=2n n待定系數(shù)：A=110分2 2-n_n-n_n1 12-n_-n_1 12n2n通解：a an=Bi2 2+B2n2 2+n2=B2=B1*B B2 2n*n*n2n2。其中B1、呼為任意常數(shù)。2 2 5,證明G或G中必I1含圈.反證法.否則G與G的各連通分支都是樹.2分設G與G的連通分支分別為G,G,，G和GlG2,，Gs，.令ni,m與nl,E分別為G,G的頂點數(shù)和邊數(shù).4分n（n_1）ssss于是2C 叫m,jC（n）?。╪,j_1）=2n（ss,M2”27分2i1j4i_1jX得n24n+40解出1n5.10分|得分|十、(10分)設G是連通的簡單的平面圖，面數(shù)r12