1、第七章部分課后習題參考答案7.列出集合A=2,3,4上的恒等關系I A,全域關系EA,小于或等于關系LA,整除關系DA.解：IA =<2，2>,<3,3>,<4,4> EA=<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>LA=<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>DA=<2,4>

2、13.設A=<1,2>,<2,4>,<3,3> B=<1,3>,<2,4>,<4,2>求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB ), fld(A-B).解：AB=<1,2>,<2,4>,<3,3>,<1,3>,<4,2> AB=<2,4>domA=1,2,3 domB=1,2,4 dom(AB)=1,2,3,4ranA=2,3,4 ranB=2,3,4ran(AB)=4A-B=<1,2>

3、,<3,3>，fld(A-B)=1,2,314.設R=<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>求RR, R-1, R0,1, R1,2解：RR=<0,2>,<0,3>,<1,3> R-1,=<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>R0,1=<0,1>,<0,2>,<0,3>,<1,2>,<1,3

4、>R1,2=ran(R|1,2)=2,316設A=a,b,c,d，為A上的關系，其中=求。解: R1R2=<a,d>,<a,c>,<a,d> R2R1=<c,d>R12=R1R1=<a,a>,<a,b>,<a,d>R22=R2R2=<b,b>,<c,c>,<c,d>R23=R2R22=<b,c>,<c,b>,<b,d>36設A=1，2，3，4，在AA上定義二元關系R， <u,v>,<x,y>AA ，u,v>

5、; R <x,y>u + y = x + v.(1) 證明R 是AA上的等價關系.(2)確定由R 引起的對AA的劃分.（1）證明：<u,v>R<x,y> u+y=x-y<u,v>R<x,y>u-v=x-y<u,v>AAu-v=u-v<u,v>R<u,v>R是自反的任意的<u,v>,<x,y>A×A如果<u,v>R<x,y> ，那么u-v=x-yx-y=u-v <x,y>R<u,v> R是對稱的任意的<u,v>

6、;,<x,y>,<a,b>A×A若<u,v>R<x,y>,<x,y>R<a,b>則u-v=x-y,x-y=a-bu-v=a-b <u,v>R<a,b>R是傳遞的R是A×A上的等價關系(2) =<1,1>,<2,2>,<3,3>,<4,4>, <2,1>,<3,2>,<4,3>, <3,1>,<4,2>,<4,1>, <1,2>,<2,3>

7、,<3,4>, <1,3>,<2,4>, <1,4> 41.設A=1，2，3，4，R為AA上的二元關系, a，b，c，d AA , a，bRc，da + b = c + d(1) 證明R為等價關系.(2) 求R導出的劃分.(1)證明：<a，b AA a+b=a+b<a,b>R<a,b> R是自反的任意的<a,b>,<c,d>A×A設<a,b>R<c,d>，則a+b=c+dc+d=a+b <c,d>R<a,b>R是對稱的任意的<a,

8、b>,<c,d>,<x,y>A×A若<a,b>R<c,d>,<c,d>R<x,y>則a+b=c+d,c+d=x+ya+b=x+y <a,b>R<x,y>R是傳遞的R是 A×A上的等價關系(2)=<1,1>, <1,2>,<2,1>, <1,3>,<2,2>,<3,1>, <1,4>,<4,1>,<2,3>,<3,2>, <2,4>,<4,

9、2>,<3,3>, <3,4>,<4,3>, <4,4>43. 對于下列集合與整除關系畫出哈斯圖:(1) 1,2,3,4,6,8,12,24(2) 1,2,3,4,5,6,7,8,9,10,11,12解: (1) (2)45.下圖是兩個偏序集<A,R>的哈斯圖.分別寫出集合A和偏序關系R的集合表達式. (a) (b)解: (a)A=a,b,c,d,e,f,g R=<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,

10、<b,e>,<c,f>,<c,g> (b) A=a,b,c,d,e,f,gR=<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>46.分別畫出下列各偏序集<A,R>的哈斯圖,并找出A的極大元極小元最大元和最小元.(1)A=a,b,c,d,eR=<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>IA.(2)A=a,b,c

11、,d,e, R=<c,d>IA.解: (1) (2)項目 (1) (2)極大元: e a,b,d,e 極小元: a a,b,c,e最大元: e 無最小元: a 無第八章部分課后習題參考答案1 設f :NN,且 f (x)=求f (0), f (0), f (1), f (1), f (0,2,4,6,)，f (4,6,8), f -1(3,5,7).解：f (0)=0, f (0)=0, f (1)=1, f (1)=1, f (0,2,4,6,)=N，f (4,6,8)=2,3,4, f -1 (3,5,7)=6,10,14.4. 判斷下列函數中哪些是滿射的?哪些是單射的?哪些是

12、雙射的? (1) f:NN, f(x)=x2+2 不是滿射，不是單射 (2) f:NN,f(x)=(x)mod 3,x除以3的余數 不是滿射，不是單射 (3) f:NN,f(x)= 不是滿射，不是單射 (4) f:N0,1,f(x)= 是滿射，不是單射 (5) f:N-0R,f(x)=lgx 不是滿射，是單射 (6) f:RR,f(x)=x2-2x-15 不是滿射，不是單射5. 設X=a,b,c,d,Y=1,2,3,f=<a,1>,<b,2>,<c,3>,判斷以下命題的真假: (1)f是從X到Y的二元關系,但不是從X到Y的函數; 對 (2)f是從X到Y的函數

13、,但不是滿射,也不是單射的; 錯 (3)f是從X到Y的滿射,但不是單射; 錯 (4)f是從X到Y的雙射. 錯第十章部分課后習題參考答案4判斷下列集合對所給的二元運算是否封閉：（1） 整數集合Z和普通的減法運算。封閉,不滿足交換律和結合律，無零元和單位元（2） 非零整數集合普通的除法運算。不封閉（3） 全體實矩陣集合（R）和矩陣加法及乘法運算，其中n2。封閉 均滿足交換律，結合律，乘法對加法滿足分配律；加法單位元是零矩陣，無零元；乘法單位元是單位矩陣，零元是零矩陣；（4）全體實可逆矩陣集合關于矩陣加法及乘法運算，其中n2。不封閉（5）正實數集合和運算，其中運算定義為： 不封閉 因為 （6）關于普

14、通的加法和乘法運算。封閉，均滿足交換律，結合律，乘法對加法滿足分配律加法單位元是0，無零元；乘法無單位元（），零元是0；單位元是1（7）A = n運算定義如下： 封閉 不滿足交換律，滿足結合律，（8）S = 關于普通的加法和乘法運算。封閉 均滿足交換律，結合律，乘法對加法滿足分配律（9）S = 0,1,S是關于普通的加法和乘法運算。 加法不封閉，乘法封閉；乘法滿足交換律，結合律（10）S = ,S關于普通的加法和乘法運算。加法不封閉，乘法封閉，乘法滿足交換律，結合律5對于上題中封閉的二元運算判斷是否適合交換律，結合律，分配律。 見上題7設 * 為上的二元運算，X * Y = min ( x，y

15、 ),即x和y之中較小的數.(1) 求4 * 6，7 * 3。 4, 3(2)* 在上是否適合交換律，結合律，和冪等律？滿足交換律，結合律，和冪等律(3)求*運算的單位元，零元及中所有可逆元素的逆元。單位元無，零元1, 所有元素無逆元8 為有理數集，*為S上的二元運算，<a,b>,<x,y >S有 < a，b >*<x，y> = <ax，ay + b>（1）*運算在S上是否可交換，可結合？是否為冪等的？不可交換：<x,y>*<a,b >= <xa，xb +y>< a，b >*<x，

16、y>可結合：(<a,b >*<x,y>)*<c,d>=<ax，ay + b>*<c,d>=<axc，axd +(ay+b) ><a,b >*(<x,y>*<c,d>)=<a, b>*<xc,xd+y>=<axc，a(xd +y)+b >(<a,b >*<x,y>)*<c,d>=<a,b >*(<x,y>*<c,d>)不是冪等的（2）*運算是否有單位元，零元？ 如果有請指出，并

17、求S中所有可逆元素的逆元。 設<a,b>是單位元，<x,y >S ，<a,b >*<x,y>= <x,y>*<a,b >=<x,y> 則<ax,ay+b>=<xa,xb+y>=<x,y>，解的<a,b>=<1,0>，即為單位。設<a,b>是零元，<x,y >S ，<a,b >*<x,y>= <x,y>*<a,b >=<a,b> 則<ax,ay+b>=<

18、xa,xb+y>=<a,b>，無解。即無零元。<x,y >S，設<a,b>是它的逆元<a,b >*<x,y>= <x,y>*<a,b >=<1,0><ax,ay+b>=<xa,xb+y>=<1,0>a=1/x,b=-y/x所以當x0時，10令S=a，b，S上有四個運算：*，分別有表10.8確定。 (a) (b) (c) (d)(1)這4個運算中哪些運算滿足交換律，結合律，冪等律？(a) 交換律，結合律，冪等律都滿足， 零元為a,沒有單位元；(b)滿足交換律和

19、結合律，不滿足冪等律，單位元為a,沒有零元 (c)滿足交換律,不滿足冪等律,不滿足結合律 沒有單位元, 沒有零元(d) 不滿足交換律，滿足結合律和冪等律 沒有單位元, 沒有零元(2) 求每個運算的單位元，零元以及每一個可逆元素的逆元。見上16設V= N，+ ，其中+ ，分別代表普通加法與乘法，對下面給定的每個集合確定它是否構成V的子代數，為什么？（1）S1= 是（2）S2= 不是 加法不封閉（3）S3 = -1，0，1 不是，加法不封閉第十一章部分課后習題參考答案8.設S=0，1，2，3，為模4乘法，即 "x,yS, xy=(xy)mod 4 問S，是否構成群？為什么？解：(1) x

20、,yS, xy=(xy)mod 4,是S上的代數運算。(2) x,y,zS,設xy=4k+r (xy)z =(xy)mod 4)z=rz=(rz)mod 4=(4kz+rz)mod 4=(4k+r)z)mod 4 =(xyz)mod 4同理x(yz) =(xyz)mod 4所以，(xy)z = x(yz)，結合律成立。(3) xS, (x1)=(1x)=x,，所以1是單位元。(4) 0和2沒有逆元所以，S，不構成群9.設Z為整數集合，在Z上定義二元運算。如下： " x,yZ,xoy= x+y-2 問Z關于o運算能否構成群？為什么？解：(1) x,yZ, xoy= x+y-2,o是Z上

21、的代數運算。(2) x,y,zZ, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz= xo(yoz)，結合律成立。(3)設是單位元，xZ, xo= ox=x,即x+-2= +x-2=x, e=2(4) xZ , 設x的逆元是y, xoy= yox=, 即x+y-2=y+x-2=2, 所以，所以Z，o構成群11.設G=，證明G關于矩陣乘法構成一個群解：(1) x,yG, 易知xyG,乘法是Z上的代數運算。(2) 矩陣乘法滿足結合律(3)設是單位元，(4)每個矩陣的逆元都是自己。所以G關于矩陣乘法構成一個群14.設G為群，且存在aG,使得 G=ak

22、kZ證明：G是交換群。證明:x,yG，設，則所以，G是交換群17.設G為群，證明e為G中唯一的冪等元。證明:設也是冪等元，則，即，由消去律知18.設G為群，a,b,cG,證明 abc=bca=cab證明：先證設設則，即左邊同乘，右邊同乘得反過來，設則由元素階的定義知，abc=bca，同理bca=cab19.證明：偶數階群G必含2階元。證明：設群G不含2階元，當時，是一階元，當時，至少是3階元,因為群G時有限階的，所以是有限階的，設是k階的,則也是k階的，所以高于3階的元成對出現的，G不含2階元，G含唯一的1階元,這與群G是偶數階的矛盾。所以，偶數階群G必含2階元20.設G為非Abel群，證明G

23、中存在非單位元a和b,ab,且ab=ba.證明：先證明G含至少含3階元。若G只含1階元,則G=e,G為Abel群矛盾；若G除了1階元e外,其余元均為2階元，則，與G為Abel群矛盾；所以，G含至少含一個3階元，設為，則，且。令的證。21.設G是Mn(R)上的加法群，n2，判斷下述子集是否構成子群。（1）全體對稱矩陣 是子群（2）全體對角矩陣 是子群（3）全體行列式大于等于0的矩陣. 不是子群（4）全體上（下）三角矩陣。 是子群22.設G為群，a是G中給定元素，a的正規化子N（a）表示G中與a可交換的元素構成的集合，即 N（a）=xxGxa=ax證明N（a）構成G的子群。證明：ea=ae, ,所

24、以由，得，即，所以所以N（a）構成G的子群31.設1是群G1到G2的同態，2是G2到G3的同態，證明12是G1到G3的同態。證明：有已知1是G1到G2的函數，2是G2到G3的函數，則1·2是G1到G3的函數。 所以:1·2是G1到G3的同態。33.證明循環群一定是阿貝爾群，說明阿貝爾群是否一定為循環群，并證明你的結論。 證明：設G是循環群,令G=<a>,令,那么,G是阿貝爾群 克萊因四元群,是交換群,但不是循環群,因為e是一階元，a,b,c是二階元。36.設是5元置換，且，(1)計算；(2)將表成不交的輪換之積。(3)將（2）中的置換表示成對換之積，并說明哪些為

25、奇置換，哪些為偶置換。解：(1) (2) (3) 奇置換， 偶置換 奇置換第十四章部分課后習題參考答案5、設無向圖G有10條邊，3度與4度頂點各2個，其余頂點的度數均小于3，問G至少有多少個頂點？在最少頂點的情況下，寫出度數列、。解：由握手定理圖G的度數之和為：3度與4度頂點各2個，這4個頂點的度數之和為14度。其余頂點的度數共有6度。其余頂點的度數均小于3，欲使G的頂點最少，其余頂點的度數應都取2,所以，G至少有7個頂點, 出度數列為3,3,4,4,2,2,2,.7、設有向圖D的度數列為2，3，2，3，出度列為1，2，1，1，求D的入度列，并求，,.解：D的度數列為2，3，2，3，出度列為1

26、，2，1，1，D的入度列為1,1,1,2.,8、設無向圖中有6條邊，3度與5度頂點各1個，其余頂點都是2度點，問該圖有多少個頂點？解：由握手定理圖G的度數之和為：設2度點個，則，該圖有4個頂點.14、下面給出的兩個正整數數列中哪個是可圖化的？對可圖化的數列，試給出3種非同構的無向圖，其中至少有兩個時簡單圖。(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4解：(1) 2+2+3+3+4+4+5=23 是奇數，不可圖化；(2) 22+2+2+3+3+4+4=16, 是偶數，可圖化；18、設有3個4階4條邊的無向簡單圖G1、G2、G3，證明它們至少有兩個是同構的。證明：4階

27、4條邊的無向簡單圖的頂點的最大度數為3，度數之和為8，因而度數列為2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1對應的圖不是簡單圖。所以從同構的觀點看，4階4條邊的無向簡單圖只有兩個：所以，G1、G2、G3至少有兩個是同構的。20、已知n階無向簡單圖G有m條邊，試求G的補圖的邊數。解：21、無向圖G如下圖(1)求G的全部點割集與邊割集，指出其中的割點和橋；(2) 求G的點連通度與邊連通度。解：點割集: a,b,(d)邊割集e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5=123、求G的點連通度、邊連通度與最小度數。解：、 、28、設n階無向簡單圖為3

28、-正則圖，且邊數m與n滿足2n-3=m問這樣的無向圖有幾種非同構的情況？解： 得n=6,m=9.31、設圖G和它的部圖的邊數分別為和，試確定G的階數。解： 得45、有向圖D如圖 (1)求到長度為1，2，3，4的通路數；(2)求到長度為1，2，3，4的回路數；(3)求D中長度為4的通路數；(4)求D中長度小于或等于4的回路數；(5)寫出D的可達矩陣。解：有向圖D的鄰接矩陣為：， (1)到長度為1，2，3，4的通路數為0,2,0,0；(2)到長度為1，2，3，4的回路數為0,0,4,0；(3)D中長度為4的通路數為32；(4)D中長度小于或等于4的回路數10；(4)出D的可達矩陣第十六章部分課后習

29、題參考答案1、畫出所有5階和7階非同構的無向樹.2、一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是3度頂點，問T有幾個頂點?解：設3度分支點個，則 ，解得T有11個頂點3、無向樹T有8個樹葉，2個3度分支點，其余的分支點都是4度頂點，問T有幾個4度分支點？根據T的度數列，請至少畫出4棵非同構的無向樹。解：設4度分支點個，則 ，解得度數列1111111133444、棵無向樹T有 (i=2，3，k)個i度分支點，其余頂點都是樹葉，問T應該有幾片樹葉?解：設樹葉片，則 ，解得評論：2，3，4題都是用了兩個結論,一是握手定理，二是5、n(n3)階無向樹T的最大度至少為幾？最多為幾？解：2，n-16、若n(n3)階無向樹T的最大度 =2，問T中最長的路徑長度為幾？解：n-17、證明：n(n2) 階無向樹不是歐拉圖.證明：無向樹沒有回路，因而不是歐拉圖。8、證明：n(n2) 階無向樹不是哈密頓圖.證明：無向樹沒有回路，因而不是哈密頓圖。9、證明：任何無向樹T都是二部圖.證明：無向樹沒有回路，因而不存在技術長度的圈，是二部圖。10、什么樣的無向樹T既是歐拉圖，又是哈密頓圖?解：一階無向樹14、設e為無向連通圖G中的一條邊， e在G的任何