離散數(shù)學(xué)期末考試卷

1、安徽大學(xué)2004-2005學(xué)年第二學(xué)期離散數(shù)學(xué)期末考試試卷（A卷）一、單項(xiàng)選擇（在備選答案中選出一個(gè)正確答案，并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每題2分，共20分）1 在自然數(shù)集上，下列哪種運(yùn)算是可結(jié)合的？（ ）A. B. C. D. 2 下列代數(shù)系統(tǒng)<，*>中，哪個(gè)是群？（ ）A. ，*是模7加法 B. （有理數(shù)集合），*是一般乘法 C. （整數(shù)集合），*是一般減法 D. ，*是模11乘法3 若<，*>是<，*>的真子群，且，則有（ ）。A. 整除 B. 整除 C. 整除且 整除 D. 不整除且 不整除4 下面哪個(gè)集合關(guān)于指定的運(yùn)算構(gòu)成環(huán)？（ ）A. ，關(guān)于數(shù)

2、的加法和乘法B.階實(shí)數(shù)矩陣，關(guān)于矩陣的加法和乘法C. ，關(guān)于數(shù)的加法和乘法D. ，關(guān)于矩陣的加法和乘法5 在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系為（ ）。A. 域一定是整環(huán) B.域不一定是整環(huán) C. 整環(huán)一定是域 D. 域一定不是整環(huán)6 是自然數(shù)集，是小于等于關(guān)系，則是（ ）。A.有界格 B.有補(bǔ)格 C. 分配格 D. 有補(bǔ)分配格7 圖1-1給出的哈斯圖表示的格中哪個(gè)元素?zé)o補(bǔ)元？（ ）abcdefgA. B. C. D. 圖1-18 給定下列序列，可構(gòu)成無(wú)向簡(jiǎn)單圖的結(jié)點(diǎn)度數(shù)序列的是（ ）。A.（1，1，2，2，3） B.（1，3，4，4，5）C.（0，1，3，3，3） D.（1，1，2，2，2）9 歐拉

3、回路是（ ）。A.路徑 B.簡(jiǎn)單回路 C.既是基本回路也是簡(jiǎn)單回路 D.既非基本回路也非簡(jiǎn)單回路10 哈密爾頓回路是（ ）。A.路徑 B.簡(jiǎn)單回路 C.既是基本回路也是簡(jiǎn)單回路 D.既非基本回路也非簡(jiǎn)單回路二、填空題（以下每個(gè)下劃線為一空，請(qǐng)按要求填入合適的內(nèi)容。每空2分，共30分）a b ca a b a b cc c 1 設(shè)是非空有限集，代數(shù)系統(tǒng)中，對(duì)運(yùn)算的單位元是，零元是，對(duì)運(yùn)算的單位元是。 表2-12 在運(yùn)算表2-1中空白處填入適當(dāng)符號(hào)，使成為群。，。3 設(shè)，是群的子群，其中，是模12加法，則有個(gè)真子群，的左陪集，。4設(shè)是一個(gè)布爾代數(shù)，如果在上定義二元運(yùn)算為：，則是一個(gè)。5 任何一個(gè)具

4、有個(gè)元素的有限布爾代數(shù)都是。6 若連通平面圖有4個(gè)結(jié)點(diǎn)，3個(gè)面，則有條邊。7 一棵樹有兩個(gè)結(jié)點(diǎn)度數(shù)為2，一個(gè)結(jié)點(diǎn)度數(shù)為3，三個(gè)結(jié)點(diǎn)度數(shù)為4，它有個(gè)度數(shù)為1的結(jié)點(diǎn)。8 無(wú)向圖是由（）棵數(shù)組成的森林，至少要添加條邊才能使成為一棵樹。三、求解題（20分） 1 試寫出中每個(gè)子群及其相應(yīng)的左陪集。 （6分）274412313652 若一個(gè)有向圖是歐拉圖，它是否一定是強(qiáng)連通的？若一個(gè)有向圖是強(qiáng)連通的，它是否一定是歐拉圖？說明理由。 （6分）3 有向圖如圖3-1所示。（1）求的鄰接矩陣； （2分）（2）中到長(zhǎng)度為4的路徑有幾條？ （2分）（3）中到自身長(zhǎng)度為3的回路有幾條？ （2分）（4）是哪類連通圖？ （

5、2分）四、證明題（30分）1 設(shè)是一群，。定義：，。證明也是一群。 （10分）2 證明：（1）證明在格中成立：。 （5分）（2）證明布爾恒等式：。 （5分）3 證明：（1）在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中，每個(gè)面由3條邊圍成。 （5分）（2）證明當(dāng)每個(gè)結(jié)點(diǎn)的度數(shù)大于等于3時(shí)，不存在有7條邊的簡(jiǎn)單連通平面圖。 （5分）安徽大學(xué)2004-2005學(xué)年第二學(xué)期離散數(shù)學(xué)期末考試試卷（A卷）參考答案一、單項(xiàng)選擇1B; 2.D; 3.A; 4.C; 5.A; 6.C; 7.B; 8.D; 9.B; 10.C.二、填空題1 ，； 2 ，； 3 5，； 4 交換群； 5 同構(gòu)；6 5； 7 9； 8 。三

6、、求解題1 解：子群有：，。的左陪集為：，的左陪集為：，的左陪集為：，2 答：（1）一個(gè)有向歐拉圖一定是強(qiáng)連通圖。因?yàn)槭菤W拉圖，存在歐拉回路，中的每個(gè)結(jié)點(diǎn)至少在中出現(xiàn)一次。因而中任意兩點(diǎn)，都在中，相互可達(dá)，故是強(qiáng)連通的。（2）一個(gè)強(qiáng)連通圖不一定是有向歐拉圖。因?yàn)閺?qiáng)連通圖中每個(gè)結(jié)點(diǎn)的入度不一定等于其出度。3 解：（1） （2）由中可知，到長(zhǎng)度為4的路徑有條（56748，）。（3）由中可知，到自身長(zhǎng)度為3的回路有1條（）。（4）是單向連通圖。四、證明題1 證明：顯然是上的二元運(yùn)算（即滿足封閉性），要證是群，需證結(jié)合律成立，同時(shí)有單位元，每個(gè)元素有逆元。 ，有 運(yùn)算是可結(jié)合的。 其次，是的單位元。事實(shí)上，有； 最后證明，是在中的逆元。事實(shí)上， 由以上證明，是群。2 證明：（1） （公式(13)分配不等式）又因?yàn)?，所以。?）因?yàn)?，所以有?（吸收律）即等式成立。 3 證明：（1）因圖中結(jié)點(diǎn)數(shù)和邊數(shù)分別為，根據(jù)歐拉公式，得。又，而簡(jiǎn)單連通平面圖的每個(gè)面至少由3條邊圍成，所以在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中