離散數(shù)學(xué)課后習(xí)題

習(xí)題參照解答習(xí)題1、（3）P：銀行利率降低Q：股價(jià)沒(méi)有上漲P∧Q（5）P：他今日乘火車(chē)去了北京Q：他隨旅游團(tuán)去了九寨溝PQ（7）P：不識(shí)廬山真面目Q：身在此山中Q→P，或～P→～Q（9）P：一個(gè)整數(shù)能被6整除Q：一個(gè)整數(shù)能被3整除R：一個(gè)整數(shù)能被2整除T：一個(gè)整數(shù)的各位數(shù)字之和能被3整除P→Q∧R，Q→T2、（1）T（2）F（3）F（4）T（5）F（6）T（7）F（8）悖論習(xí)題1（3）P(QR)P(QR)(PQ)(PR)(PQ)(PR)（4）(PQ)(QR)(RP)((PR)Q)(RP)((PR)(RP))(Q(RP))(PR)(PR)(QR)(QP)右2、不，不，能習(xí)題1、(3)P(R(~P(~P

(QP))~P(R(~QP))R)(T)~PR(~PR(~QQ))R~Q)(~PRQ)主合取范式P(R(QP)P(R(QP))P(RQ)(RP))(P(QQ)(RR)(RQ(PP))(RP(QQ))(PQR)(PQR)(PQR)(PQR)(RQP)(RQP)(RPQ)(RPQ)(PQR)(PQR)(PQR)(RQP)(RQP)(RPQ)————主析取范式2、(2)Q(PQ)(PR)(~PQ)(~PR)(~PQ(~RR))(~PR(~QQ))(~PQ~R)(~PQR)(~PR~Q)P(QR)~P(QR)(~PQ)(~PR)(~PQ~R)(~PQR)(~PR~Q)等價(jià)3、解：依據(jù)給定的條件有下述命題公式：（A→（CD））∧～（B∧C）∧～（C∧D）（～A∨（C∧～D）∨（～C∧D））∧（～B∨～C）∧（～C∨～D）（（～A∧～B）∨（C∧～D∧～B）∨（～C∧D∧～B）∨（～A∧～C）∨（C∧～D∧～C）∨（～C∧D∧～C））∧（～C∨～D）（（～A∧～B）∨（C∧～D∧～B）∨（～C∧D∧～B）∨（～A∧～C）∨（～C∧D∧～C））∧（～C∨～D）（～A∧～B∧～C）∨（C∧～D∧～B∧～C）∨（～C∧D∧～B∧～C）∨（～A∧～C∧～C）∨（～C∧D∧～C∧～C）∨（～A∧～B∧～D）∨（C∧～D∧～B∧～D）∨（～C∧D∧～B∧～D）∨（～A∧～C∧～D）∨（～C∧D∧～C∧～D）（由題意和矛盾律）（～C∧D∧～B）∨（～A∧～C）∨（～C∧D）∨（C∧～D∧～B）（～C∧D∧～B∧A）∨（～C∧D∧～B∧～A）∨（～A∧～C∧B）∨（～A∧～C∧～B）∨（～C∧D∧A）∨（～C∧D∧～A）∨（C∧～D∧～B∧A）∨（C∧～D∧～B∧～A）（～C∧D∧～B∧A）∨（～A∧～C∧B∧D）∨（～A∧～C∧B∧～D）∨（～A∧～C∧～B∧D）∨（～A∧～C∧～B∧～D）∨（～C∧D∧A∧B）∨（～C∧D∧A∧～B）∨（～C∧D∧～A∧B）∨（～C∧D∧～A∧～B）∨（C∧～D∧～B∧A）∨（C∧～D∧～B∧～A）（～C∧D∧～B∧A）∨（～A∧～C∧B∧D）∨（～C∧D∧A∧～B）∨（～C∧D∧～A∧B）∨（C∧～D∧～B∧A）（～C∧D∧～B∧A）∨（～A∧～C∧B∧D）∨（C∧～D∧～B∧A）三種方案：A和D、B和D、A和C習(xí)題1、（1）需證(PQ)(P(PQ))為永真式Q(PQ)(P(PQ))~(~PQ)(~P(PQ))~(~PQ)((~PP)(~PQ))T~(~PQ)(~PQ)TPQP(PQ)（3）需證PPRS為永真式PPRSFRSFSTPPRS3、QABAB為永真式。即~AB永真Q~ABB~A~B~A永真AB當(dāng)且僅當(dāng)~B~A4、設(shè)：P：瑰寶藏在東配房Q：藏寶的房屋湊近池塘R：房屋的前院栽有大柏樹(shù)S：瑰寶藏在花園正中地下t：后院栽有香樟樹(shù)m：瑰寶藏在鄰近（后院）命題化后進(jìn)行推理：(Q

~p)

(R

P)Q

(R

S)(t

m)~p

(R

P)(R

S)(t

m)~R

(R

S)

(t

m)S(t

m)即S為真，瑰寶藏在花園正中地下5、(1)F(P=0,Q=1)(2)F(P=1,Q=R=0)(3)F(P=0,Q=1)習(xí)題1.（1）~PQ,R~QP~R證：利用CP規(guī)則①

P

P(附帶前提

)②

~P

Q

P③

Q

T①②I④

R~Q

P⑤~RT③④I⑥結(jié)論建立CP規(guī)則①⑤（2）(PQ)(RS),(SVE)BPB證：①PP(附帶)②P∨QT①③(PQ)(RS)P④RST②③⑤ST④⑥S∨ET⑤⑦S∨E→BP⑧BT⑥⑦⑨PBCP(①⑧)(2)P：無(wú)任何印跡Q：失竊時(shí)，小花在OK廳R：失竊時(shí)，小英在OK廳S：失竊時(shí)，小胖在鄰近T：金剛是盜竊者M(jìn)：瘦人是盜竊者命題可符號(hào)化為：{P,

Q

R,

S

P,Q

T,

S

R,

R

M}證：①

P

P②

S~P

P③~ST①②④~S~RP⑤~RT③④⑥QRP⑦QT⑤⑥⑧QTP⑨TT⑦⑧∴金剛是竊賊。3.(1)不相容(2)相容P1,RQS0（3）不相容（4）不相容4.(1)證：P~QRSS~Q(PQ)P~P~QRS~S~Q~PQP即~P~Q,RS,~S~Q,~PQ,P利用消解原理：①PP②~P~QP③~Q①②④~PQP⑤~P③④⑥~PPF□①⑤習(xí)題1.(1)Ax：x是實(shí)數(shù)Bx：x是有理數(shù)xBxAxxAxBxxAxBx(2)Ax：x是直線(xiàn)Fx,y：x與y平行Gx,y：x與y訂交abAaAbFa,bGa,b(3)A(x)：x是會(huì)員C(x)：x存心義F(x,y)：x參加ya：這個(gè)活動(dòng)CaxAxFx,a或許x(AxFx,a)Ca（4）Ax：x是正整數(shù)B(x)：x是合數(shù)C(x)：x是質(zhì)數(shù)xAxBxCx（5）Ax：x是人B（x）：x存錢(qián)a：利息P:存錢(qián)有益息Fx,y：x想有yxAxBxFx,aPAxBx2.(1)P0P1P2R0R1Q2(2)P0Q0P1Q1P2Q24.(1)xyPx,yQy,tzRx,y,z習(xí)題1.（1）D：數(shù)Ax:x0fx,yxyxyAfx,yAxAyAx1Afx1,x1可知足式(2)Ax:x是誠(chéng)實(shí)的人Bx:x講真話(huà)a：小林xAxBxAaBa可知足式(3)Ax:x不廉價(jià)Bx:x是好貨Fx,y:x買(mǎi)的ya：衣服b：小王xAxBxFa,bAaBa可知足式（4）Ax:x是作家Bx:x懂得人性實(shí)質(zhì)Cx:x是詩(shī)人Dx:x是真實(shí)的x:x能刻畫(huà)人們心里世界Fx:x很高妙Px,y:x創(chuàng)作了ya：莎士比亞b：哈姆雷特xAxBxFxCxE(x)DxPa,b(x)A(x)B(x)E(x)xC(x)P(x,b)D(x)2.(1)3.(1)

TF(2)T4.D:實(shí)數(shù)P(x,y):yex,Q(y):y0習(xí)題1.（1）xyPxQyxy~PxQyxy~PxyQyx~PxyQ(y)~xPxyQ(y)AxPxyQ(y)不建立D={0,1,2}

P(0)P(1)P(2)Q(0)Q(1)Q(2)0,,1,,10013.(1)~xPxyPy~~xPxyPy~x~PxyPyxPxy~PyxyPx~Py——skolem范式(2)~xPxyzQy,z~~xPxyzQy,zxPxyz~Qy,zxyzPx~Qy,z——前束范式xyPx~Qy,fx,y——skolem范式習(xí)題1.（1）證：在某個(gè)解說(shuō)下，

xyPx

Q(y)

取值

1，必有

a,b

D,Pa

Qb

，取值

1，所以，

a

D

Pa

取值

1。xPx取值1，由定義，包含關(guān)系建立。（2）①

~

xPx

Qa

~xPx

~QaxPx

~Qa(2)證:

在某個(gè)解說(shuō)下，

~

xPx

Qa

取值

1即xPxQa取值0，分二種狀況：i)

xPx

0，則不論

Qa

為什么值，

xPx

~Qa

取值

1。ii)

Qa

0

xPx

1，則

xPx

~Qa

取值

1由定義，包含關(guān)系建立。習(xí)題1（2）（反證法）①~xPxQx②xPxQx③x~~PxQx④xPx~Qx⑤Px~QxPxxPx⑧xPxxQxxQx~Qx11○Qx12○□(1)錯(cuò)誤，應(yīng)換元，即①xPxQx，

PT①,ET②,IT③,IUS④T⑤,IUG⑥PT⑧,IT⑤,IUS⑨T⑩11I○②PyQx（2）正確（3）錯(cuò)誤，a、b應(yīng)是同一個(gè)常元（4）錯(cuò)誤，因?yàn)樵赑xx[QxR(x)]中x其實(shí)不是自由出現(xiàn)(5)錯(cuò)誤，因?yàn)樵趚PxQx中，前件是命題，爾后件不是命題6）錯(cuò)誤，因?yàn)閍、b其實(shí)不是同一個(gè)常量7）錯(cuò)誤，①②和③④的次序不對(duì)應(yīng)先使用ES，再使用US3(1)解：設(shè)F(x,y):x≥y;G(z):z≥0;f(x,y)=x-y前提：(x)(y)（F(x,y)→G(f(x,y))(x)(y)（F(x,y)→G(f(x,y))(x)(y)(G(f(x,y)→G(f(y,x)))結(jié)論：(x)(y)（G(f(x,y))∨G(f(y,x))）證明（反證法）：(x)(y)（G(f(x,y))∨G(f(y,x))）②（ｘ）（ｘ）（G(f(x,y))∨G(f(y,x))）G(f(a,b))∧G(f(b,a))(x)(y)（F(x,y)→G(f(x,y))F(a,b)→G(f(a,b))G(f(a,b))→F(a,b)(x)(y)(G(f(x,y)→G(f(y,x)))G(f(b,a))→G(f(a,b))(x)(y)（F(x,y)→G(f(x,y))F(a,b)→G(f(a,b))G(f(a,b))→F(a,b)⑿F(a,b)∧F(a,b)（2）證：第一，將結(jié)論否認(rèn)否作為前提加入到原有前提中xPxxPxQxRxxPxxQx~xyRxRxx~Pxx~PxQxRxuPuvQv~wyRwRyxuvwy~PxRx~Px~QxRxPuRu~Rw~Rwxwy~PxRx~Px~QxRxPaQb~Rw~Ry

Skolem范式子句集為~PxRx,~Px~QxRx,Pa,Rb,~Rw~Ry①~PxRx②Pa③Rx①,②代換{a/x}④Rc③代換{c/x}⑤~Rw~Ry⑥~Ry④,⑤代換{c/w}⑦~Rc⑥代換{c/y}⑧□習(xí)題3、2A2Bx2A或x2B(1)xxA或xBxABx2AB等號(hào)建立的條件為：AB（）“”2A2Bx2A和x2B2xxA和xBxABx2AB“”如x2AB，因?yàn)樯鲜鲞^(guò)程可逆x2A2B習(xí)題2.RRRRR12345關(guān)系性質(zhì)自反性×√√√×反自反性××××√對(duì)稱(chēng)性×√√√×反對(duì)稱(chēng)性√×××√傳達(dá)性√√√×√習(xí)題2.（3）“”R是對(duì)稱(chēng)的，設(shè)x,yR則y,xRx,yR1y,xR1x,yRy,xR，即R1R“”RR1x,yR，由R1的定義，y,xR1y,xR，即R是對(duì)稱(chēng)的。（5）“”R是傳達(dá)的，對(duì)x,zR2yAx,yRy,zRx,zR即R2R“”R2R，x,yRy,zR2，對(duì)，由R的定義，有x,zR2Rx,zR，即R是可傳達(dá)的。4.解：RRR，且RR2121RmRm1Rm2AA1A2R13IAR25IA,需3|m，5|m12m15，即n16R16R16R16RRR1212故使RmRn的最小正整數(shù)m1,n16習(xí)題2、解：01000000111000001110000000100000111000001000000000011111MR00001000Mt(R)00011111000001000001111100000010000000010001111100001000000111113.(3)證：t(R1)iURi11t(RR)U(R1R)i12i12由概括法可證：對(duì)iN

it(R2)URi12iiR)iRR(R2121t(R)t(R)URiiiiR)it(RR)2URU(RR)U(R21i11i12i112121i1(4)證：①RRRt(R)URii1RtRUtRjj1由概括法可證：jNtRjtRRUtRjUtRtRRj1j1③RRRRIAtRRRRIAtRRIARtRRRtRtRR習(xí)題1.證：Aa,b|a,bNRa,b,c,d|adbc①自反性由A的定義，abbaa,bNa,b,a,bR②對(duì)稱(chēng)性設(shè)a,b,c,dR，則adbc即cbdac,d,a,bR③傳達(dá)性設(shè)a,b,cd1R，則adbc1111111c1,d1,c2d2R，則c1d2d1c2a1d1d2b1c1d2b1d1c2a1d2b1c2a1,b1,c2,d2R3.解：A1,2,3,4,,S01,2,4,3設(shè)A11,2,3,4,A231，1，1，2，1，42，1，2，2，2，4，4，1，4，2，4，4，3，3解：∵每個(gè)會(huì)合的區(qū)分就能夠確立一個(gè)等價(jià)關(guān)系∴會(huì)合有多少個(gè)區(qū)分就能夠確立多少個(gè)等價(jià)關(guān)系4321種。CCCC154444解：①R1UR2不是A上的等價(jià)關(guān)系②R1R2是A上的等價(jià)關(guān)系rR1R2是A上的等價(jià)關(guān)系④R1oR2不是A上的等價(jià)關(guān)系習(xí)題解：Aa,b,c2A,a,b,c,a,b,a,c,b,c,a,b,c{a,b,c}{a,b}{a,c}{b,c}{a}{c}<2C,>3.解：會(huì)合A上的空關(guān)系、恒等關(guān)系IA都是等價(jià)關(guān)系和偏序關(guān)系。6.解：Aa,b,c,d2A,a,b,c,d,a,b,a,c,a,d,b,c,b,d,c,d,a,b,c,a,b,d,b,c,d,a,c,d,a,b,c,dabcda,ba,ca,db,cb,dc,da,b,ca,b,da,c,db,c,da,b,c,d7.證：i）自反性，對(duì)bBA,b,bR，（R的自反性）明顯b,bBBb,bRBBii)反對(duì)稱(chēng)性，對(duì)a,bB,a,bRBB,b,aRBB即a,bR,b,aR，由R的反對(duì)稱(chēng)性，abiii)傳達(dá)性，對(duì)a,b,cB，設(shè)a,bRBB,b,cRBB，則a,bR，b,cR。由R的傳達(dá)性，a,cR，明顯a,cBBa,cRBB習(xí)題4、證：1）對(duì)b1、b2B，b1b2f(x)是滿(mǎn)射，a1、a2A,f(a1)b1,f(a2)b2由g(x)的定義，a1g(b1),a2g(b2)，且a1g(b2),a2g(b1)不然，如a1g(b2),a2g(b1)，有f(a1)b2,f(a2)b1與函數(shù)的定義相矛盾，g(b1)g(b2),即g(x)為單射）而為單射時(shí)，對(duì)bB,其實(shí)不可以保證g(b),2g(x)f(x)不必定是滿(mǎn)射7、證：f:AB,g:BC（）反證法：設(shè)不是單射，x1x2A,f(x1)f(x2)1即gf(x1)g(f(x1))g(f(x2))gf(x2)與gf為單射矛盾（）f為滿(mǎn)射2g對(duì)zC,gf(x)令f(x)yyB,

xA,g(f(x))Bg(y)

z

z即g為滿(mǎn)射習(xí)題:3．證明：非空有限集A與可數(shù)集B的笛卡爾積A×B也是可數(shù)集。證明：設(shè)A={a1,a2,,an｝B={b1,b2,,bn}令Bi={(ai,b1),(ai,b2),,(ai,bn),}≤(in),則kA×B=UBi

,i1因?yàn)锽為可數(shù)集，所以Bi為可數(shù)集。A×B為有限個(gè)可數(shù)集的并集。下邊用概括法證明有限個(gè)(m個(gè))可數(shù)集的并集為可數(shù)集。設(shè)Cm={cm1,cm2,mn,c,}當(dāng)m=2時(shí)，結(jié)構(gòu)雙射f:N→C1∪C2,N123456n-1nf(N)c11c21c12c22c13c23c1(n/2)c2(n/2)所以2個(gè)可數(shù)集的并集為可數(shù)集。假定m=k-1(k≥3)時(shí)結(jié)論建立，即k-1個(gè)可數(shù)集的并集為可數(shù)集，記為D。則m=k時(shí)，能夠結(jié)構(gòu)近似的雙射g:N→D∪Ck,所認(rèn)為可數(shù)集。因此有限個(gè)可數(shù)集的并集為可數(shù)集。所以A×B是可數(shù)集。習(xí)題1．設(shè)G是一個(gè)(n,m)簡(jiǎn)單圖。證明：m≤Cn2,等號(hào)建立當(dāng)且僅當(dāng)G是完整圖.nd(k)，d(k)表示第k個(gè)結(jié)點(diǎn)的度證明：由歐拉定理，2m=k1因?yàn)镚是簡(jiǎn)單圖，所以d(k)≤n-1,等號(hào)建立當(dāng)且僅當(dāng)G是完整圖nnd(k)n1,2m=k1≤k1所以2m≤n(n-1)即m≤n(n1)=Cn223、解：（1）不是圖的序列，因?yàn)槠鏀?shù)度結(jié)點(diǎn)的個(gè)數(shù)不是偶數(shù)。（2）、（3）、（4）都是圖的序列。4、證：由歐拉定理，2md(v)vGd(v)vG

vG

vGn

d(v)

2m

nvG2mn9．若，稱(chēng)G是自補(bǔ)圖。確立一個(gè)圖為自補(bǔ)圖的最低條件；畫(huà)出一個(gè)自補(bǔ)圖來(lái)。解：設(shè)G=(n,m)，G’=(n,m’)則m+m’=n(n-1)/2,所以m=m’=n(n-1)/4v3v3v4v4v2v1v2v1G習(xí)題1、若u和v是圖中僅有的兩個(gè)奇度數(shù)結(jié)點(diǎn)，證明u和v必是連通的。證：（反證法）設(shè)v與u不連通G={V1，V2}，v與u分別屬于V1，V2二個(gè)子圖∵v與u是G中僅有的二個(gè)奇數(shù)度結(jié)點(diǎn)v與u即是V1與V2中僅有的一個(gè)奇數(shù)度結(jié)點(diǎn)，與歐拉定理的推論相矛盾,故v與u必連通3、設(shè)(n,m)簡(jiǎn)單圖G知足m＞(n-1)(n-2)/2，證明G必是連通圖。結(jié)構(gòu)一個(gè)m=(n-1)(n-2)/2的非連通簡(jiǎn)單圖。（書(shū)上證明更好）5、設(shè)G=(V，E)是點(diǎn)度均為偶數(shù)的連通圖。證明：對(duì)任何v∈V,ω(G-v)d(v)/2證：（反證法）設(shè)結(jié)論不建立，即存在:v∈V,ω(G-v)＞d(v)/2.因?yàn)镚是連通的，所以G-v的每個(gè)分支都起碼有一個(gè)點(diǎn)與v相毗鄰，并且存在一個(gè)分支，其與v相毗鄰的點(diǎn)只有一條邊與v相連（因?yàn)槿缑總€(gè)分支中有二個(gè)以上的點(diǎn)v

V與,

v(G-v相)

1連d(v)，2則，出現(xiàn)矛盾）∴存在一個(gè)分支，此中只有一條邊與v相連；因?yàn)镚中每個(gè)結(jié)點(diǎn)的度數(shù)為偶數(shù)，所以在這個(gè)分支中就會(huì)出現(xiàn)一個(gè)奇度數(shù)結(jié)點(diǎn)，其他結(jié)點(diǎn)的度數(shù)全為偶數(shù)，與歐拉定理的推論相矛盾，故故對(duì)任何v∈V,ω(G-v)d(v)/29.證明：恰有兩個(gè)非割點(diǎn)的簡(jiǎn)單連通圖必是Pn(n≥2)證明：概括法。n=2時(shí)，結(jié)論明顯建立。設(shè)n=k時(shí)結(jié)論建立，當(dāng)n=k+1時(shí)，設(shè)v1、vk是Pk上的兩個(gè)非割點(diǎn)，vk+1是在Pk上增添的一個(gè)割點(diǎn)，假如結(jié)點(diǎn)vk+1不在Pk上的隨意兩個(gè)結(jié)點(diǎn)之間，則必與Pk上某兩個(gè)結(jié)點(diǎn)組成一個(gè)回路，vk+1就不是割點(diǎn)，與只有兩個(gè)非割點(diǎn)矛盾。故結(jié)論建立。習(xí)題3、解：v1e2v3e1e3e5e6v2e4v4v1v2v3v4v5v6v7011000000010000001100A0101001000000000001010000110

e7v5e8

v6e9e11e12e10v7v1v2v3v4v5v6v7v1v2v3v4v5v6v711111001111000111110011110001111100PPT1111000P11110011110001000000000001000000111000001100001110000011三個(gè)強(qiáng)分圖G({v1,v2,v3,v4})G({v5})G({v6,v7})e1e2e3e4e5e6e7e8e9e10e11e1211-1000000000-100100000000MG0-1001-1100000001-1-11010000000000-1-1-1-1000000000010-1100000000011-15.證明：支數(shù)為k，階數(shù)為n的無(wú)環(huán)圖G，其關(guān)系矩陣的秩是n-k.證明：將各支結(jié)點(diǎn)和邊集中編號(hào)后，G的關(guān)系矩陣M10000M200M0O0000Mk由分塊矩陣子公式及定理，γ(M)=γ(M1)+γ(M2)++γ(Mk)=(n1-1)+(n2-1)++(nk-1)=n-k習(xí)題1、設(shè)一個(gè)樹(shù)中度為k的結(jié)點(diǎn)數(shù)是nk，求它的葉的數(shù)量。解：設(shè)L是葉的數(shù)量，m是樹(shù)的邊數(shù),由Euler定理:iknkL2mk2由樹(shù)的定義:inkmL1k2iink2L2kknkL22k2i(k2)nkL2(ik2)k2習(xí)題6、證明正則二叉樹(shù)必有奇數(shù)個(gè)結(jié)點(diǎn)。證明：由正則二叉樹(shù)的定義，其葉結(jié)點(diǎn)的個(gè)數(shù)必為偶數(shù)，設(shè)葉數(shù)為t，分支數(shù)為i。由定理：(m-1)i=t-1m=1∴i=t-1有分支點(diǎn)數(shù)是奇數(shù)故結(jié)點(diǎn)數(shù)=i+t=奇數(shù)習(xí)題3、證：（反證法）設(shè)G=（n，m）和G’=（n，m’）都是平面圖由G的定義m+m’=n(n-1)/2由定理10-4.2m≤3n-6,m’≤3n-6m+m’=n(n-1)/2≤6n-12有n2-13n+24=(n-11)2+9n-97≤0又∵（n-11)2≥0，n≥11時(shí),9n-97≥2∴（n-11)2+9n-97≥2與上式相矛盾，故G與G’起碼有一個(gè)是非平面圖4、證明：擁有6個(gè)結(jié)點(diǎn)，12條邊的簡(jiǎn)單連通平面圖，它的面度都是3。證：由Euler公式，n-m+f=26-12+f=2f=8，即面數(shù)為8?！邔?duì)每個(gè)面，其度數(shù)≥3∴總面度≥3×8=24∵總面度=2×m=24∴每個(gè)面的度數(shù)為35、少于30條邊的簡(jiǎn)單平面圖起碼有一個(gè)極點(diǎn)的度不大于4。證：（反證法）設(shè)所有極點(diǎn)的度數(shù)5由Euler公式，由定理10-4.2m≤3n-63n-6≥5n/2即n≥12則m≥5n/2≥5×12/2=30與m＜30矛盾所以，起碼存在一個(gè)極點(diǎn)的度數(shù)不超出4。習(xí)題2、證明：4k+1階的所有2k正則簡(jiǎn)單圖都是哈密頓圖。證：∵G是2k正則圖，∴對(duì)隨意的u、v∈G，d(u)+d(v)=4k由定理10-6-2在G中存在一條Hamilton道路，設(shè)為：v1v2,,v4k+11)v1v4k+1∈E，則v1v2,,v4k+1v1組成一個(gè)Hamilton圈2)v1v4k+1E，則vi1,vi2,,vi2k與v1毗鄰G的階數(shù)為4k+1v4k1必與vi11,vi21,,vi2k1中的一個(gè)點(diǎn)毗鄰，（不然d(v4k+1)=4k-1-2k=2k-1與d(v4k+1)=2k矛盾)設(shè)vitv4k1E，可結(jié)構(gòu)v1,vit1,v4k1v4k,,vitv1即為G的一個(gè)Hamilton圈，故G是一個(gè)Hamilton圖5、設(shè)G是(n,m)簡(jiǎn)單圖，若mCn212,證明G必是哈密頓圖。證：（反證法）假定G不是哈密爾頓圖，則s,tG,deg(s)deg(t)n2mdeg(v)deg(v)deg(s)deg(t)vGvG{s,t}2mdeg(v)nvG{s,t}因?yàn)镚除結(jié)點(diǎn)s,t外的其他n-2結(jié)點(diǎn)之間最多能夠組成完整圖，所以2m<(n-2)(n-3)+n+n<n2-3n+6=(n-1)(n-2)+4進(jìn)而：m1(n1)(n2)2Cn2122與已知mCn212矛盾，故結(jié)論建立。習(xí)題：4.設(shè)<S，·>是一個(gè)含有幺元e的代數(shù)系統(tǒng)，a∈S.假如存在元b,c∈S使b·a=e(或a·c=e),則稱(chēng)b是a的左逆元(或c是a的右逆元)。證明：假如一個(gè)元既有左逆元b又有右逆元c，則必b=c.證明：S上的運(yùn)算·是可聯(lián)合的。b=b·e=b·(a·c)=(b·a)·c=e·c=c習(xí)題4、設(shè)半群<A,·>中任何兩個(gè)不一樣元素對(duì)于運(yùn)算“·”不行互換，證明：對(duì)任何a∈A,a·a=a證明：（反證法）設(shè)a∈A,使得a·a≠a,結(jié)構(gòu)b=a·a，則a·b=a·a·a=b·a即a、b可互換，與已知條件相矛盾a∈A,a·a=a5.設(shè)S={00,111,1010}是字符集Σ={0,1}上的字會(huì)合。試結(jié)構(gòu)Σ*的一個(gè)包括會(huì)合S的最小的含幺子半群。解：令空字符為λ.m,n,k為正整數(shù)，T={λ,(00)m,(111)n,(1010)k}∪{(00)m(111)n(1010)k}∪{(00)m(1010)k(111)n}∪{(111)n(00)m(1010)k}{(111)n(1010)k(00)m}∪{(1010)k(00)m(111)n}{(1010)k(111)n(00)m}λ01111010習(xí)題1、證明：群中只有幺元是冪等元。證：（反證法）設(shè)a

A,a

e,

a2

a，a

1

,

aa2

?a

1

a?a

1

e矛盾5、寫(xiě)出s3,中的所有子群。解：（1），（12），（1），（13），（1），（23），（1），（123），（132）和二個(gè)平庸子群。6、設(shè)<S，·>和<T，·>都是<G,·>的子群，令S∩T={x|x∈S∧S∈