1、大題一二三四五六七八九十總分得分得分成都理工大學2012-2013學年第二學期離散數學考試試卷一、填空題(本大題共10小題，每小題2分，共20分)1、設G為9階無向圖，每個結點度數不是5就是6,則G中至少有個5度結點。2、n階完全圖，Kn的點數X (Kn)二。3、 有向圖中從v1到v2長度為2的通路有條。4、設R, +,-是代數系統，如果R, +是交換群R,-是半群則稱R, +, 為環。5、設L，是代數系統，則L，滿足幕等律，即對V。G L有。 A上的關系R是自反的、對稱和傳遞的，稱R是A上的_等價關系。 群是一個存在二元運算可結合，存在單位元，每個元素存在逆元 的代數。若 h 是 A=S,米

2、到 A=S,米的同態，則h (a米b) =_h (a)米h (b)。R, +, 是環，則R, +是交換群，R,是_半群_。 一個無向圖的歐拉回路要求經過圖中每條邊一次且僅一次，哈密爾頓回路要求經過圖中每個頂點 一次且僅一次。巴分選擇題（本大題共10小題，每小題2分，共20分）1、下面四組數能構成無向簡單圖的度數列的有（）。A、(2,2,2,2,2)；B、(1,1, 2, 2, 3)；C、(1,1,2,2,2)；D、(0,1, 3, 3, 3)。2、下圖中是哈密頓圖的為（）。3、如果一個有向圖D是強連通圖，則D是歐拉圖，這個命題的真值為（）A、真；B、假。4、下列偏序集（）能構成格。s = 1,

3、1,2,1,3,1,45、設 234, *為普通乘法，則S，*是（）。A、代數系統；B、半群；C、群；D、都不是。6.設 A = 1,2,3,4, A 上的關系 R = （1,1）,（2,3）,（2,4）,（3,4）,則 R 具有（）。A-自反性；B.傳遞性；C.對稱性；D.以上都不是滿足謂詞P（x,y）： xy0的整數集Z上的二元關系具有（）性質？B、A-自反、對稱B.對稱、傳遞。.反對稱D .反自反、對稱、傳遞V=1, 2, 3, *, 1，x*y表示取x和y中較大數。下列不是V的 子代數的（）。A. 1, 2, 3, *, 1 B. 1, *, 1C. 2, 3, *, 1 D. 1,

4、3, *, 1A.2, 3；B . 2, 2, 2, 2；C10.3, 3, 3, 3； D . 1, 3, 3, 3。下列無向圖中，不是二部圖的是（D）。9.給定下列各序列，不能構成無向簡單圖的度數序列是（）。5Q得分一三、（本大題共40分）一1、（10%）在至少有2個人的人群中，至少有2個人，他們有相同的朋友數。2、（8%）若圖G中恰有兩個奇數度頂點，則這兩個頂點是連通的。3、（8%）證明在6個結點12條邊的連通平面簡單圖中，每個面的面數都是3。4、（10%）證明循環群的同態像必是循環群。5（12%）設B，x, +，_，1是布爾代數，定義運算*為a * b =（a x方）+ （。x b），

5、 求證B, *是阿貝爾群。得分四、（本大題共20分）_1、在二叉樹中1）求帶權為2, 3, 5, 7, 8的最優二叉樹T。（10分）2）求T對應的二元前綴碼。（10分）2、下圖所示帶權圖中最優投遞路線并求出投遞路線長度（郵局在D點）。302320答案:一、填空1、6； 2、n； 3、2； 4、+對分配且對+分配均成立；5、選擇題目12345答案A,BB,DBCD三、證明1、（10分）證明：用n個頂點，vn表示n個人，構成頂點集V=v，vn，設E = uvIu，V e K 且 u,v 是朋友（u 牛 v），無向圖 g=（V，e）現證G中至少有兩個結點度數相同。事實上，（1）若G中孤立點個數大于等

6、于2,結論成立。（2）若G中有一個孤立點，則G中的至少有3個頂點，既不考慮孤立點。設G中每個結 點度數均大于等于1，又因為G為簡單圖，所以每個頂點度數都小于等于n-1，由于G中n 頂點其度數取值只能是1，2,，n-1，由鴿巢原理，必然至少有兩個結點度數是相同的。2、（8分）證：設G中兩個奇數度結點分別為u，v。若u，v不連通則至少有兩個連通分支GG2,使得u，v分別屬于G1和G2。于是G1與G2中各含有一個奇數度結點，與握手定 理矛盾。因而u，v必連通。f=2-n+m=2-6-12=8Z deg（F） = 2 x m = 24由圖論基本定理知：而岫氣）Z 3，所以必有dW）=3，3 （8分）證

7、：n=6,m=12歐拉公式n-m+f=2知即每個面用3條邊圍成。4 （10分）證：設循環群A，的生成元為a同態映射為f，同態像為f （A），*，于是Pan,am e A都有 f (an -am) = f (an)* f (am)n=2,有 fg = f(a o) = f (q) * f(a) = (f (0)2若 n=k-l 時有 fg)=(f(g對 n=k 時，f (以)=f(以-1 . a) = f O-1) * f (o) =(o) =這表明，f(A)中每一個元素均可表示為(f0)n ,所以f(A),*為f(a)生成的循環群。5、證：交換律 寸。， 8 有1*力=(oxZ?) + (ix

8、Z?) = (Z?x3) + (Z? Xi) =Z?*o結合律：gb，cwB有(1 * Z?) * c = (g x 方)+(1 x /?) * c = (。xB) + (ax b) xc) + (a x 方)+ (1 x 人)x c =(a xb x c + a x b x c) + (a + b) x (a + b) x c= axbxc + axbxc + (axa + axb+bxa + bxb)xc=axbxc+axbxc+bxaxc + axbx c=axbxc + axb xc + axbxc + axb xc而：a * (Z? * c) = a * (Z? x c) + (方

9、x c)=(白 x (Z? x c) + (片 x c) + (a x(bxc) + (bx c) -ax(b+c)x(b + c)-haxbxc+axbxc= axbxc + axbxc+axbxc + axbx c(a*b)*c = a* (b*c)幺：有a0 = (ax0) +(ax0) = a + 0 = a 0*a = (0 x a) + (Ox a) = 0 + a = a。是8,*幺元。一、 、斗 /a e B a = (a xa) + (a xa) = 0 + 0 = Q理：。是。的逆元。綜上所述：田，*是阿貝爾群。四、計算1、（10 分）（1）（5分）由Huffman方法，得最佳二叉樹為:（2） （5 分）最佳前綴碼為：000, 001, 01, 10, 112