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

33、 ⑴ 項(xiàng)目 (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(wàn):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è)*=國(guó)上6~}丫={1,2,3}力={<2,1>,<02>,<63>,} 判斷以下命題的真假 (1)f是從X到Y(jié)的二元關(guān)系，但不是從X到Y(jié)的函數(shù)； 對(duì) (2)f是從X到Y(jié)的函數(shù)，但不是滿射，也不是單射的； 錯(cuò) (3)f是從X到Y(jié)的滿射，但不是單射； 錯(cuò) (4)f是從X到Y(jié)的雙射. 錯(cuò) 第十章部分

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

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

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

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

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

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

42、元。 見(jiàn)上 16.設(shè)V=〈 N, + , ?〉，其中+ , ?分別代表普通加法與乘法，對(duì)下面給定的每個(gè)集合 確定它是否構(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 問(wèn)〈S,悔〉是否構(gòu)成群？為什么？ 解：(1) x,y € S, x y=(xy)mod 4 S,a 是 S上的代數(shù)運(yùn)算 (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沒(méi)有逆元 所以，〈S」〉不構(gòu)成群 9.設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算。如下： " x,y 6 Z,xoy= x+y-2 問(wèn)Z關(guān)于o運(yùn)算能否構(gòu)成群？為什么？ 解：(1)

44、x,y € Z, xoy= x+y-2 Z ,o是Z上的代數(shù)運(yùn)算。 (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、個(gè)群. 0 10 1 0 1 0 1 解：（1） x,y € G,易知xy C G,乘法是Z上的代數(shù)運(yùn)算 (2)矩陣乘法滿足結(jié)合律 1 0 、，、 ⑶設(shè)1 0是單位元， 0 1 ⑷ 每個(gè)矩陣的逆元都是自己。 所以G關(guān)于矩陣乘法構(gòu)成一個(gè)群. 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 反過(guò)來(lái)，設(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時(shí)，a是一階元，當(dāng)a e時(shí)，a至少是3 階元,因?yàn)槿篏時(shí)有限階的，所以a是有限階的，設(shè)a是k階的，則a 1也是k階的，所以 高于3階的元成對(duì)出現(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含至少含一個(gè)3階元，設(shè)為a,則a a2,且a2a aa2。 令b a2的證。 21 .設(shè)G是M(R)上的加法群，n>2,判斷下述子集是否構(gòu)成子群。 (1)全體對(duì)稱(chēng)矩陣 是子群 (2)全體對(duì)角矩陣 是子群 (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 ⑴計(jì)算，，1, 1, 1 ； ⑵將，1, 1表成不交的輪換之積。 (3)將(2)中的置換表示成對(duì)換之積，并說(shuō)明哪些為奇置換，哪些為偶置換 解：⑴ 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è)無(wú)向圖G有10條邊，

52、3度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)的度數(shù)均小于 3,問(wèn)G至 少有多少個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫(xiě)出度數(shù)列、 (G)、(G)。 解：由握手定理圖G的度數(shù)之和為：2 10 20 3度與4度頂點(diǎn)各2個(gè)，這4個(gè)頂點(diǎn)的度數(shù)之和為14度。 其余頂點(diǎn)的度數(shù)共有6度。 其余頂點(diǎn)的度數(shù)均小于3,欲使G的頂點(diǎn)最少，其余頂點(diǎn)的度數(shù)應(yīng)都取 2, 所以，G至少有7個(gè)頂點(diǎn)，出度數(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è)無(wú)向圖中有6條邊，3度與5度頂點(diǎn)各1個(gè)，其余頂點(diǎn)都是2度點(diǎn)，問(wèn)該圖有多少 個(gè)頂點(diǎn)？ 解：由握手定理圖G的度數(shù)之和為：2 6 12 設(shè)2度點(diǎn)x個(gè)，則3 1 5 1 2x 12, x 2,該圖有4個(gè)頂點(diǎn). 14、下面給出的兩個(gè)正整數(shù)數(shù)列中哪個(gè)是可圖化的？對(duì)可圖化的數(shù)列，試給出 3種非同 構(gòu)的無(wú)向圖，其中至少有兩個(gè)時(shí)簡(jiǎn)單圖。 (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個(gè)4階4條邊的無(wú)向簡(jiǎn)單圖G、G、G,證明它們至少有兩個(gè)是同構(gòu)的。 證明：4階4條邊的無(wú)向簡(jiǎn)單圖的頂點(diǎn)的最大度數(shù)為 3,度數(shù)之和為8,因而度數(shù)列 為2, 2, 2, 2; 3, 2, 2, 1; 3, 3, 1, 1。但3, 3, 1, 1對(duì)應(yīng)的圖不是簡(jiǎn)單圖。所以 從同構(gòu)的觀點(diǎn)看，4階4條邊的無(wú)向簡(jiǎn)單圖只有兩個(gè): 所以，G、G、G至少有兩個(gè)是同構(gòu)的。 20、已知n階無(wú)向簡(jiǎn)單圖G有m條邊，試求G的補(bǔ)圖G的邊數(shù)m 解：m n(n」m 2 21、無(wú)向圖G

55、如下圖 (1)求G的全部點(diǎn)割集與邊割集，指出其中的割點(diǎn)和橋； (2)求G的點(diǎn)連通度k(G)與邊連通度(G)。 解：點(diǎn)割集：{a,b},(d) 邊割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} k(G)= (G)=1 28、設(shè)n階無(wú)向簡(jiǎn)單圖為3-正則圖，且邊數(shù)m與n滿足2n-3=m問(wèn)這樣的無(wú)向圖有幾種 非同構(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長(zhǎng)度為1 1 1 8(m m) 得n 2 ,2, 3, 4的通路數(shù); ⑵求V5到V5長(zhǎng)度為1, 2, 3, 4的回路數(shù); (3)求D中長(zhǎng)度為4的通路數(shù)； (4)求D中長(zhǎng)度小于或等于4的回路數(shù)； (5)寫(xiě)出D的可達(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長(zhǎng)度為1, 2, 3, 4的通路數(shù)為0,2,0,0 ; (2) V5到V5長(zhǎng)度為1, 2, 3, 4的回路數(shù)為0,0,4,0 ; ⑶D中長(zhǎng)度為4的通路數(shù)為32; ⑷D中長(zhǎng)度小于或等于4的回路數(shù)10; 11111 11111 ⑷出D的可達(dá)矩陣P 11111 11111 11111 第十六章部分課后

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

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

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

61、結(jié)論成立，當(dāng)k=t時(shí)，無(wú)向圖G是t棵樹(shù)組成的森林，任取兩棵樹(shù)，每棵 樹(shù)任取一個(gè)頂點(diǎn)，這兩個(gè)頂點(diǎn)連線。則所得新圖有 t-1棵樹(shù)，所以m = n- (k-1). 所以原圖中m = n-k 得證。 24、在圖16.6所示2圖中，實(shí)邊所示的生成子圖 T是該圖的生成樹(shù). (1)指出T的弦，及每條弦對(duì)應(yīng)的基本回路和對(duì)應(yīng) T的基本回路系統(tǒng) (2)指出T的所有樹(shù)枝， 及每條樹(shù)枝對(duì)應(yīng)的基本割集和對(duì)應(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的所有樹(shù)枝：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)問(wèn)題仿照給出 25、求圖16.17所示帶權(quán)圖中的最小生成樹(shù) . 圖 16.17 (a) (b) 解： 注：答案不唯一。 37、畫(huà)一棵權(quán)為3, 4, 5, 6, 7, 8, 9的最優(yōu)2叉樹(shù)，并計(jì)算出它的權(quán) 38.下面給出的各符號(hào)串集合哪些是前綴碼 ？ 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個(gè)字母在通信中出現(xiàn)的頻率如下 ： a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5% .并指出傳輸 用Huffman算法求傳輸它們的前綴碼.要求畫(huà)出最優(yōu)樹(shù)，指出每個(gè)字母對(duì)應(yīng)的編碼 10n(n >2)個(gè)按上述頻率出現(xiàn)的字母，需要多少個(gè)二進(jì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)個(gè)按上述頻率出現(xiàn)的字母，需要 255*10 n-2個(gè)二進(jìn)制數(shù)字