離散數(shù)學(xué)(B)答案2015

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

2、則G不是哈密頓圖。（ Ú ）8、 在圖G中若所有的頂點(diǎn)度數(shù)都是偶數(shù)，則G是歐拉圖。（ ´ ）9、若圖G不是平面圖則圖G一定含有一個(gè)子圖它是或。（ ´ ） 10、沒有基本回路且有n1條邊的n階圖是樹。（ Ú ）二、填空題（每空4分，共20分）得分1、將命題：“明天我去北京或上海出差?！狈?hào)化。 解：設(shè)命題P：明天我去北京出差；Q：明天我去上海出差。則命題：“明天我去北京或上海出差?！笨梢苑?hào)化為： 2、集合X上的等價(jià)關(guān)系R。 解：集合X上的等價(jià)關(guān)系R是指關(guān)系R是集合X上的自反，對(duì)稱和傳遞關(guān)系。 3、 基本通路。 解：基本通路是一條沒有頂點(diǎn)重復(fù)的通路。4、

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

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