1、班級： 學號： 姓名： 裝 訂 線 杭州師范大學錢江學院2014 2015 學年第二學期期末試卷_ 班 離散數學 （B）卷 命題教師_田正平_題目一二三四五總分分值2020202020100得分一、 判斷題（對的打Ú，錯的打´；每空2分，共20分）得分1、 “若鳥會飛，則地球比太陽小。” 是假命題。（´ ）2、 。（ Ú ）3、 （ Ú ）4、 有限偏序集必定存在極大元。（ Ú ）5、 反對稱關系一定不是對稱關系。（ ´ ）6、 設集合上的關系的關系矩陣是，則關系是偏序關系。（ Ú ）7、 偶圖G的頂點個數是奇數，

2、則G不是哈密頓圖。（ Ú ）8、 在圖G中若所有的頂點度數都是偶數，則G是歐拉圖。（ ´ ）9、若圖G不是平面圖則圖G一定含有一個子圖它是或。（ ´ ） 10、沒有基本回路且有n1條邊的n階圖是樹。（ Ú ）二、填空題（每空4分，共20分）得分1、將命題：“明天我去北京或上海出差。”符號化。 解：設命題P：明天我去北京出差；Q：明天我去上海出差。則命題：“明天我去北京或上海出差。”可以符號化為： 2、集合X上的等價關系R。 解：集合X上的等價關系R是指關系R是集合X上的自反，對稱和傳遞關系。 3、 基本通路。 解：基本通路是一條沒有頂點重復的通路。4、

3、輪圖的色數5、簡單圖的聯通分支數，則。三、選擇題（每題4分，共20分） 得分1、下面蘊含永真式中，錯誤的是（ D ）（A） (B)(C) (D) 2、設集合上的關系是整除關系，則關系（ D ） （A）有最大元，有最小元 (B)有最大元，無最小元 (C) 無最大元，有最小元 (D) 無最大元，無最小元3、圖G的鄰接矩陣，則圖G（ C ）（A）有歐拉通路，有哈密頓回路 (B)有歐拉回路，無哈密頓通路 (C) 無歐拉通路，無哈密頓回路 (D) 無歐拉回路，有哈密頓通路 4、設是實部不為零的復數數集，下面關系中是等價關系的是（ C ）（A） (B) (C) (D) 5、 和謂詞公式等值的是（ B ）

4、（A） (B) (C ) (D) 四、計算題（每題4分，共20分）得分1、 化簡命題公式。解： 2、集合上的關系，求關系的傳遞閉包。解： 所以： 3、在復數集上定義關系，給出這個等價類的幾何說明。 解： 所以等價類是復平面上平行于實軸的直線。4、 圖的鄰接矩陣，求從頂點到頂點長度為3的不同通路的個數。 解： 所以頂點到頂點長度為3的不同通路的個數是6。 5、設集合上的關系是整除關系, 寫出偏序關系的極大元、極小元。 解：偏序關系的極大元是18,20；極小元是2,3,5五、證明題（每題10分，共20分）得分1、 圖G的最小度數。證明：圖G有基本回路。證明：因為G至少有k條邊，所以有基本通路存在。由定理知基本通路的長度不大于n-1。設P是所有基本通路中長度最長的一條，v分別是基本通路的終點。因為，從頂點v出發至少還有一條邊v, u，頂點u必定在基本回路中出現，否則的話我們得到一條新的基本通路P+v,u,它比基本通路P還要長，這和P是所有基本通路中長度最長的一條這一事實相矛盾。所以G中必有回路存在。從而圖G有基本回路。 2、 證明：有限偏序集必有極小元存在。 證明：任意取 ，如果不是極小元，那么存在，使得；如果不是極小