1、第六章代數(shù)系統(tǒng)6.1第129頁1.證實：任取x,yI,g(y,x)y*xyxyxxyxyg(x,y),因此,二元運(yùn)算*是可交換的；任取x,y,zI,g(x,g(y,z)x*(y*z)x*(yzyz)xyzyzx(yzyz)xyzxyxzyzxyzg(g(x,y),z)(x*y)*z(xyxy)*zxyxyz(xyxy)zxyzxyxzyzxyzg(x,g(y,z)因此,運(yùn)算*是可結(jié)合的.該運(yùn)算的么元是0,0的逆元是0,2的逆元是2,其余元素沒有逆元.2.證實：任取x,yN,xy,由x*yx,y*xyx知,y*xx*y,*運(yùn)算不是可交換的.任取x,y,zN,由(x*y)*zx*zx,x*(y*z

2、)x*yx知,(x*y)*zx*(y*z),*運(yùn)算是可結(jié)合的.任取xN,x*xx,可知N中的所有元素都是等哥的.*運(yùn)算有右么元,任取x,yN,x*yx,知n中的所有元素都是右么元.*運(yùn)算沒有左么元.證實：采用反證法.假定e為*運(yùn)算的左么元,WbN,be,由*的運(yùn)算公式知e*be,由么元的性質(zhì)知,e*bb,得eb,這與be相矛盾,因此,*運(yùn)算沒有左么元.3 .解：任取x,yI,xyx*yx和y的最小公倍數(shù)y*xy和x的最小公倍數(shù)x和y的最小公倍數(shù)因此對于任意的x,yI,xy都有x*yy*x,即二元運(yùn)算*是可交換的.任取x,y,z|,(x*y)*z(x和y的最小公倍數(shù))*zx,y,z的最小公倍數(shù)x

3、*(y*z)x*(y和z的最小公倍數(shù))x,y,z的最小公倍數(shù)因此對于任意的X,y,z,都有(x*y)*zx*(y*z),即二元運(yùn)算*是可結(jié)合的.設(shè)幺元為ex*ee*x/口e的最小公倍數(shù)x,那么e1,即幺元為1.對于所有的元素xI,都有x*xx,所以所有元素都是等哥的.4 .解：設(shè)Xn設(shè)f是X上的二元運(yùn)算,那么f是一個從X2X的映射.求X上有多少個二元運(yùn)算即相當(dāng)于求這樣的映射的個數(shù).22由于X2n2,映射f的個數(shù)為nn,即X上有nn個二元運(yùn)算.可交換即fx,yfy,x設(shè)集合X1,2,3,4),要求X上可交換的二元運(yùn)算的個數(shù),即相當(dāng)于求映射f的個數(shù),f:AX,其中：A1,2,1,31,42,32,

4、43,4,1,12,23,34,4具體如以下圖所示:1,2,2,11,3,3,21,4,4,12,3,3,212,4,4,223,4,4,331,142,2X3,34,4A此時映射f的個數(shù)N44644c44一C2n推廣到x有n個元素時,映射f的個數(shù)Nnn單位元素即幺元,假設(shè)存在必唯一.設(shè)集合X1,2,34,假設(shè)幺元為1,那么有1,111,2,2,121,3,3,131,4,4,14此時的二元運(yùn)算的個數(shù)相當(dāng)于求映射f:AX的個數(shù),其中:A2,23,34,4X2,313,222,434,243,44,32.,9,41)2映射f:AX的個數(shù)為N4491(41)2幺元為2,3,4時同理,N444c44

5、2個有單位元素的二元運(yùn)算.推廣到X有n個元素時,具有單位元素的二元運(yùn)算的個數(shù)為,22NnCnn(n1).5.解：任取ai,a2,a3a1*a2a1a2a2*a1a2aia1a2a1*a2對于任意的a1,a2R都有a2*ai&*a?,故二元運(yùn)算*是可交換的.*aa1a2a3a1a2aia2ai*a3)ai*(a2a3)aia2a3假設(shè)ai1,a2302ai*a2*a36,a1*(a2*a3)0,此時ai*a2*a3a1*(a2*a3)故二元運(yùn)算*是不可結(jié)合的.不存在這樣e使得任意的xR都有x*e因此,二元運(yùn)算*不含幺元.a2*ai對于任意的aia2ai,a2a2/2ai/2aiR者B有a

6、2*a1a2/2a1*a2a*a2,故二元運(yùn)算*是可交換的.*aa1a2a3a1a2/2aia222ai*(a2*a3)a1*a2a3/2a2a3ai二22aa2a3a1a22a3故二元運(yùn)算*是不可結(jié)合的.不存在這樣e使得任意的xR都有x*e(xe)/2x,因此集合X1,2,34上有N4449C44(4i)因此,二元運(yùn)算*不含幺元.a1*a2a1/a2a2*a1a2/a1a1*a2因此,二元運(yùn)算*是不可交換的.a1*a2*a3a1/a2*a3a1/a2a3aia2a3ai*(a2*a3)aj)aia2/a3陋a2aia2a3故二元運(yùn)算*是不可結(jié)合的.R都有由于二元運(yùn)算*不是可交換的,所以不存在

7、這樣e使得任意的xx*ee*xx/ex,因此,二元運(yùn)算*不含幺元.6.設(shè)x是X中的任意元素.由于二元運(yùn)算*是可結(jié)合的,故x*x*xx*x*x又對于任意的x,yX,假設(shè)x*yy*x,那么yx故x*xx即對于X中的任意元素,都有x*xx,所以X中的每一個元素都是等哥的.6.2第137頁4 .證實：首先,U和V都只含有一個二元運(yùn)算,因此是同類型的；第二,f的定義域是自然數(shù)集合N,值域是0,1,是V定義域的子集.第三,驗證是否運(yùn)算的像等于像的運(yùn)算.任取x,yN,分情況討論：ix和y都可以表示成2k,設(shè)x2k1,y2k2,那么f(xgy)f(2k1乎k2)f(2k1k2)1,f(x)f(y)1f(x)g

8、f(y)1gi1f(xgy)(2)x和y都不能表示成2k,那么xgy也不能表示成2kf(xgy)0,f(x)f(y)0f(x)gf(y)0g00f(xgy)(3) x可以表示成2k,y不能表示成2k,那么xgy也不能表示成2kf(xgy)0,f(x)1,f(y)0f(x)gf(y)1g30f(xgy)(4)x不可以表示成2k,y能表示成2k,那么xgy也不能表示成2kf(xgy)0,f(x)0,f(y)1f(x)gf(y)0gl0f(xgy)可知,無論x和y如何取值,都能夠保證f(x)gf(y)f(xgy).綜上所述,f是u到v的同態(tài)映射.5 .證實：設(shè)Ua,b,c,V1,2,3,首先,U和V

9、都僅有一個二元運(yùn)算,因此U和V是同類型的；第二,U和V的定義域大小相同,具備構(gòu)成雙射函數(shù)的條件；第三,尋找特異元素,U中么元是a,右零元是c,三個元素都是等哥元；V中么元是3,右零元是1,三個元素都是等哥元.第四,在u和V的定義域之間構(gòu)造雙射函數(shù)f,使得f(a)3,f(b)2,f(c)1.把*運(yùn)算表中的元素都用f下的像點代替,得321332122211121調(diào)整表頭的順序為1,2,3,轉(zhuǎn)變?yōu)橄卤?23112121223123跟V中運(yùn)算表完全相同,因此代數(shù)系統(tǒng)a,b,c,和1,2,3,是同構(gòu)的.6 .證實：(1)兩個代數(shù)系統(tǒng)都只存在一個二元運(yùn)算,故滿足同型.(2)構(gòu)造函數(shù)f,使得儂)=2&quo

10、t;,顯然f是雙射函數(shù).(3)對于任意的X,Y(X)On¥)=-(XnY)=-Xu-Y故f(XcY)=fOOuf(Y),所以滿足運(yùn)算的像=像的運(yùn)算.由(1),(2),(3)可知,兩代數(shù)系統(tǒng)是同構(gòu)的.7 .解：fp(X)(px)mod6,p0,1,2,3,4,5當(dāng)p0時,f0零同態(tài);當(dāng)p1時,f1恒等映射,自同態(tài);p2時,f20,0p3時,f30,0p4時,f40,0p5時,f5(0,01,2,2,4,3,01,3,2,0,3,31,4,2,2,3,01,5,2,4,3,34,2,5,4；4,0,5,3；4,4,5,2；4,2,5,1自同構(gòu).8 .證實：xn10的n個復(fù)數(shù)根可表示成：,

11、.,.2,xkcoskisinkii,ki0,1,2,.nin(1) En,?與Nn,n都含有一個二元運(yùn)算,故為同型的.(2) En,?與Nn,n定義域大小相同,具備構(gòu)成雙射函數(shù)的條件.f(xk)kimodn(3)構(gòu)造雙射函數(shù)kii對于任意的xki,Xk2En,f(xk1?xk2)f(cosk1sink1i)?(cosk2sink2i)2、f(cosk1cosk2cosk1sink2isink1cosk2isink1sink2i)f(cosk1cosk2cosk1sink2isink1cosk2isink1sink2)f(cos(k1k2)sin(k1k2)i)(k1k2)(modn)f(Xk

12、1)nf(Xk2)K(modn)nk2(modn)(k1(modn)k2(modn)(modn)(k1k2)(modn)因此,f(Xk1?Xk2)f(Xk1)nf(Xk2).由(1),(2),(3)可知,En,?同構(gòu)于Nn,n.9.證實：g是代數(shù)系統(tǒng)X,*到當(dāng)y,?的同態(tài)映射gXy又Xi,*是X,*的子代數(shù)X1XgX1y(2)對于a,bgX,必存在Xa,XbX1,使得gXaa,gXbb,a?bgXa?gXb由于g為代數(shù)系統(tǒng)X,*到當(dāng)Y,?的同態(tài)映射gXa?gXbgXa*XbXa,XbXi,又Xi,*是X,*的子代數(shù)故X1X*運(yùn)算封閉Xa*XbXigXa*XbgXi,即a?bgXigXi對？運(yùn)算

13、滿足封閉性.由,(2),(3)可知,gXi,?為Y,?的子代數(shù).6.3第i4i頁i.解：mx,mam,yamb)m,解：首先,判斷m是否是等價關(guān)系.任取xI,由于xx0m,因此x是自反的；任取x,yI,假設(shè)xmy,即xyam(aI),那么yxymx,因此m是對稱的；任取x,y,zI,假設(shè)xmy,ymZ,那么X(aI),yzbm(bI),于是xz(xy)(yz)(aabI,因此xmz,可知m是可傳遞的.因此,m是等價關(guān)系.其次,判斷m關(guān)于*是否滿足代換性質(zhì).任取x,yI,假設(shè)xmy,即存在某個pI,滿足xypm* (x)xk(modm)* (y)yk(modm)那么* (x)(ypm)k(mod

14、m)C；ykCkyki(pm)iC；yk2(pm)2LCfy0(pm)kykPm(C：ykiC；yk2(pm)iLC【y0(pm)ki)于是*(x)*(y)pm(C1yk1C2yk2(pm)1LCky0(pm)k1)P(Ckyk1C；yk2(pm)1LC：y0(pm)k1)m由于p(Ckyk1C：yk2(pm)1LCky0(pm)k1)I,因此*(x)m*(y),m關(guān)于*是滿足代換性質(zhì).綜上所述,m是U上的同余關(guān)系.2 .解：(1)對于+運(yùn)算,在二元運(yùn)算下,任取X1,X2,y1,y21,驗證下式是否成立印必x2Ry2X1X2RWy2取X11,X22,y11,y22,可知滿足X1R%,x2Ry2

15、,但|X1X211yly2|,即x1x2Ky1y2.可知對于運(yùn)算+,R不滿足代換性質(zhì).(2)對于運(yùn)算,在二元運(yùn)算下,任取X1,X2,y1,y21,假設(shè)X1Ry,x2Ry2,那么必然滿足|x1|必|,|x?|y?|于是|XX21|x11|X21|必|y21|yy21可得x1x2Ry1y2.由x1,X2,y1,y2取值的任意性可知,對于運(yùn)算,R滿足代換性質(zhì).3 .證實：對于為？2,%.2,有x1Ry1,X2Ry2由于R對3具有代換性質(zhì),所以有(X1x1)R(y1%)由此可知：(X13x13-3X1)R(Y1X2個Xi同理可知：(X23X23.3X2)R(y2yi個X2因R是等價關(guān)系,故是可傳遞的,

16、所以有所以R對3具有代換性質(zhì).(2)S0,0,1,1,2,2,1,2但對3不具有代換性質(zhì),因2,23y133y1)X13X2Ry13X2個y13y23.3y2)y13X2Ry1y2個y1X13X2Ry13y2211對3具有代換性質(zhì),31,20,1SX23y24 .設(shè)代數(shù)系統(tǒng)VG,R,R為同余關(guān)系.(1)即證：R1R2為同余關(guān)系證實：RR2為等價關(guān)系假設(shè)w對任意a,",a2,b2,a%,bnwG有a3R2)b1,a2(R1R2)b2,anw(R1R2)bn那么aRQ,azRB,anwR1bnwaiR2b1,a?R2b2,anwR2bnwRR2為同余關(guān)系w(a1,a2,anw)Rw(匕笛

17、2,b0w)w(a1,a2,.anw)R?w(bb,bnw)w(四®,anw)R1R2w(b1,b2,bnw)所以R1R2為同余關(guān)系.(2)RR2為等價關(guān)系假設(shè)w對任意ai,bi,a2,b2,.anw,bnwG有ai(RiR2)bi,a2(RiR2A,%(R1R2)bnw未必有aiRbi,azRbz,anwR1bnw#2>,a2R2b2,%wR2bnw因此,可能不滿足代換性質(zhì)所以RiR2未必是同余關(guān)系.5.(1) xRy,當(dāng)且僅當(dāng)(x0y0)(x0y0)解：r不是I,上的同余關(guān)系,取xi0,yi3,x2i,y22,那么XiRyiRy2,但是Xix2i0,0y2i0,因此xix2

18、Xyiy2,不滿足代換性質(zhì).(2) xRy,當(dāng)且僅當(dāng)xyi0解：R不是I,上的同余關(guān)系,取x0,y9,zi5,那么xRy,yRz,但|xz|i5i0,xXz,R不滿足可傳遞性,不是等價關(guān)系.(3) xRy,當(dāng)且僅當(dāng)(xy0)(x0y0)解：r不是I,上的同余關(guān)系,取取xi3,yi2,x23,y22,那么為Ry,x2Ry2,但是xx20,yV240,因此xixzKyiy2,不滿足代換性質(zhì).(4) xRy,當(dāng)且僅當(dāng)xy解：r不是I,上的同余關(guān)系,取x9,y8,那么xRy,但y/x,即y火x,R不滿足對稱性,不是等價關(guān)系.6.4第i43頁i.解:(i)設(shè)f2F3N2N3,e其中,n2N3(0,0,0

19、,i,0,2,i,0,i,i,i,2任取ai,n,azbN2N3ai,biazbai2a2,b13b2ai,biea2bai2a2,bi3b2卜面通過運(yùn)算表構(gòu)造*運(yùn)算(這里僅給出了一個運(yùn)算表,另一個照推)<0,0><0,i><0,2><i,0><i,i><0,0><0,0><0,0><0,0><i,0><i,0><0,i><0,0><0,i><0,2><i,0><i,i><0,2>

20、<0,0><0,2><0,i><i,0><i,2><i,0><i,0><i,0><i,0><0,0><0,0><i,i><i,0><i,i><i,2><0,0><0,i><i,2><i,0><i,2><i,i><0,0><0,2>設(shè)f3F2N3N2,',e'其中,N3N2(0,0,0,i,i,0,i,i,2

21、,0,2,i任取ai,b,a2bN3N2ai,bia2,b2ai2a2,bi3b2ai,biea2bai2a2,bi3b2運(yùn)算表的構(gòu)造方法與上同.2.(1)證實：任取Xi,yiX2,y2XY,xi,yix2,y2xi?x2,yi*y2和*可交換<i,2><i,0><i,2><i,i><0,0><0,2><0,i>xqX2,y2X2,y2Xi,yiXi?X2,yi*y2X2?Xi,y2*%是可交換的.(2)任取Xi,yi,X2,y2,X3,y3Xi,yiX2,y2X3,y3?和*可結(jié)合Xi,yiX2,y2X3,y

22、3Xi,yiX2?X3,y2*y3Xi,yi(X2,y2X3,y3是可結(jié)合的.XYXi?X2?X3,yi*y2*y3Xi?X2?X3,yi*(y2*y3)3.m0i234500i2345ii23450223450i33450i24450i23550i234<0,0><0,i><0,2><i,0><i,i><i,2><0,0><0,0><0,0><0,0><i,0><i,0><i,0><0,i><0,0><0,i

23、><0,2><i,0><i,i><i,2><0,2><0,0><0,2><0,i><i,0><i,2><i,i><i,0><i,0><i,0><i,0><0,0><0,0><0,0><i,i><i,0><i,i><i,2><0,0><0,i><0,2><i,2><i,0>

24、;<i,2><i,i><0,0><0,2><0,i>證實：A2A3與A6都只有一個二元運(yùn)算,故為同型的.A2A3與A6定義域大小相同,具備構(gòu)成雙射函數(shù)的條件.構(gòu)造雙射函數(shù)f(0.0)0,f(0,1)1,f(0,2)2,f(1,0)3,f(1,1)4,f(1,2)5由上圖可知,像的運(yùn)算=運(yùn)算的像所以A2A3與A6是同構(gòu)的.6.5第155頁1.(1)半群(2)半群(3)半群(4)獨異點,么元0(5)不是半群,取a=b=1,c=2,那么(a3b)3c1a3(b3c)2不滿足結(jié)合律(6)不是半群,由于|不是二元運(yùn)算；(7)半群(8)獨異點,么

25、元0(9)半群(10)獨異點,么元為恒等關(guān)系；(11)獨異點,么元為a2.(1)二元運(yùn)算表如以下圖所示:(2)XX,o,其中X1,2,3.(假定XX為叢X到X的雙射函數(shù))解：X到X有6個雙射函數(shù),分別用R,p2,L,P6表示,設(shè)X:abcP1:abcp2:acbp3:bacp4:bcap5:cabp6:cba構(gòu)造運(yùn)算表o如下：opip2p3p4p5p6pipip2p3p4p5p6p2p2pip5p6p3p4p3p3p4pip2p6p5p4p4p3p6p5pip2p5p5p6p2pip4p3p6p6p5p4p3p2pi第七章圖論6.1第164頁1.畫出圖GV,E,的圖示,指出其中哪些圖是簡單圖.

26、(1)&V2e3e2q4eeeV3不是簡單圖.V3一泰.68yzee10e.vSe60Ne7Qe4VVev14e3不是簡單圖.(3)eiV1V2V6e3e2e4e9e1e5'eV3注V4V7e0V8e7,e5V52.寫出圖7-8的抽象數(shù)學(xué)定義.(1)解：GV,E,其中V1,2,3,a,2,4,b,1,2,c,1,1,是簡單圖.4,Ea,b,c,d,e,f,d,1,3,e,3,2,f,4,2解：GV,E,其中V1,2,3,4,5,6,7,8,9,Ea,b,c,d,e,f,g,h,i,j,k,l,a,1,3,b,1,3,c,1,2,d,2,3,e,3,4,f,2,4,g,2,5,h

27、,6,7,i,7,9,j,7,8,k,8,9,l,9,93 .證實：在n階簡單有向圖中,完全有向圖的邊數(shù)最多,其邊數(shù)為n(n1).證實：簡單有向圖是沒有自環(huán),沒有平行邊的有向圖,只要兩個不同的結(jié)點之間才能有邊.完全有向圖是每個結(jié)點的出度和入度都是n-1的簡單有向圖,也就是每個結(jié)點都有到其他所有結(jié)點的邊,因此,完全有向圖的邊數(shù)最多.在完全有向圖中,所有結(jié)點的出度之和為n(n-1),所有結(jié)點的入度之和為n(n-1),設(shè)邊的個數(shù)為m,由握手定理可知,2m=n(n-1)+n(n-1),即m=n(n-1),得證.4 .證實：3度正那么圖必有偶數(shù)個結(jié)點.證實：設(shè)三度正那么圖的結(jié)點個數(shù)為n,那么所有結(jié)點的度

28、數(shù)之和為3n,由握手定理可知,邊的個數(shù)為3n/2=1.5n,由于邊的個數(shù)一定是整數(shù),因此,n為偶數(shù).得證.5 .在一次集會中,相互熟悉的人會彼此握手,試證實：與奇數(shù)個人握手的人數(shù)是偶數(shù)個.證實：設(shè)集會上的人一共有m個,可分為兩局部,一局部為與奇數(shù)個人握手的人,設(shè)為x個,另一局部為與偶數(shù)個人握手的人,為m-x個.由于握手是相互的,即一次握手,兩個人握手的次數(shù)都加1,一共加2,因此,集會上所有人的握手次數(shù)之和為偶數(shù).與偶數(shù)個人握手的人,這些人的握手次數(shù)之和為a1a2Lamx(其中,a1,a2,L,amx都是偶數(shù)),為偶數(shù).與奇數(shù)個人握手的人,這些人的握手次數(shù)之和為b1b2Lbx(其中,b,b2,L

29、,bx為基數(shù)),由于所有人的握手次數(shù)之和偶數(shù),因此b1b2Lbx也要為偶數(shù),即(b1b2Lbx)mod20又由于(Db2Lbx)mod2hmod2b2mod2Lbxmod2xmod2即xmod20,因此x為偶數(shù),即與奇數(shù)個人握手的人是偶數(shù)個,得證.6 .證實：圖7-7中的兩個圖同構(gòu).證實：首先,給這兩幅圖標(biāo)上對應(yīng)的結(jié)點編號,如下兩個圖的結(jié)點和邊的數(shù)目都相同.假設(shè)函數(shù)1,1',5,2',3,3',4,4',5,2',6,6',左圖中相鄰的結(jié)點是1和4,1和5,1和6,2和4,2和5,2和6,3和4,3和5,3和6,對應(yīng)的像點1'和4'

30、;,T和2',T和6',5'和4',5'和2',5'和6',3'和5',3'和2',3'和6'在右圖中也相鄰,因此,兩圖同構(gòu).7 .證實：在任意六個人中,假設(shè)沒有三個人彼此熟悉,那么必有三個人彼此都不熟悉.證實：分三種情況：(1)任何一個人最多熟悉另外一個人將相互熟悉的兩個人分成一組,那么至少可以分3組,每組取一個人,那么這三個必不熟悉.(2)任何一個人最多熟悉另外兩個人最糟糕的情況是當(dāng)每個人都熟悉另外兩個人時,假設(shè)熟悉的人之間畫一條線可以構(gòu)成一個六邊形,取不相鄰的三個點即是不熟悉的

31、.(3)任何一個人最多熟悉另外的三個人不妨設(shè)點A與B,C,E熟悉(用實線連接).由于B,C,E之間只有有兩個人熟悉就不滿足任何三個人都不熟悉的條件,比方B,C熟悉畫一條實線,那么A,B,C就相互熟悉,與矛盾.所以B,C,E是所求的三個互補(bǔ)熟悉的人.(4)任何一個人最多熟悉兩外4或5個人該情況與(3)類似,所求的人即與A熟悉的兩外4或5個人中的三個人.證畢.8 .證實：圖7-9的兩個圖不同構(gòu).證實：給這兩幅圖標(biāo)上對應(yīng)的結(jié)點編號,如下：55'6'67'788'10343'4'a)b)2,2'(1,2,3,4)a1,2,3b1ee,12,33,

32、415,6,7,8e5a,6,7e7,7,8b2e5722(5,66,77,82除這兩(1,5,7,3)a3e4aadbbcc3,41,4同構(gòu)e4,1,4)8,9同構(gòu).,3,1在b)e,1,2e5,5,6e8,8,9)8,8'中對應(yīng)的同構(gòu)圖.因此(1,2,3,4)G2e55,6,7,8)1,1e10e9e4e7e7e,1,20,7,33,3',4,4'5,5',6,6',7,7'9.圖7-10的兩個圖是否同構(gòu)？說明理由G1V1,E1E2,2.),27,1,5,e8,5,7121'2'e1e1a)b)7.2第168頁1.畫出K4的所

33、有不同的子圖,并說明其中哪些是生成子圖,找出互為補(bǔ)圖的生成子圖.解：-其中,1和7,2和6,3和5,4中的后兩個圖可以構(gòu)成互補(bǔ)的生產(chǎn)子圖.GV是完全有向圖解：對于圖b中的點d,其出度為：dGd3,入度：dGd0.而在a圖中不存在這樣的結(jié)點.因此這兩個圖不同構(gòu).nk(k1)n2m.證實：由題意,結(jié)點數(shù)為n,由總邊數(shù)建立關(guān)系:2.設(shè)GV,E,是完全有向圖.證實：對于V的任意非空子集V,10.證實：任何階大于1的簡單無向圖必有兩個結(jié)點的度數(shù)相等.證實：考慮一個有n個結(jié)點的連通圖如果有一個孤立結(jié)點,去掉孤立結(jié)點考慮聯(lián)通子圖.由于是無向連通圖,每個結(jié)點的最大度數(shù)是n-1,最小度數(shù)是1.即對n個點賦值,共

34、n-1種取值,由抽屜原理,必有兩個結(jié)點的取值相同,即必有兩個點的度數(shù)相同.11.設(shè)n階無向圖G有m條邊,其中nk個結(jié)點的度數(shù)為k,其余結(jié)點的度數(shù)為k+1,證實:2nk(k1)nnkk(nri)(k1),m-,由此可得:2m.(5)(6)(2)證實：1當(dāng)V中只有一個結(jié)點時,GV是完全有向圖(2)當(dāng)V中有多于一個結(jié)點時,對其中任意兩個結(jié)點Vi,Vj是V的子集,即Vi,VjV.由于圖G是完全有向圖,因此Vi,Vj間存在兩條有向邊5和e/.GV是由非空子集V生成的子圖,故00GV,即GV中任意兩個結(jié)點間存在兩條有向邊,故GV是完全有向圖.3 .畫出圖7-15的兩個圖的交、并和環(huán)和.解:并:環(huán)和:esV

35、3V44 .設(shè)G是任意6階簡單無向圖,證實：G或G必有一個子圖是3階無向圖.證實：取G或G任意取三個點,取與這三個點相關(guān)聯(lián)的變構(gòu)成一個3階的無向子圖.5 .我們稱與補(bǔ)圖同構(gòu)的簡單無向圖為自補(bǔ)圖.證實：每個自補(bǔ)圖的階能夠被4整除或被4整除余數(shù)為1.證實：設(shè)圖的頂點數(shù)為n,Kn的邊數(shù)為此口,由自補(bǔ)圖的定義知該2圖與其子圖的邊數(shù)相同同構(gòu),故其邊數(shù)為嵬3,由該數(shù)是整數(shù)4得：皿*n4korn4k1.故每個自補(bǔ)圖的階能夠被4整除或4被4整除余數(shù)為1.7.3第173頁1.考慮圖7-211從A至F的路徑有多少條？找出所有長度小于6的從A至F的路徑.解：A到F的路徑有無數(shù)條.長度小于6的有24條.cfh:4,c

36、gh:4,cei:4,bdefh:2,bdegh:2,bdi:4(2)找出從A至F的所有簡單路徑.解：12條.(cfh,cgh,ceI,bdefh,bdegh,bdi),還有一個自環(huán),需乘以2.(3)找出從A至F的所有根本路徑.解：6條.(cfh,cgh,ceI,bdefh,bdegh,bdi)(4)求出從A至F的距離.求出該圖的直徑.解：距離為3.直徑為3.(5)找出該圖的所有回路.解：AaA,AbDdEeBcA,BeEiFhCgB;BgCfB;AbDdEiFhCgBcA;BeEiFhCfB;2 .證實：圖7-21中根本路徑必為簡單路徑.證實：根本路徑要求途經(jīng)的頂點不重復(fù),簡單路徑要求途經(jīng)的

37、邊不重復(fù).在圖7-21中,對于所有的根本路徑,邊不重復(fù)出現(xiàn).所以根本路徑必是簡單路徑.3 .考慮圖7-22(1)對于每個結(jié)點v,求R(v).解：R(Vi)R(V2)R(V3)R(V4)Vi2,V3,V4,V5,V6,R(V5)V5,V6,R(V6)V6,RM)V6,VyR(V8)V6,V7,V8,R(V9)V9,R(%0)V10(2)找出所有強(qiáng)分支、單向分支和弱分支.解：強(qiáng)分支7個,分別是v9,V10,V8,v7,v6,V5,v1,v2,v3,v4單項分支4個,分別是V9,V10,v6,v7,V8,V1,v2,v3,v4,V5,v6弱分支3個,分別是V9,v10,V1,v2,v3,v4,v5,

38、v6,v7,v84.設(shè)ViV2V3是任意無向圖有向圖G的三個任意結(jié)點,以下三個公式是否成立？如果成立,給出證實；如果不成立,舉出反例.（1） dVi,V20,并且等號成立,當(dāng)且僅當(dāng)ViV2.解：成立.當(dāng)ViV2時,距離必定大于1.（2） dV1,V2dv2,V1解：成立.由于無向圖是無方向的.5,證實：有向圖的每個結(jié)點和每條邊恰處于一個弱分支中.反證法：假設(shè)任意結(jié)點V處于兩個或兩個以上的弱分支中,不妨設(shè)兩個弱分支為G1,G2,那么G1,G2是G的極大聯(lián)通子圖.設(shè)VG1,VG2,又G,g2G,故G1,G2聯(lián)通.這與G1,G2是極大聯(lián)通子圖矛盾,故命題得證.6.有向圖的每個結(jié)點每條邊是否恰處于一個

39、強(qiáng)分支中？是否恰處于一個單向分支中？解：有向圖中的每個結(jié)點處于一個強(qiáng)分支中,而邊不一定.有向圖的結(jié)點和邊可能出現(xiàn)在兩個單向分支中.圖見書上P141圖7-187,證實同階的回路必同構(gòu).證實：同階說明兩個圖的頂點個數(shù)相同,設(shè)為V;又聯(lián)通二度正那么圖稱為回路.即兩個圖的每個頂點的度數(shù)相同為2,邊數(shù)為2V/2=V,相同.由于兩個圖的頂點數(shù),邊數(shù)相同,且每個頂點的度數(shù)均為2,故兩個圖同構(gòu).9,設(shè)G是弱聯(lián)通有向圖,如果對于G的任意結(jié)點v,dGv1,那么G恰有一條有向回路.試給出證實證實：由于G是弱聯(lián)通有向圖,不妨設(shè)一條極大單向聯(lián)通子圖：0-*OMV2Vk1Vk由于：dGv1,所以對Vk,eVk,V.假設(shè)V

40、ViVki,那么與極大聯(lián)通子圖矛盾,故V必為ViVki之一.又假設(shè)有兩條以上的回路反證法,不妨設(shè)有兩條,那么這兩條回路上所有點的出度為1,而要使這兩條回路聯(lián)通,那么至少其中有一個點的出度大于1,這與dGv1矛盾.故G恰有一條會向回路.10 .設(shè)G為n階簡單無向圖,對G的任意結(jié)點v,dGvn1/2,證明G是聯(lián)通的.證實:任取Vi,Vj,由于dGvn1/2,故至少存在工個點與M相連,最2多還剩余n2工J1U除去V,Vj剩余的點.故對于Vj222至少存在一個與Vi連接的點與Vj相連,因此Vi與Vj聯(lián)通.由Vi與Vj選取的任意性,G聯(lián)通.11 .證實：對于小于或等于n的任意正整數(shù)k,n階連通無向圖有k

41、階連通子圖.證實：n階連通無向圖,那么n個頂點中的任意點與其他頂點均可達(dá)取其中的k個頂點也滿足該性質(zhì),故存在k階連通子圖.7.4第181頁1.解：根據(jù)圖7-26得鄰接矩陣為:Vi至UV4:長度為1的根本路徑為：ViV4長度為2的根本路徑為:V1v2V4長度為4的根本路徑為:v1v2V3V2V400A00100110101110A20102010011013,A311110000211221202242,A203040301212233322.解：(1)對于n=1,2,-,6,試計算矩陣a1n中的各兀素.0011103112114255720000111201112222531001002102

42、1203522522A1,A2,A13101010211311525472110101112141752745010010110112232252A6(2)17991613998499794109144169917139139141324997499812373771221217373504473774977446677102441227377123121731217710212116877734944737750382233395122221618223317.5331818332618A3922333851225133265144332217182233160001100201110000

43、00011020000000010001010100A11010100,A10031001001000101120001000000000011010000000000112014300704660000000220400000100310040324004032400,A24602116003014200604670002000000000022020000000000221206171300000004460211600_5_6A21306171200040000004000003001731290008000001701114170031014453100290

44、1731300000000440000044(3)試求出圖中G1和G2中的所有根本循環(huán)對于A和A2,a：表示結(jié)點m(i1,2,.7)上長度為k的循環(huán)的個數(shù).3,對于圖7-26中的有向圖,試求出鄰接矩陣A的轉(zhuǎn)置At,AAt,AtA,列出矩陣AAT的元素值,并說明它們的意義.解：AT表示有向圖逆圖的鄰接矩陣,即原圖中如果有第i個結(jié)點到第j個結(jié)點長度為1的路徑,那么AT中第j行第i列為1;第i個結(jié)點和第j個結(jié)點引出的邊,可以同時終止于某些結(jié)點,這些結(jié)點的個數(shù)為aat中第i行第j列的元素值.從某些結(jié)點引出的邊,可以同時終止于第i個結(jié)點和第j個結(jié)點,這些結(jié)點的個數(shù)為ata中第i行第j列的元素值.AAT中

45、第i行第j列對應(yīng)元素為1表示從第i個結(jié)點和第j個結(jié)點引出的邊,可以同時終止于某些結(jié)點；為0表示第i個結(jié)點和第j個結(jié)點引出的邊,不可以同時終止于某個結(jié)點.4.對于nxn的布爾矩陣A,試證實：(IA)(IA)(IA)IAA其中I是nxn的單位矩陣,并且有AAA.再證實：對于任何正整數(shù)nI,都有(IA)IAA2A證實：(1)(IA)(IA)o(IA),假設(shè)該矩陣中的a.1,那么存在Vk使得編1且a：j1,即(IA)(IA),故(IA)(IA)(IA).又IAA,AIA(由于I相當(dāng)于每個頂點到自己的邊,不改變該頂點到其他頂點的邊),因此有：(IA)(IA)I2(IA)(AI)A2=IAA2,故問題一得

46、證.(2)用數(shù)學(xué)歸納法證實：當(dāng)n=2時成立假設(shè)當(dāng)n=k是成立,那么有：(Ia嚴(yán)IAAA(k)當(dāng)n=k+1時,(IA)(k1(IA)(k)o(lA)(IAAA(k)o(IA)(IAAA(k)(IA)(IAAA(k)I)(IAAA(k)A)(IAA(2)A(k)(IAA(2)A(k)A)(IAAA(k)(AAA(k)A(k1)IAA(2)A(k)A(k1)故命題成立.5.給定簡單有向圖GV,E,并且有V|n.設(shè)A是G的鄰接矩陣試證實：根據(jù)第1題中所得到的結(jié)果能夠把路徑矩陣表示成P(IA).證實：對于有向圖的路徑矩陣：PAA(2)A,而對于第一題有：aAA(n)IAAA(n),故有：PIAAA(n)

47、,由第4題得到：(IA)(n)IAA2A,故有：P(IA)(n),得證.6.圖7-27給出一個簡單有向圖.試求出該圖的鄰接矩陣A,并求出其路徑矩陣PA.解:0100000010A10000,00001010000000A2010100010001000,0000100001A3000000001000010,0100010100A4000001000010001,001000PAAAAA(4)0000A(5)010100A(5)010001000,0000100101101011=1101101011010117.使給出圖7-25中的有向圖的距離矩陣.dij1意味著什么?解：012101D21

48、0,dj1表示有一條M到Vj的邊.01108 .試求出第2題中的圖G1和G2的距離矩陣.解:021112203211130123Di12101211210121321002110112012D2110112101021209 .如何才能從一個距離矩陣中求得一個路徑矩陣呢?證實：對于任意結(jié)點Vi和Vj(ij),由題意aij0,因此從Vi到Vj必定存在一條長度不為0的路徑,由結(jié)點選取的任意性得：任何兩個結(jié)點均是聯(lián)通的.故G的強(qiáng)聯(lián)通的有向圖.從距離矩陣求路徑矩陣：將距離矩陣中不為0的值變?yōu)?,即可得到10 .試確定圖7-25所示的圖是否是強(qiáng)分支解：對圖7-25由距離矩陣求得的路徑矩陣為:011001

49、010011000,由路徑矩陣知該圖不是強(qiáng)分支0000111 5第184頁1.解：a),b),c)是歐拉圖,d),e),f)不是歐拉圖.2.如果Gi和G2是可運(yùn)算的歐拉有向圖,那么GiG2仍是歐拉有向圖.這句話對嗎？如果對,給出證實,如果不對,舉出反例.證實：不對,不能保證連通.4.設(shè)G是平凡的連通無向圖,證實：G是歐拉圖,當(dāng)且僅當(dāng)G是假設(shè)干個邊不相交的回路的并.證實：充分性,當(dāng)進(jìn)行假設(shè)干個不相交的回路的并運(yùn)算后,每個結(jié)點都是偶結(jié)點,因此G是歐拉圖.必要性,對于G是歐拉圖,那么G必定有歐拉閉路.如果某個結(jié)點的度數(shù)大于2,可以對結(jié)點的環(huán)路進(jìn)行分解,分解為多個小的環(huán)路的并.7.6第186頁1 .圖7-34是不是二部圖？如果是,找出其互補(bǔ)結(jié)點子集.解：是,互補(bǔ)結(jié)點子集是：v1,v3,v5,v2,v4,v6,v7.2 .如何由無向圖G的鄰接矩陣判斷G是不是二部圖？解：設(shè)G的鄰接矩陣為A,Vn,計算A,A,人.其中如果矩陣的對角線出現(xiàn)了基數(shù),那么G不是二部圖.如果所有的矩陣包括矩陣A的回路長度都是偶數(shù),那么是二部圖.3 .舉出一個二部圖的例子,它不滿足定理7.6.3的條件,但是存在完美匹配.解：如第一題的例子,二部圖為