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

習(xí)題參考解答

習(xí)題1.1

1、(3)P：銀行利率降低

Q：股價(jià)沒有上升

PAQ

(5)P：他今天乘火車去了北京

Q：他隨旅行團(tuán)去了九寨溝

PVQ

(7)P：不識廬山真面目

Q：身在此山中

Q—P,或?P-*?Q

(9)P：一個(gè)整數(shù)能被6整除

Q：一個(gè)整數(shù)能被3整除

R：一個(gè)整數(shù)能被2整除

T：一個(gè)整數(shù)的各位數(shù)字之和能被3整除

P-QAR,Q-T

2、(1)T(2)F(3)F(4)T(5)F

(6)T(7)F(8)悖論

習(xí)題1.3

1(3)

pT(0VR)=-1Pv(。vR)=(-1Pvg)v(-1PvR)

Q(PTQ)V(PTR)

(4)

(P人。)V(。AR)V(R人P)=((PV/?)A2)V(7?AF)

=((PV/?)V(/?AP))A(。V(R△P))

=(尸VR)A(PVR)A(0VR)A(QVP)

=右

2、不，不，能

習(xí)題1.4

1、⑶P7(R人(。一?P))=~PV(RA(~QVP))

=(~PvR)人(T)=~PvR=(~PvR\/(~。人。))

二(?PvRY?Q)人(?PVRVQ)

主合取范式

PT(RA(。-P)

=Yv(R人(]?v尸))

=^PV(/?A-10)V(7?AP))

=(-iPA(-\QvQ)A(-\Rvi?)v(7?A-\QA{-\PvJP))V(7?AJPA(-\Qv。))

=(―\PA―\QA-\R)V(―\P人0A.―iR)V(—\PA-\QA7?)V(—\PA-\QA/?)V

(RA-1(2人—＞尸)V(/?A-10AP)v(/?APA-10)V(/?APA0)

=(―PA—I。A―\R)V(—\PA)2A-LR)V(一尸A—\QAR)V

(KA-10A-iP)v(7?A—\Q人P)v(K人P人。)

--------主析取范式

2、(2)?..(P-?。)人(P-R)=(~PVQ)A(~PVR)

二(?戶vQv(?R八/?))△(?PV/?V(~QA。))

二(~PvQy~R)A(~Pv。vR)八(?PvRr~Q)

P7(。八R)=~Pr(Q八R)

=(~尸vQ)A(?尸△R)

二(~PvQy?R)八PvQvH)A(?PvRv~Q)

等價(jià)

3、解：根據(jù)給定的條件有下述命題公式：

(A-*(CVD))A?(BAC)八?(CAD)

o(?AV(C八?D)V(?CAD))A(?BV?C)A(?CV?D)

<=>((?AA?B)V(CA-DA-B)V(?CADA?B)V

(?AA?C)V(CA-DA-C)V(-CADA-C))A(?CV?D)

<=>((?A八?B)V(CA-DA-B)V(-CADA-B)V

(?A八?C)V(-CADA-C))A(?CV?D)

o(?AA?B八?C)V(CA?D八?BA?C)V(?CADA?BA?C)V

(?AA?C八?C)V(?CAD八?C八?C)V(?A八?B八?D)V

(C八?DA?BA?D)V(?CADA?B八?D)V(?AA?CA?D)V

(?CAD八?CA?D)(由題意和矛盾律)

o(?CADA?B)V(?AA?C)V(?CAD)V(C△?D八?B)

=(-CADA-BAA)V(?CADA?BA?A)V(-AA-CAB)V

(~AA-CA-B)V(-CADAA)V(-CADA-A)V

(CA-DA-BAA)V(CA?DA?B八?A)

o(?CAD八?BAA)V(?AA?CABAD)V(?A/\?CABA?D)V

(?A/\?C八?BAD)V(?A/\?C八?B八?D)V

(-CADAAAB)V(-CADAAA-B)V(-CADA-AAB)V

(-CADA-AA-B)V(CA-DA-BAA)V(C八?D△?B八?A)

=(?CAD八?BAA)V(-AA-CABAD)V(~CADAAA-B)V

(?CADA?AAB)V(CA~DA~BAA)

=(-CADA-BAA)V(-AA-CABAD)V(CA-DA-BAA)

三種方案：A和D、B和D、A和C

習(xí)題1.5

1、(1)需證(尸TQ)T(P—>(PA。))為永真式

?..(P-?Q)-?(P7(PAQ))=~(~PVQ)V(~PV(PAQ))

~P7P

=~PvQ)v((T)A(~PvQ))

=~P7Q)7P7Q)=T

/.PTQ=PT(PAQ)

(3)需證尸△-1P-?S為永真式

PA-\PAR—>SF八R—>SF—>ST

PA—iPARnS

3、；AnB」.ATB為永真式。即~4丫8永真

,/?AvB=Bv?A=?BA永真

/.4=>8當(dāng)且僅當(dāng)~8二>~4

4、設(shè)：P：珍寶藏在東廂房

Q：藏寶的房子靠近池塘

R：房子的前院栽有大柏樹

S：珍寶藏在花園正中地下

t：后院栽有香樟樹

m：珍寶藏在附近(后院)

命題化后進(jìn)行推理：

(Q—p)八(R-P)八。八(RvS)八(t—m)

n?pA(R―P)△(/?vS)A(f—?加)

n?7?A(7?v5)A(z—?m)

nS八(/—?m)

即S為真，珍寶藏在花園正中地下

5.(1)F(P=QQ=l)②Fg,Q^O)(3)F(P=0,Q=l)

習(xí)題1.6

1.(1)~P7Q,RQnPR

證：利用CP規(guī)則

①p產(chǎn)(附加前提)

②~PvQP

③QT①②I

④RT~QP

⑤~RT③④I

⑥結(jié)論成立CP規(guī)則①⑤

(2)(PvQ)7(R八S),(SVE)TBnPTB

證：①PP(附加)

PVQT①

(PVQ)T(RAS)P

④RAST②③

⑤ST④

⑥SVET⑤

⑦SVE-*BP

⑧BT⑥⑦

PTBCP(①⑧)

2.(2)P：無任何痕跡

Q：失竊時(shí)，小花在OK廳

R：失竊時(shí)，小英在OK廳

S：失竊時(shí)一，小胖在附近

T：金剛是偷竊者

M：瘦子是偷竊者

命題可符號化為：

{P,QvR,ST「P,QTT,t->R,RtM}

證：①PP

②ST~PP

③~sT①②

④?S-"RP

⑤~RT③④

⑥QvRP

⑦QT⑤⑥

⑧QTTP

⑨TT⑦⑧

.??金剛是竊賊。

3.(1)不相容

(2)相容(P=l,R=Q=S=O)

(3)不相容

(4)不相容

4.⑴證:(PT~Q)人(RVS)A(ST~Q)人(P—Q)人尸

<=>Pv~Q）A（RvS）A（~Sv~Q）A（~尸VQ）AP

即中={~Pv~Q,RvS,~Sv~g,~Pvg,P}

利用消解原理:

①尸P

②~Pv~QP

③①②

④~PvQP

⑤-P③④

⑥~PAP=F□①⑤

習(xí)題2.1

1.(l)A(x)：x是實(shí)數(shù)B(x):x是有理數(shù)

V（x）（B（x）-?A（X））A—iVx（A（x）8（X））A3x（A（x）AB（X））

（2）A（x）：x是直線

F（x,>1）：x與y平行G（x,y）:x與y相交

Way/b[A（a）AA（b）t（F（a,b）—」G（a,'））]

（3）A（x）:x是會員C（x）:x有意義

F（x,y）:x參加ya:這個(gè)活動

C（a）—>Vx（A（x）—>F（x,a））

或者-iMx（A（x）—>F—>―iC（a）

（4）A（x）:x是正整數(shù)B（x）：x是合數(shù)C（x）:x是質(zhì)數(shù)

Vx（A（x）TB（x）VC（x））

（5）A（x）：X是人B（x）：x存錢a：利息

P：存錢有利息F（x,y）：x想有y

Vx［（A（x）AB（x）—>F（x,a））A（-IP—>A（x）A-d?（x））］

2.（1）p（o）Ap（l）AP（2）A（/?（o）V1?（1）ve（2））

（2）［P（0）T0（0）］人［P⑴T2（1）］A［p（2）T0（2）

4.⑴（VxXm_y）［P（x,y）TQ（y,f）］v（Vz）R（x,y,z）

習(xí)題2.2

1.(1)D：數(shù)A(x):x=Of(x,y)=xy

VxVy[A(/(x,j))-A(x)vA。)]A-1A(x-1)T-1A(/(x-l,x+1))

可滿足式

(2)A(x)：x是誠實(shí)的人M%)：x講實(shí)話a：小林

Vx[A(x)-?B(x)]A—i4(?)-?—iB(a)

可滿足式

(3)A(x):x不便宜8(x):x是好貨

/(x,〉):》買的ya：衣服b：小王

VX[A(X)—?B(X)]AF(?,Z>)AA(a)—>B(a)

可滿足式

(4)A(x):x是作家8(x)：x懂得人性本質(zhì)

C(x):x是詩人O(x):x是真正的

E(x):x能刻畫人們內(nèi)心世界

尸(x)：x很高明p(x,y):x創(chuàng)作了y

a：莎士比亞b:哈姆雷特

Vx[(A(x)AJB(X)—>F(x))A(C(x)A—iE(x)—>—i￡)(x))]AP(a,b)

A—i(3x)(A(x)A—iB(x)AE(x))AVx[c(x)AP(x,b)—?￡>(x)]

3.(1)F(2)T

4.D:實(shí)數(shù)P(x,y):y=ex,g(j):j>0

習(xí)題2.3

1.(1)%3y[P(x)T0。)]

Q3x3y[~P(x)v0()，)]

Q玉日y~P(x)v小，0(y)]

<=>Hr~P(x)v力。(y)

=~VxP(x)v寺0(y)

<=>(Ax)P(x)-?(3j)0(j)

2.不成立

nh1CIP(°)P⑴P⑵2(°)2(1)2⑵

D={0,l,2}二，丁，丁丁，丁，丁

3.(1)~((VX)P(X)T(W))

o~(Vx)P(x)v(3y)P(y))

=~((五)(~P(x"⑶)P(y))

Q(VX)「(x)A(VyX~P(y))

<=>(VXXVJ)(P(X)A~P(j))skolem范式

⑵~((Vx)P(x)T0y)(Vz)e(y,z))

<=>~(~(Vx)P(x)v3(j)(Vz)g(j,z))

=(VX)P(X)A(VJX3Z)~2(y,z)

q(VxXVyX3zX^(x)A~2(y，z))-----前束范式

<=>(VxXVy)(P(x)人~0(J,/(x,j)))—skolem范式

習(xí)題2.4

1.⑴證:在某個(gè)解釋下，缶X力）［尸（x）AQ（y）］取值1,必有訴D,

P（a”Q0）,取值1,因此，BaeDP⑷取值1。

」.（玉）P（x）取值1,由定義，蘊(yùn)含關(guān)系成立。

（2）①?（0x）P（x）A0（a））o~0x）P（x）v~Q（a）

Q（玉）P（x）->~Q（a）

（2）證：在某個(gè)解釋下，~（（玉）P（x）人Q（a））取值1

即（玉）P（x）人Q（a）取值0,分二種情況：

i）0x）P（x）=O,則無論。（a）為何值，（玉）P（x）->~Q（a）取值1。

ii）Q（a）-0（玉）P（x）=l,則（玉）P（X）T~。⑷取值1

由定義，蘊(yùn)含關(guān)系成立。

習(xí)題2.5

1（2）（反證法）

①?（玉）［p（x）-?Q（x）］P

②（VX）［P（X）T°（X）］T①,E

③（Vx）［~（~P（x）->v0（x）］T②,I

④（VX）（P（X）A~Q（X））T③,1

⑤P（x）/\~Q（x）US④

⑥P（x）T⑤,I

⑦（Vx）P（x）UG@

⑧（VX）P（X）T（X/X）Q（X）P

⑨（Vx）Q（x）T⑧,I

⑩?如）T⑤,I

OQ（x）US⑨

運(yùn)口T⑩。I

2.（1）錯(cuò)誤，應(yīng)換元，即

①（VX）P（X）TQ（X）,

②P（y）TQ（x）

(2)正確

(3)錯(cuò)誤，a、b應(yīng)是同一個(gè)常元

(4)錯(cuò)誤，因?yàn)樵赑(_X)V(3X)[°(%)AR(%)]中％并不是自由出現(xiàn)

(5)錯(cuò)誤，因?yàn)樵?玉)P(x)->Q(x)中，前件是命題，

而后件不是命題

(6)錯(cuò)誤，因?yàn)閍、b并不是同一個(gè)常量

(7)錯(cuò)誤，①②和③④的順序不對

應(yīng)先使用ES,再使用US

3(1)解：設(shè)F(x,y):xNy;G(z):zNO;f(x,y)=x-y

前提：

①V(x)V(y)(F(x,y)-G(f(x,y))

②V(x)V(y)(」F(x,y)-*-1G(f(x,y))

③V(x)V(y)(-iG(f(x,y)fG(f(y,x)))

結(jié)論：V(x)V(y)(G(f(x,y))VG(f(y,x)))

證明(反證法)：

①-1V(x)V(y)(G(f(x,y))VG(f(y,x)))

②Gx)Gx)「(G(f(x,y))VG(f(y,x)))

③「G(f(a,b))A」G(f(b,a))

@V(x)V(y)(F(x,y)-*G(f(x,y))

⑤F(a,b)-*G(f(a,b))

⑥-1G(f(a,b)),->F(a,b)

⑦V(x)V(y)(-1G(f(x,y)fG(f(y,x)))

⑧「G(f(b,a))-*G(f(a,b))

⑨V(x)V(y)(-iF(x,y)->-iG(f(x,y))

⑩—iF(a,b)iG(f(a,b))

(IDG(f(a,b))F(a,b)

?-nF(a,b)AF(a,b)

4.(2)

證：首先，將結(jié)論否定否作為前提加入到原有前提中

旗獷(尤)T(Vx)[(p(x)V0(X)T/?(%))]}A0x)p(x)人(玉)Q(X)A

~(玉)0y)[R(x)八R(x)]

Q{(VX)~P(X)v(Vx)[~(p(x)V(2(x))VA(3M)F(w)A(3V)<2(V)A

~(3w)(3y)[/?(vv)A/?(y)]

Q(Vx)(3?)(3V)(VVV)(V)')[(~P(X)VR(x))A(~P(x)v~Q(x)vR(x))]

A^(z/)A/?(?)A(~7?(W)V~/?(W))]

<=>(Vx)(Vvv)(Vy)[(~P(x)v/?(X))A(~P(x)v~Q(x)v/?(X))A-(a)A。⑸]

A(~/?(w)v~/?(>1))]Skolem范式

子句集為｛~P（x）v/?（%）,-P（x）v~Q（x）vR（x\p（a）,硝,~R（w）v~R（y）｝

①?p（x）vR（x）

②P（。）

③R（X）①,②代換｛a/x｝

④R?③代換卜/x｝

⑤~R（w）v~H（y）

⑥?祗）④,⑤代換｛c/w｝

⑦?碓）⑥代換｛c/y｝

⑧口

習(xí)題3.4

(1)XG2A\J2B=xt2A或2B

=x=A或xcB=>xcAljB=>xe2AUB

等號成立的條件為：AAB=^

②2人028nxe2”和xe2^

nx聶A和xaBnxqAClBnxe2AnB

“u”如xc2AnB,由于上述過程可逆=>XG2AP2B

習(xí)題5.2

2.

RiR2R3RiRs

性質(zhì)、

自反性XVJVX

反自反性XXXXV

對稱性XVJVX

反對稱性XXXV

傳遞性JJXV

習(xí)題5.3

2.(3)"n"R是對稱的，設(shè)(x,y)eR則RR

v<j,x>eR~lx,y>eRy,x>eR,BPR~l=R

"<="R=R-iV(x,j)eR,由R”的定義，&㈤wRT

：.{y,x)eR,即R是對稱的。

(5)“n”R是傳遞的，對V<x,z>eR2

GA3<x,y>ER<y,z>GR/.<x,z>GR

即/?2小

“u”R2qR,,對V<x,y>eR<j,z>eR,由R?的定義，

有<x,z>eR2qR/.<x,z>eR,即R是可傳遞的。

4.解：?.?/?=口通，且與口尺2=中

mmm

/.R=Ri\jR2A=AXUA2

R=I

.,./?；=/&2A2^.,?需3|m,5|m

nm=15,gp〃=16

Rl6=肝6u用6=&u曲=A

故使Rm=Rn的最小正整數(shù)m=l,n=16

習(xí)題5.4

2、解;

(i1100000、

01000000"

11100000

00100000

11100000

10000000

0000100000011111

M=監(jiān)⑻=

KR0000010000011111

0000001000011111

0000000100011111

川0001000,1。0011111>

00i00i

3.⑶證：t(R2)=UR

1=111=12

t(RiU&)=I(&UR2)'

i=l~

由歸納法可證：對WieN+R；UR；q(RiUR2)i

(8；\oo

=/(A：UR：)q/(&UR2)'=f(&UR2)

.」因)山(曲)=VRUU

v=1VU=i2J1=112i=l

+00

（4）證：①（R+曠=RR+=f(R)=UK

1=1

1+1=（女））+=3（f（R）y

尸1

由歸納法可證：VjwN+（f（R）V=f（R）

(R+y=U(?R)y=u(?R))=/(/?)=R+

j=lj=l

③R。R*=R+?.R*=/AU,R)

RoR*=RO(IA\Jt(R})=ROIA\JROt(R)

=R\jRot(R)=t(R)=R+

習(xí)題5.5

1.證：A={(a,/?)Ia,feeN+]

R={((a,A),(c,d))lad=bc}

①自反性由A的定義，ab=baa,beN

???((a,/?),(〃,/?加R

②對稱性設(shè)((〃力),(c,d))￡R,則ad=Z?c

即cb-da((c,d),(a,b))￡R

③傳遞性設(shè)((ai，%),(ciH))wR,則a@=%ci

R,貝ljc〃2=4。2

=>0]4d2=4C02=61dle2=>a，2=仇，2

((q,仇),(c2，d2))eR

3.解：?「A={1,2,3,4,},So={{1,2,4},{3}}

設(shè)A={1,2,3,4},4={3}

...R={(1,1),(1,2),(1,4)(2,1),(2,2),(2,4),(4,1),(4,2),(4,4),(3,3)}

4.解：???每個(gè)集合的劃分就可以確定一個(gè)等價(jià)關(guān)系

.??集合有多少個(gè)劃分就可以確定多少個(gè)等價(jià)關(guān)系

4321工人

C+C+C+C=15種。

4444

5.解:

①單/此不是A上的等價(jià)關(guān)系

②R|Ca是A上的等價(jià)關(guān)系

③《/?「凡)是A上的等價(jià)關(guān)系

④用。魚不是A上的等價(jià)關(guān)系

習(xí)題5.6

2.解：A-{a,b,c}

2'={①,(a),⑸,(c),(a,b),(a,c),(〃,c),(a,6,c)}

<?,c>

3.解：集合A上的空關(guān)系中、恒等關(guān)系h都是等價(jià)關(guān)系和偏序關(guān)系。

6.解：A=(a,b,c,d)

2A={0,(a),(/?),(c),(d),(a,Z>),{a,c\(a,d\(b,c\(b,d),(c,d),(a,b,c),(a,b,d),(/?,c,d),(a,c,d),(a,b,c,d)}

①<(a)<(6)<(c)<(J)<(a,b)<(a,c)<(a,J)<(ft,c)<(b,J)<(c,J)<(a,c)<(a,)

<(a,c,d)<伍(a,b,c,d)

7.證：i）自反性，對VbeBqA,/.（b,b）eR,（R的自反性）

顯然/.?b)GRCBxB

ii)反對稱性，對(a,b)ERC\BxB,(b,a)eRC\BxB

即(a,b)e￡,(b,a)e￡,由R的反對稱性,=>a=b

iii)傳遞性，對W”,仇ce5,^(a,b)eR^BxB,(b,c)eRr\BxB,

WJR,(b,c)eRo

由R的傳遞性，(?,c)eR,顯然(a,c)w5x3

/.(a,c)ERp\BxB

習(xí)題6.2

4、證：

D對Vbi、b2eB,如Wb2

b

???/")是滿射,/.3aPa2eA,3f(ax)=3/^2)=2

由g(x)的定義,ajeg(b1),a2eg(b2),Kajg(b2),a2?g(bx)

否貝！J,如ajeg(b2),a2Gg(如),有f(al)=b2,f(a2)=bx

與函數(shù)的定義相矛盾，；.g(b1)Ag?),即g(x)為單射

2)而g(x)為單射時(shí)，對VbeB,并不能保證g(b)W0,

/.f(x)不一定是滿射

7、證：f:ATB,g:BlC

①反證法：設(shè)不是單射，Sxj^x2eA,3f(xY)=f(x2)

即g°f(Xi)=g(#q))=g(f(x2))=g°/(x2)

與g。/為單射矛盾

②?.修/為滿射

.,.對VzeC,3XGA,

3g°/(X)=g(/(X))=Z

令=B

:.3yeB,3g(y)=z

即g為滿射

習(xí)題6.4:

3.證明：非空有限集A與可數(shù)集B的笛卡爾積AXB也是可數(shù)集。

證明：設(shè)A={a1a2,…,aj

B={bbb2,…,bn,,?,)

令Bi={(a“bi),(ai,b2),…，(a”bn),???}(iWn),則

k

AXB=LiB,,

i=l

因?yàn)锽為可數(shù)集，所以R為可數(shù)集。AXB為有限個(gè)可數(shù)集的

并集。下面用歸納法證明有限個(gè)(m個(gè))可數(shù)集的并集為可數(shù)集。

設(shè)Cm—{Cml,Cm25***,Cmn,***}

當(dāng)m=2時(shí)，

構(gòu)造雙射f：N-GUC2,

N123456n-ln…

f(N)CHC21C12C22C13C23,**Cl(n/2)C2(n/2)…

所以2個(gè)可數(shù)集的并集為可數(shù)集。

假設(shè)m=k-l(k^3)時(shí)結(jié)論成立，即k-1個(gè)可數(shù)集的并集為可數(shù)集，記

為Do

則m=k時(shí)，可以構(gòu)造類似的雙射g:N-DUCk,所以為可數(shù)集。因而有

限個(gè)可數(shù)集的并集為可數(shù)集。所以AXB是可數(shù)集。

習(xí)題9.1

1.設(shè)G是一個(gè)(n,m)簡單圖。證明：mWC;，等號成立當(dāng)且僅當(dāng)G

是完全圖.

證明：由歐拉定理，2m=￡火外，d(k)表示第k個(gè)結(jié)點(diǎn)的度

左=1

因?yàn)?是簡單圖，所以d(k)Wn-l,等號成立當(dāng)且僅當(dāng)G是完全圖

%(k)?

2m=IW,

k=\

所以2mWn(nT)

即mW-2-

3、解：(1)不是圖的序列，因?yàn)槠鏀?shù)度結(jié)點(diǎn)的

個(gè)數(shù)不是偶數(shù)。

(2)、(3)、(4)都是圖的序列。

4、證：由歐拉定理，2m=Xd(v)

veG

???2b《Xd(v)<ZA

VGGVGGVGG

.,.nb4^d(v)=2m<nA

VGG

q/2m

no<——<A

n

9.若，稱G是自補(bǔ)圖。確定一個(gè)圖為自補(bǔ)圖的最低條件；畫出一個(gè)

自補(bǔ)圖來。

解：設(shè)G=(n,m),G'=(n,m')

則m+m,=n(n-1)/2,所以m=m'=n(n-l)/4

G

習(xí)題9.2

1、若u和v是圖中僅有的兩個(gè)奇度數(shù)結(jié)點(diǎn)，證明u和v必是連通的。

證：(反證法)設(shè)v與u不連通

/.G={V1,V2},v與u分別屬于VI,V2二個(gè)子圖

???v與u是G中僅有的二個(gè)奇數(shù)度結(jié)點(diǎn)

Av與u即是VI與V2中僅有的一個(gè)奇數(shù)度結(jié)點(diǎn)，與歐拉定理的

推論(9-1.1.1相矛盾,故v與u必連通

3、設(shè)(n,m)簡單圖G滿足m>(nT)(n-2)/2,證明G必是連通圖。構(gòu)

造一個(gè)m=(n-l)(n-2)/2的非連通簡單圖。

(書上證明更好)

5、設(shè)G=(V,E)是點(diǎn)度均為偶數(shù)的連通圖。證明：對任何v￡V,3(G-v)

Wd(v)/2

證：(反證法)設(shè)結(jié)論不成立，即存在：v￡V,3(G-v)>d(v)/2.

因?yàn)镚是連通的，所以G-v的每個(gè)分支都至少有一個(gè)點(diǎn)與v相鄰接,

而且存在一個(gè)分支，其與v相鄰接的點(diǎn)只有一條邊與v相連(因?yàn)槿?/p>

VVGV,3dXG-v)<^J(v)

每個(gè)分支中有二個(gè)以上的點(diǎn)與V相連，則|,

出現(xiàn)矛盾)

??.存在一個(gè)分支，其中只有一條邊與V相連；因?yàn)镚中每個(gè)結(jié)點(diǎn)的度

數(shù)為偶數(shù)，所以在這個(gè)分支中就會出現(xiàn)一個(gè)奇度數(shù)結(jié)點(diǎn)，其余結(jié)點(diǎn)的

度數(shù)全為偶數(shù)，與歐拉定理的推論相矛盾，故故對任何v￡V,3(G-v)

Wd(v)/2

9.證明：恰有兩個(gè)非割點(diǎn)的簡單連通圖必是Pn(n22)

證明：歸納法。

n=2時(shí)，結(jié)論顯然成立。

設(shè)n=k時(shí)結(jié)論成立，

當(dāng)11=1;+1時(shí)，設(shè)q、Vk是Pk上的兩個(gè)非割點(diǎn)，Vk+i是在Pk上增

加的一個(gè)割點(diǎn)，如果結(jié)點(diǎn)Vk“不在Pk上的任意兩個(gè)結(jié)點(diǎn)之間，則必與

Pk上某兩個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)回路，VkM就不是割點(diǎn)，與只有兩個(gè)非割點(diǎn)

矛盾。故結(jié)論成立。

習(xí)題9.3

3、解:

vlV2%乙%V6V]

0110000

0001000

0001100

A=

1010100

0000000

0000101

0000110

匕了2丫3%%羽6匕匕y2丫3%了5%V

11111001111000

11111001111000

11111001111000

PGPT=

11111001111000

00000000000100

00001110000011

00001110000011

三個(gè)強(qiáng)分圖G(WI#2#3#4})

G(伍))

G({%47))

eie2e3e4e5e6e7e8e9eMel\el2

11-1000000000

-100100000000

0-1001-1100000

001-1-11010000

000000-1-1-1-100

0000000010-11

0000000001-1

5.證明：支數(shù)為k,階數(shù)為n的無環(huán)圖G,其關(guān)聯(lián)矩陣的秩是n-k.

證明：將各支結(jié)點(diǎn)和邊集中編號后，G的關(guān)聯(lián)矩陣

/000、

oM00

M=2

00**

00o

由分塊矩陣子公式及定理9-3.2,

Y(M)=Y(Ml)+Y(M2)+-+Y(Mk)

二(n-1)+(n2-l)+…+(nk-l)

=n-k

習(xí)題10.1

1、設(shè)一個(gè)樹中度為k的結(jié)點(diǎn)數(shù)是nk,求它的葉的數(shù)目。

解：設(shè)L是葉的數(shù)目，m是樹的邊數(shù)，由Euler定理:

Ekn+L=2m

k=2k"

由樹的定義：

i

m=En+L—l

k=2k

=Zknk+L=2Enk+2￡-2

k=2k=2

^L=i(k-2)nk+2(i>k>2)

k=2

習(xí)題10.2

6、證明正則二叉樹必有奇數(shù)個(gè)結(jié)點(diǎn)。

證明：由正則二叉樹的定義，其葉結(jié)點(diǎn)的個(gè)數(shù)必為偶數(shù)，設(shè)葉數(shù)

為3分支數(shù)為i。

由定理10-2.1：(m-1)i-t-1

Vm=l/.i=t-l有分支點(diǎn)數(shù)是奇數(shù)

故結(jié)點(diǎn)數(shù)4+t=奇數(shù)

習(xí)題10.4

3、證：(反證法)

設(shè)6=(n,m)和G'=(n,m,)都是平面圖

由G的定義m+m,=n(nT)/2

由定理10-4.2m^3n-6,m'W3n-6

m+m,=n(nT)/2W6nT2

有n2-13n+24=(n-11)2+9n-97WO

又(n-ll)220,n211時(shí)，9n-9722

/.(n-ll)2+9n-9722

與上式相矛盾，故G與G'至少有一個(gè)是非平面圖

4、證明：具有6個(gè)結(jié)點(diǎn)，12條邊的簡單連通平面圖，它的面度都是

30

證：由Euler公式，n-m+f=2

A6-12+f=2f=8,即面數(shù)為8。

???對每個(gè)面，其度數(shù)23

總面度23X8=24

*.*總面度=2Xm=24

???每個(gè)面的度數(shù)為3

5、少于30條邊的簡單平面圖至少有一個(gè)頂點(diǎn)的度不大于4。

證：（反證法）設(shè)所有頂點(diǎn)的度數(shù)5

由Euler公式，

由定理10-4.2mW3n-6

3n-625n/2即n，12

則11125n/225X12/2=30與mV30矛盾

因此，至少存在一個(gè)頂點(diǎn)的度數(shù)不超過4。

習(xí)題10.6

2、證明：4k+1階的所有2k正則簡單圖都是哈密頓圖。

證：:G是2k正則圖,

:.對任意的u、vWG,d(u)+d(v)=4k

由定理10-6-2在G中存在一條Hamilton道路，設(shè)為：

V1V2,,,,,V4k+1

1)ViV4k+i￡E,貝V1V2,…，V4k+iVi構(gòu)成一個(gè)Hamilton圈

2)ViV4k+i任E,則明，匕2,…，公與匕鄰接

VG的階數(shù)為4k+l

必與匕…,“I中的一個(gè)點(diǎn)鄰接，

(否貝［|d(v4k+i)=4k-l-2k=2k-l與d(v4k+i)=2k矛盾)

設(shè)ui,V4k+1€，可構(gòu)造匕，…。-1，%?+1了4★，…，匕

即為G的一'個(gè)Hamilton圈，故G是一個(gè)Hamilton圖

5、設(shè)G是(n,m)簡單圖，若加C?-1+2，證明G必是哈

密頓圖。

證：(反證法)假設(shè)G不是哈密爾頓圖，則

*"eG,3deg(s)+deg(￡)<n

'：2m=Edeg(v)=Zdeg(v)4-deg(s)4-deg(Z)

veGveG-{s4}

2m<Edeg(v)+w

VGG-{S^}

因?yàn)镚除結(jié)點(diǎn)s,t外的其余n-2結(jié)點(diǎn)之間最多可以構(gòu)成完全

圖，所以2m<(n-2)(n-3)+n+n<n2-3n+6=(n-l)(n-2)+4

從而：[

m＜-(n-l)(n-2)+2=Ctl+2

與已知機(jī)？。3+2矛盾，故結(jié)論成立。

習(xí)題11.1:

4.設(shè)〈S,?＞是一個(gè)含有幺元e的代數(shù)系統(tǒng)，a￡S.如果存在元b,c￡S

使b?a=e(或a?c=e),則稱b是a的左逆元(或c是a的右逆元)。證

明：如果一個(gè)元既有左逆元b又有右逆元c,則必b=c.

證明：S上的運(yùn)算?是可結(jié)合的。

b=b,e=b?(a?c)=(b?a)?c=e,c=c

習(xí)題11.2

4、設(shè)半群＜A,?》中任何兩個(gè)不同元素關(guān)于運(yùn)算“?”不可交換，證明:

對任何a￡A,a,a=a

證明：(反證法)

設(shè)3a￡A,使得a?aWa,構(gòu)造b=a?a,貝！]

a?b=a?a?a=b,a

即a、b可交換，與已知條件相矛盾

VaGA,a,a=a

5.設(shè)S={00,in,1010}是字符集2={0,1}上的字集合。試構(gòu)造？*的一

個(gè)包含集合S的最小的含幺子半群。

解：令空字符為人.m,n,k為正整數(shù)，

T={X,(00)m,(111)；(1010)k}U{(00)m(lll)ndoio)k)

U{(00)m(1010)k(lll)n}u{(ll