南京郵電大學(xué)2010/2011學(xué)年 第一學(xué)期圖論與代數(shù)系統(tǒng)清欠考試 試卷本試卷共 4 頁； 考試時(shí)間 110 分鐘；裝 訂 線 內(nèi) 不 要 答 題自 覺 遵 守 考 試 規(guī) 則，誠 信 考 試，絕 不 作 弊 專業(yè) 班級(jí) 學(xué)號(hào) 姓名 題號(hào)一二三四總分分?jǐn)?shù)得分一、填空題（20分，每空2分）1由布爾格，可以誘導(dǎo)一個(gè)代數(shù)系統(tǒng)，這個(gè)代數(shù)系統(tǒng)稱為 。2在代數(shù)系統(tǒng)中，對(duì)運(yùn)算的幺元是_，對(duì)運(yùn)算的幺元是_。3設(shè)是一個(gè)偏序集，則稱為格。4有限布爾代數(shù)的元素的個(gè)數(shù)必定等于。5n個(gè)結(jié)點(diǎn)的無向完全圖的邊數(shù)為 。6給定無孤立結(jié)點(diǎn)圖G，G中的歐拉路是指 。7若一條路中所有的邊均不相同，稱作 。8一個(gè)代數(shù)系統(tǒng)，其中是非空集合，是上的一個(gè)二元運(yùn)算。如果：（1），（2） ，則稱代數(shù)系統(tǒng)為半群。得分二、判別題，正確的打、錯(cuò)誤的打。（20分，每題2分）1分配格一定是布爾格。 （）2自然數(shù)集合上的減法運(yùn)算是封閉的。 （）3強(qiáng)連通圖一定是單側(cè)連通的。 （）4群中一定有零元。 （）5代數(shù)系統(tǒng)每個(gè)元素都有逆元。 （）6元素個(gè)數(shù)為4的格一定是布爾格。 （）7一個(gè)圖的生成子圖必是唯一的。 （）8存在割點(diǎn)的連通圖其連通度必為1。 （）9對(duì)于兩個(gè)圖，如果結(jié)點(diǎn)數(shù)目相等，邊數(shù)相等，度數(shù)相等的結(jié)點(diǎn)數(shù)目也相等，則這 兩個(gè)圖同構(gòu)。 （）10在任何有向圖中，所有節(jié)點(diǎn)的入度之和等于所有節(jié)點(diǎn)的出度之和。 （ ） 得分三、解答題（50分，每題10分）1. 請(qǐng)畫出兩個(gè)含有5個(gè)元素的非分配格。2. 寫出下圖的鄰接矩陣，并求出可達(dá)性矩陣。 3. 下面各圖中，哪些可以一筆畫？哪些可以從任一點(diǎn)一筆畫？ （a） (b) (c) a4 判斷所給的圖G是否為漢密爾頓圖，如果是，則給出汗密爾頓回路，否則證明其不是漢密爾頓圖。fedcb5. 求下圖的一棵最小生成樹。 裝 訂 線 內(nèi) 不 要 答 題自 覺 遵 守 考 試 規(guī) 則，誠 信 考 試，絕 不 作 弊得分四、證明題（10分）1給定代數(shù)系統(tǒng)R，+，其中，R為實(shí)數(shù)集，+