離散數(shù)學(xué)答案屈婉玲版第二版高等教育出版社課后答案

33、 ⑴ 項目 (1) (2) 極人兒： e a,b,d,e 極小元： a a,b,c,e 取大兀： e 最小元： a (2) 第八章部分課后習(xí)題參考答案 1.設(shè) f :N N,且 1,若以奇數(shù) f (x)= 三若x為偶數(shù) 2, 求 f (0), -1({3,5,7}). ({0})， f (1), f ({1}), f ({0,2,4,6,…}) , f ({4,6,8}),

34、 解：f (0)=0, f({0})={0}, f (1)=1, f({1})={1}, -1 ({3,5,7})={6,10,14}. f ({0,2,4,6, …}尸N, f ({4,6,8})={2,3,4}, f 4.判斷下列函數(shù)中哪些是滿射的？哪些是單射的？哪些是雙射的？ (1) f:N N, f(x)=x 2+2 不是滿射，不是單射 (2) f:N N,f(x)=(x)mod 3,x 除以 3 的余數(shù) 不是滿射，不是單射 ⑶f:N 1, N,f(x)= 0, 若x為奇數(shù) 若x為偶數(shù) 不是滿射，不是單射 ⑷f:N {0,1

35、},f(x)= 0,若x為奇數(shù) 1,若x為偶數(shù) 是滿射，不是單射 ⑸ f:N-{0} R,f(x)=lgx 不是滿射，是單射 (6) f:R R,f(x)=x 2-2x-15 不是滿射，不是單射 5.設(shè)*=國上6~}丫={1,2,3}力={<2,1>,<02>,<63>,} 判斷以下命題的真假 (1)f是從X到Y(jié)的二元關(guān)系，但不是從X到Y(jié)的函數(shù)； 對 (2)f是從X到Y(jié)的函數(shù)，但不是滿射，也不是單射的； 錯 (3)f是從X到Y(jié)的滿射，但不是單射； 錯 (4)f是從X到Y(jié)的雙射. 錯 第十章部分

36、課后習(xí)題參考答案 4 .判斷下列集合對所給的二元運算是否封閉： (1) 整數(shù)集合Z和普通的減法運算。 封閉，不滿足交換律和結(jié)合律，無零元和單位元 (2) 非零整數(shù)集合K和普通的除法運算。不封閉 (3) 全體n n實矩陣集合M (R)和矩陣加法及乘法運算，其中 生2。 封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律； 加法單位元是零矩陣，無零元； 乘法單位元是單位矩陣，零元是零矩陣； (4) 全體n n實可逆矩陣集合關(guān)于矩陣加法及乘法運算，其中 e2。不封閉 (5) 正實數(shù)集合艮一和二運算，其中"運算定義為： 爐工 b = R-, at-b = al — a — b 不

37、封閉 因為111111 1 R (6) n巨Z+hZ = {m|z e ZI遙關(guān)于普通的加法和乘法運算。 封閉，均滿足交換律，結(jié)合律，乘法對加法滿足分配律 加法單位元是0,無零元； 乘法無單位元(n 1),零元是0; n 1單位元是1 (7) A = { a1，a2， 冏} nN”運算定義如下： va, b E A, a= b = t 封閉 不滿足交換律，滿足結(jié)合律， (8) S =⑦-小"用關(guān)于普通的加法和乘法運算。 封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律 (9) S = {0,1},S 是關(guān)于普通的加法和乘法運算。 加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合

38、律 (10) S = ［工］”2小巨2+) ,S關(guān)于普通的加法和乘法運算。 加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律 5 .對于上題中封閉的二元運算判斷是否適合交換律，結(jié)合律，分配律。 見上題 7 .設(shè)*為Z上的二元運算 x, y Z , X * Y = min ( x , y ),即x和y之中較小的數(shù). (1)求4 * 6 , 7 * 3 。 4. 3 (2)*在Z上是否適合交換律，結(jié)合律，和幕等律？ 滿足交換律，結(jié)合律，和幕等律 (3)求*運算的單位元，零元及Z中所有可逆元素的逆元。 單位元無，零元1,所有元素?zé)o逆元 8. S Q Q Q為有理數(shù)集，*為$上的

39、二元運算，v,憶S有 < a , b >* = (1) *運算在S上是否可交換，可結(jié)合？是否為幕等的？ 不可交換：*= < a , b >* 可結(jié)合：(*)*=*= *(*)=*= (*)*=*(*<

40、c,d>) 不是幕等的 (2) *運算是否有單位元，零元？ 如果有請指出，并求S中所有可逆元素的逆元 設(shè) 是單位元，v s S , *= *= 貝U== ,解的 =<1,0> ,即為單位。 設(shè)<2口>是零元，爐 e S , *= *= 貝U== ,無解。即無零元。 v 七 S,設(shè)<2口>是它的逆元 *=

41、*=<1,0> ==<1,0> a=1/x,b=-y/x 所以當(dāng)x 0時, x, y (a)交換律，結(jié)合律，幕等律都滿足， 零元為a,沒有單位元； (b)滿足交換律和結(jié)合律，不滿足幕等律，單位元為 a,沒有零元 a 1 a, b 1 b (c)滿足交換律，不滿足幕等律，不滿足結(jié)合律 a (b b) a a b, (a b) b a b a a (b b) (a b) b 沒有單位元，沒有零元 (d)不滿足交換律，滿足結(jié)合律和幕等律 沒有單位元，沒有零元 (2)求每個運算的單位元，零元以及每一個可逆元素的逆

42、元。 見上 16.設(shè)V=〈 N, + , ?〉，其中+ , ?分別代表普通加法與乘法，對下面給定的每個集合 確定它是否構(gòu)成V的子代數(shù)，為什么？ (1) S1=(2n.| n Z!是 (2) S2=2n + i||nmZ! 不是 加法不封閉 (3) & = {-1 , 0, 1} 不是，加法不封閉 第十一章部分課后習(xí)題參考答案 8.設(shè)S={0, 1, 2, 3},⑨為模4乘法，即 "x,y C S, x y=(xy)mod 4 問〈S,悔〉是否構(gòu)成群？為什么？ 解：(1) x,y € S, x y=(xy)mod 4 S,a 是 S上的代數(shù)運算 (2) x,y,z CS,設(shè)

43、 xy=4k+r 0 r 3 (x v) z =((xy)mod 4) z=r 8 z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理 x--：(y|z) =(xyz)mod 4 所以，(x y) z = x因(y&z),結(jié)合律成立。 ⑶ x € S, (x g 1)=(1 0x)=x,,所以1是單位元。 ⑷1 1 1, 3 1 3, 0和2沒有逆元 所以，〈S」〉不構(gòu)成群 9.設(shè)Z為整數(shù)集合，在Z上定義二元運算。如下： " x,y 6 Z,xoy= x+y-2 問Z關(guān)于o運算能否構(gòu)成群？為什么？ 解：(1)

44、x,y € Z, xoy= x+y-2 Z ,o是Z上的代數(shù)運算。 (2) x,y,z € Z, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz),結(jié)合律成立。 ⑶設(shè)e是單位元， x C Z, xo e= eox=x，即 x+e-2= e+x-2=x, e=2 (4) x C Z ,設(shè) x 的逆元是 y, xoy= yox= e,即 x+y-2=y+x-2=2, 所以，x 1 y 4 x 所以〈Z, o＞構(gòu)成群 10 10 1 0 1 0 ,,, 一… … 11.設(shè)G= , , , ，證明G關(guān)于矩陣乘法構(gòu)成一

45、個群. 0 10 1 0 1 0 1 解：（1） x,y € G,易知xy C G,乘法是Z上的代數(shù)運算 (2)矩陣乘法滿足結(jié)合律 1 0 、，、 ⑶設(shè)1 0是單位元， 0 1 ⑷ 每個矩陣的逆元都是自己。 所以G關(guān)于矩陣乘法構(gòu)成一個群. 14 .設(shè)G為群，且存在aCG,使得 G={a k I k C Z} 證明：G是交換群。 證明：x,y C G,設(shè) x ak, y al ,則 xy akal ak l al k alak yx 所以，G是交換群 17 .設(shè)G為群，證明e為G中唯一的幕等元。 證明：設(shè)e0 G也是幕等元，則e2 a ,即e2 ee ,由消去律知e

46、 e 18 .設(shè)G為群，a,b,c CG,證明 I abc I = I bca I = I cab I 證明：先證設(shè)(abc)k e (bca)k e 設(shè)(abc)k e, 則(abc)(abc)(abc) (abc) e, 即 a(bca)(bca)(bca) (bca)a 1 e 左邊同乘a 1 ,右邊同乘a得 k 1 (bca)( bca)(bca) (bca) (bac) a ea e 反過來，設(shè)(bac)k e,則(abc)k e. 由元素階的定義知，I abc I = I bca I ,同理I bca I = I cab I 19 .證明：偶數(shù)階群G必含2階元

47、。 證明：設(shè)群G不含2階元，a G,當(dāng)a e時，a是一階元，當(dāng)a e時，a至少是3 階元,因為群G時有限階的，所以a是有限階的，設(shè)a是k階的，則a 1也是k階的，所以 高于3階的元成對出現(xiàn)的,G不含2階元，G含唯一的1階元e,這與群G是偶數(shù)階的矛 盾。所以，偶數(shù)階群G必含2階元 20 .設(shè)G為非Abel群，證明G中存在非單位元a和b,awb,且ab=ba. 證明：先證明G含至少含3階元。 若G只含1階元，則G={e},G為Abel群矛盾； 若G除了 1階元e外，其余元a均為2階元，則a2 e, a 1 a 1 1 1 1 1 1 a, b G, a a, b b, (ab) ab

48、,所以 ab a b (ba) ba, 與G為Abel群矛盾； 所以，G含至少含一個3階元，設(shè)為a,則a a2,且a2a aa2。 令b a2的證。 21 .設(shè)G是M(R)上的加法群，n>2,判斷下述子集是否構(gòu)成子群。 (1)全體對稱矩陣 是子群 (2)全體對角矩陣 是子群 (3)全體行列式大于等于0的矩陣.不是子群 (4)全體上(下)三角矩陣。 是子群 22 .設(shè)G為群，a是G中給定元素，a的正規(guī)化子N (a)表示G中與a可交換的元素構(gòu)成 的集合，即 N (a) ={x I x C GA xa=ax} 證明N (a)構(gòu)成G的子群。 證明：ea=ae, e N (a)

49、 x, y N (a), 貝1J ax xa, ay ya a(xy) (ax)y (xa)y x(ay) x(ya) (xy)a,所以 xy N(a) 由 ax xa ,得 x 1 axx 1 x 1 xax 1,x 1ae eax 1 ,即 x 1a ax 1 ,所以 x 1 N(a) 所以N (a)構(gòu)成G的子群 31.設(shè)1是群G到G的同態(tài)，2是G到G的同態(tài)，證明1 2是G到G的同態(tài)。 證明：有已知1是G到G的函數(shù)，2是G到G的函數(shù)，則1 - 2是G到G的函數(shù)。 a,b G1, ( 1 2)(ab) 2( 1(ab)) 2( 1(a) 1(b)) (2( 1(a)))( 2(

51、3’ 3 4 5 1 2 ⑴計算，，1, 1, 1 ； ⑵將，1, 1表成不交的輪換之積。 (3)將(2)中的置換表示成對換之積，并說明哪些為奇置換，哪些為偶置換 解：⑴ 1 1 2 3 4 5 2 15 3 4 1 2 3 4 5 4 3 12 5 1 2 3 4 5 5 4 13 2 1 2 3 4 5 4 5 12 3 (1425) 1 (14253) 1 (143)(25) (3) (14)(12)(15) 奇置換, (14)(12)(15)(13) 偶置換 (14)(13)(25)奇置換 第十四章部分課后習(xí)題參考答案 5、設(shè)無向圖G有10條邊，

52、3度與4度頂點各2個，其余頂點的度數(shù)均小于 3,問G至 少有多少個頂點？在最少頂點的情況下，寫出度數(shù)列、 (G)、(G)。 解：由握手定理圖G的度數(shù)之和為：2 10 20 3度與4度頂點各2個，這4個頂點的度數(shù)之和為14度。 其余頂點的度數(shù)共有6度。 其余頂點的度數(shù)均小于3,欲使G的頂點最少，其余頂點的度數(shù)應(yīng)都取 2, 所以，G至少有7個頂點，出度數(shù)列為3,3,4,4,2,2,2, (G) 4, (G) 2. 7、設(shè)有向圖D的度數(shù)列為2,3,2, 3,出度列為1,2,1,1,求D的入度列，并求(D), (D), (D), (D), (D), (D). 解：D的度數(shù)列為2, 3

53、, 2, 3,出度列為1, 2, 1, 1, D的入度列為1,1,1,2. (D) 3, (D) 2, (D) 2, (D) 1, (D) 2, (D) 1 8、設(shè)無向圖中有6條邊，3度與5度頂點各1個，其余頂點都是2度點，問該圖有多少 個頂點？ 解：由握手定理圖G的度數(shù)之和為：2 6 12 設(shè)2度點x個，則3 1 5 1 2x 12, x 2,該圖有4個頂點. 14、下面給出的兩個正整數(shù)數(shù)列中哪個是可圖化的？對可圖化的數(shù)列，試給出 3種非同 構(gòu)的無向圖，其中至少有兩個時簡單圖。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+

54、3+4+4+5=23 是奇數(shù)，不可圖化； ⑵2 +2+2+2+3+3+4+4=16,是偶數(shù)，可圖化； 18、設(shè)有3個4階4條邊的無向簡單圖G、G、G,證明它們至少有兩個是同構(gòu)的。 證明：4階4條邊的無向簡單圖的頂點的最大度數(shù)為 3,度數(shù)之和為8,因而度數(shù)列 為2, 2, 2, 2; 3, 2, 2, 1; 3, 3, 1, 1。但3, 3, 1, 1對應(yīng)的圖不是簡單圖。所以 從同構(gòu)的觀點看，4階4條邊的無向簡單圖只有兩個: 所以，G、G、G至少有兩個是同構(gòu)的。 20、已知n階無向簡單圖G有m條邊，試求G的補圖G的邊數(shù)m 解：m n(n」m 2 21、無向圖G

55、如下圖 (1)求G的全部點割集與邊割集，指出其中的割點和橋； (2)求G的點連通度k(G)與邊連通度(G)。 解：點割集：{a,b},(d) 邊割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} k(G)= (G)=1 28、設(shè)n階無向簡單圖為3-正則圖，且邊數(shù)m與n滿足2n-3=m問這樣的無向圖有幾種 非同構(gòu)的情況？ 解： 3n 2m 得 n=6,m=9. 2n 3 m 31、設(shè)圖G和它的部圖G的邊數(shù)分別為m和m,試確定G的階數(shù)。 解：m m n(n一1) 2 45、有向圖D

56、如圖 (1) 求V2到V5長度為1 1 1 8(m m) 得n 2 ,2, 3, 4的通路數(shù); ⑵求V5到V5長度為1, 2, 3, 4的回路數(shù); (3)求D中長度為4的通路數(shù)； (4)求D中長度小于或等于4的回路數(shù)； (5)寫出D的可達矩陣。 解：有向圖D的鄰接矩陣為: 0 0 2 0 1 , A2 0 0 0 10 10 0 10 10 0 0 0 0 2 0 1 0 1 0 A3 0 0 0 0 2 2 0 2 0 0 2 0 2 0 0 0 2 0 2 0 2 0 2 0 0 0 2 0 2 0 0 0 0 0 4

57、 0 0 0 0 4 4 0 4 0 0 4 A 0 0 0 0 4 4 0 4 0 0 0 4 0 4 0 2 n 3 AAA A4 0 12 15 5 2 5 2 2 2 12 15 4 2 5 2 2 2 5 2 5 4 (1) V2到V5長度為1, 2, 3, 4的通路數(shù)為0,2,0,0 ; (2) V5到V5長度為1, 2, 3, 4的回路數(shù)為0,0,4,0 ; ⑶D中長度為4的通路數(shù)為32; ⑷D中長度小于或等于4的回路數(shù)10; 11111 11111 ⑷出D的可達矩陣P 11111 11111 11111 第十六章部分課后

58、習(xí)題參考答案 1、畫出所有5階和7階非同構(gòu)的無向樹 2、一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是 3度頂點，問T有幾個頂點？ 解：設(shè)3度分支點x個，則 5 1 3 2 3x 2 (5 3 x 1),解得 x 3 T有11個頂點 3、無向樹T有8個樹葉，2個3度分支點，其余的分支點都是 4度頂點，問T有幾個4度分支 點？根據(jù)T的度數(shù)列，請至少畫出 4棵非同構(gòu)的無向樹。 解：設(shè)4度分支點x個，則 2 3 4x 2 (8 2 x 1),解得 x 2 度數(shù)列 1111

59、11113344 4、棵無向樹T有Q(i=2 , 3,…，k)個i度分支點，其余頂點都是樹葉，問 T應(yīng)該有幾片樹 葉？ 解：設(shè)樹葉x片，則 ni i x 1 2 (ni x 1),解得 x (i 2)ni 2 評論：2, 3, 4題都是用了兩個結(jié)論，一是握手定理，二是 m n 1 5、n(n>3)階無向樹T的最大度A(T)至少為幾？最多為幾？ 解：2, n-1 6、若n(n>3)階無向樹T的最大度=2,問T中最長的路徑長度為幾？ 解：n-1 7、證明：n(n > 2)階無向樹不是歐拉圖. 證明：無向樹沒有回路，因而不是歐拉圖。 8、證明：n(n > 2)階無向樹不是

60、哈密頓圖. 證明：無向樹沒有回路，因而不是哈密頓圖。 9、證明：任何無向樹 T都是二部圖. 證明：無向樹沒有回路，因而不存在技術(shù)長度的圈，是二部圖。 10、什么樣的無向樹 T既是歐拉圖，又是哈密頓圖 ？ 解：一階無向樹 14、設(shè)e為無向連通圖G中的一條邊，e在G的任何生成樹中，問e應(yīng)有什么性質(zhì)？ 解：e是橋 15、設(shè)e為無向連通圖G中的一條邊，e不在G的任何生成樹中， 問e應(yīng)有什么性質(zhì)？ 解：e是環(huán) 23、已知n階m條的無向圖G是k(k >2)棵樹組成的森林，證明：m = n-k.； 證明：數(shù)學(xué)歸納法。k=1時，m = n-1 ,結(jié)論成立； 設(shè)k=t-1(t-1 1)時，

61、結(jié)論成立，當(dāng)k=t時，無向圖G是t棵樹組成的森林，任取兩棵樹，每棵 樹任取一個頂點，這兩個頂點連線。則所得新圖有 t-1棵樹，所以m = n- (k-1). 所以原圖中m = n-k 得證。 24、在圖16.6所示2圖中，實邊所示的生成子圖 T是該圖的生成樹. (1)指出T的弦，及每條弦對應(yīng)的基本回路和對應(yīng) T的基本回路系統(tǒng) (2)指出T的所有樹枝， 及每條樹枝對應(yīng)的基本割集和對應(yīng) T的基本割集系統(tǒng) (a) (b) 圖 16.16 解：(a)T 的弦：c,d,g,h T 的基本回路系統(tǒng):S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,

62、g}} T的所有樹枝：e,a,b,f T 的基本割集系統(tǒng):S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}} (b)有關(guān)問題仿照給出 25、求圖16.17所示帶權(quán)圖中的最小生成樹 . 圖 16.17 (a) (b) 解： 注：答案不唯一。 37、畫一棵權(quán)為3, 4, 5, 6, 7, 8, 9的最優(yōu)2叉樹，并計算出它的權(quán) 38.下面給出的各符號串集合哪些是前綴碼 ？ A1={0 , 10, 110, 1111} 是前綴碼 A2={1 , 01, 001, 000} 是前綴碼 A3=

63、{1 , 11, 101, 001, 0011} 不是前綴碼 A4={b , c, aa, ac, aba, abb, abc} 是前綴碼 A5={ b , c, a, aa, ac, abc, abb, aba} 不是前綴碼 41.設(shè)7個字母在通信中出現(xiàn)的頻率如下 ： a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5% .并指出傳輸 用Huffman算法求傳輸它們的前綴碼.要求畫出最優(yōu)樹，指出每個字母對應(yīng)的編碼 10n(n >2)個按上述頻率出現(xiàn)的字母，需要多少個二進制數(shù)字 ^ 解： a:01 b:10 c:000 d:110 e:001 f:1111 g:1110 W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255 傳輸10n(n >2)個按上述頻率出現(xiàn)的字母，需要 255*10 n-2個二進制數(shù)字