离散习题答案冯伟森

1、习题参考解答习题一1、(1)设P:他是本片的编剧，Q:他是本片的导演。PAQ(2) 设P:银行利率很低，Q:股价上扬。P-Q(3) 设P:银行利率很低，Q:股价上升。(P-Q)(4) 设P:这个对象是占空间的，Q这个对象是有质量的，R:这个对象是不断变化的,S:这个对象称为物质。PAQAFS(5) 设P:他今天乘火车去了北京，Q他今天随旅行团去了九寨沟。PVQ(6) 设P：小张身体单薄，Q小张极少生病，R:小张头脑好使。PAQAR(7)设P这个人不识庐山真面目，Q这个人身在庐山中。P-Q(8)设P:两个三角形相似，Q两个三角形的对应角相等或者对应边成比例。P-Q(9)设P一个整数能被6整除，Q

2、这个整数能被2和3整除。P-Q设R一个整数能被3整除，S这个整数的个位数之和也能被3整除。R-S2、(1)命题T(2)命题T/F(3)不是命题，因为真值无法确定。(4)命题T(5)不是命题。(6)命题T(7)命题T/F(8)不是命题，是悖论。5、(1)证：(PAQV(PAQ)V(PAQ)<=>(PAQA(PAQ)V(PAQ)<=>(PVQ)A(PVQ)V(PAQ)<=>(PV(QVQ)V(PAQ)<=>(PV(PAQ)<=>P(3)证：P(QVR)<=>PV(QVR)<=>PVQVRVR<=>(PV

3、Q)V(RVR)<=>(PQ)V(iR)6、解：如果PVQ<=>VR,不能断定P<=>R因为当Q=T时，PVQ<=>VR恒成立。如果PAQ<=>AR,不能断定P<=>R因为当Q=F时，PAQv二>QR恒成立。如果P<=>R则P<=>R8把下列各式用f等价表示出来：(1)解：(PAQ)VPv=>(PfQ)f(PfQ)V(PfP)v=>(PfQ)f(PfQ)f(PfQ)f(PfQ)f(PfP)f(PfP)(1) 解：(P(QVF)APv=>(PV(QVR)Pv=>(PfP)

4、V(QV(RfR)A(PfP)v=>(PfP)V(QfQ)(RfR)A(PfP)v=>(PfP)V(PfP)f(QfQ)f(RfR)f(RfR)f(QfQ)f(RfR)A(PfP)v=>(PfP)f(PfP)f(QfQ)(RfR)f(RfR)f(QfQ)f(RfR)f(RfR)f(PfP)f(PfP)f(PfP)f(QfQ)f(RfR)f(RfR)f(QfQ)f(RfR)f(RfR)f(PfP)9、证：tPVQ<=>VQ<=>(P)tQPAQv二（PVQv=（PQ而,V,A是功能完备集，t是功能完备集，t不能互相表示，故，t是最小功能完备集。cc-也是

5、最小功能完备集=10、证：由书上的表可知，“”对应的真值表含2个1和2个0,而“”对应的真值表也含2个1和2个0，V对应的真值表含3个1和1个0，A对应的真值表含1个1和3个0,所以，“V”无法用“”和“”来表示，同样“A”也无法用“”和“”来表示，因此，不是功能完备集。10、解：（1）a）真值表法PQH5dARQAR->S(P->(QAR->S)0000Q110001011001001100110110100011010101101101010111111100001110010I1101001110110111100011110101111101001111111由表中可

6、以看出,i) 使公式(PT(QARtS)取值1时的解释所对应的全部极小项为:丨P/Q/R人S),(P/Q/R/S),P/Q/R/S),(P/VARAS),(P/Q/R八S),(P/Q/R八S),(PAQARAS),(QARAS),(-QAPA-RA-S),(-QAPA-RAS),(-QAPARA-S),(，APARAS),(-RAQAPA-S),(-RAQAPAS),(SAQARAP)，由定理1.8,主析取范划：(PAQ人R人S)V(P/QARAS)V(PAQAR人S)V(P/VARAS)V(-PAQA-RA-S)V(-PAQA-RAS)V(-PAQARA-S)V(QARAS)V(QAP/RA

7、S)V(Q八PAR/S)V(QAPAR人S)VAPARAS)V(-RAQAPAS)VHRAQAPAS)V(SAQARAP)°ii) 使公式(PT(QAR->S)取值0时的解释所对应的全部极大项为；PVQVrVs由定理1.7,其主合取范式为：PVQVRVScb)等价变换法Pt(Q/R)tS)OPV(Q/R)VS)u>p/qvrvS主合取范式o（PA（QVQ）A（RVR）A（SVS）V CQA（PVP）A（RVR）A（SVS）V （RA（PVP）A（QVQ）A（SVS）V （SA（PVP）A（QVQ）A（RVR）添加永真式o（P/Q/RAS）V（P/Q/R/S）V（P/QAR

8、AS）V （-PA-QARAS）V（PAQARAS）V（-PAQARAS）V（-PAQARA-S）V（-PAQARAS）V（Q/P/RAS）V（QAPARAS）V（QA!ARA-S）V（-QA-PARAS）V（Q八P/RAS）V（QAP/RAS）V（【APARA-S）V（QAPARAS）V（RAQAPAS）V（-RAQ/PAS）V（RAQAPAS）V（RAQAPAS）V（RAQAPAS）V（RAQAMS）V（-RAQAPAS）V（-RAQAPAS）V（S八QAR八P）V（S/QARAP）V（SA-QARA-P）V（SA-QARAP）V（SAQA-RA-P）V（SAQA-RAP）V （SAQAR

9、A-P）V（SAQARAP）合并相同的项o(P/Q/R/S)V(P/QAR/S)V(P/Q/R/S)V(P"QARAS)V(P/Q/R/S)V(PAQARAS)V(-PAQARAS)V(FAQARAS)V(QAPARAS)V(QAPARAS)V(QAPARAS)V(-QAPARAS)V(RAQAPAS)V(-RAQAPAS)V(SAQARAP)主析取范式(3)等价变换法PT(RA(QTP)oPV(RA(QVP)oPV(RAQ)V(RAP)oP/(QVQ)A(-RVR)V(RA-QA(PVP)V(RAPA(QVQ)oP八QAR)VPAQAR)V(PAQAR)V(-*P人QAR)V(RA

10、QAPV(RA-QAP)V(RAPAQ)V(R八P/Q)oP八QAR)V(PAQ人R)V(P/QAR)V(PAQAR)V(RAQAP)V(RAPAQ)主析取范式Pt(R人(Qtp)»pV(RZ(QVP)O(PVR)V(T)OPVRoPVRV(QAQ)PVRV-Q)PVRVQ)主合取范式13*解：(1) (PtQ)t(PAQ)(-PVQ)V(PAQ)«TAPVQ)-PVQGPIQ)A(QtP)=SOP)VQ)A(-QVP)w(PVQ)A(-QVP：oPv(Q/Q)oP不等价(2) (PtQ)A(PtR)o(PVQ)A(P/R)PV(QAR)P(QAR)PV(Q/R)等价14、

11、解：由题设A:A去，B:B去，C:C去，DD去则满足条件的选派应该是如下范式：(D)A(BAQA(CAD)构造和以上范式等价的主析取范式(AT(CVD)A(BAC)A(CAD)<=>(A/B/C/D)V(A/BAfIaD)/(AAB/CAD：V (AABCD)V(A人BAGlD)/(AABACAD)V AABA-CAD)V(AABA-CAD)共有八个极小项，但根据题意，需根据题意，需派出两人出差，所以，只有其中三项满足要求：(AABACAD),(AABACAD),(AABACAD)即有三种方案：A和C去或者A和D去或者B和D去。15、证：(1)由定理，需证(P-Q-(P-(PAQ)

12、为永真式t(P*(P*(PAQ)IR-PVQ)VPV(PAQ)(PVQ)V(-PVP)PVQ)Q(PVQ)V(-PVQ)wT人(p_Q)=(p_(FAQ)(3)由定理，需证PAPAFHS为永真式；PA*FARt5uFARt$uEt5o丁:.PMPAR=516、证：(1)性质1由定理和“”的定义，AA是永真式，所以A=>A(2) 性质2由定理，TA=>BB=>A二A-B和B-是永真式，即A-是永真式，由定理，A<=>B成立。(3) 性质3由定理，TA=>B二AB是永真式，又TA是永真式，根据“”的定义，E必是永真式。17、证：“二>”，TA=>E二

13、A-B是永真式，vA*Bu=T工心BnA“<=”因为上述等价式是可逆的，当B=>A必有A=>E18、解：设P:珍宝藏在东厢房Q藏宝的房子靠近池塘R：房子的前院栽有大柏树S:珍宝藏在还原正中地下T:后院栽有香樟树M珍宝藏在附近(后院)对语句符号化后得到以下蕴含式：QHP,FHP,QRVS,T-M=>?(Q*-P)ACR>P)AQA(RVS)ACT*M)<=>QA(Q一+P)A(R一P)A(RVS)A(T>M)=PA(RP)A(RVS)ACTM)<=>PA(P*R.)A(RVS)A(T*M)nRA(RVS)A(TM)SA(T*M)所以S为

14、真，即珍宝藏在花园正中地下。19、解：(1)不成立(P=0,Q=1(2) 不成立(P=1,Q=R=0(3) 不成立(P=0,Q=1(4) 不成立(P=0,Q=1,R=0(5) 不成立(P=1,Q=1,R=020、证：(1)利用CF规则 PP(附加前提规则) PVQP QT FHQP QHRTE23 RT P-RCP规则(2)利用CP规则 PP(附加前提规则) PVQTE3(PVQ(RAS)P RAST15 STE4 SVETE3SVE)tBP BTI5 BCP规则(4)(反证法)P(阳如前提规则)TEgPT巨FT殆T£TS)E3T山TE3TE3TSC1TgTGL5P p) P PR

15、R R-Q)A(R5) R-*Q Q R-*S SQtE)/X(S-B)心QtES-»B©E©BOEAB(EAB)OFIOO21、把下列句子防疫成逻辑形式，并给出证明。(1) 如果资方拒绝增加工资，那么罢工不会结束；除非罢工超过一年，并且资方撤换了经理；现在资方拒绝了增加工资，罢工刚开始，判断罢工能否停止。(2) 某公司发生了一起盗窃案，经仔细侦查，掌握了如下一些事实:被盗现场没留下任何痕迹； 失窃时，小花或者小英正在卡拉0K厅； 如果失窃时小胖正在附近，他就会习惯性的破门而入偷走东西后扬长而去; 如果小花正在卡拉0K厅唱歌，那么金刚是最大的嫌疑者； 如果失窃时小

16、胖不再附近，那么他的女友小英会和他一起外出旅游； 如果失窃时小英正在卡拉0K厅唱歌，那么瘦子是最大的嫌疑者根据以上事实，请通过演绎推理找出偷窃者。(2)P:无任何痕迹Q：矢窃时小花在0K厅失窃时，小英在0K厅S：失窃讨，小胖在附近T：金刚是临窃者M：瘦子是偷窃者命题可符号化为：P、QvRqS>尸，证：P ST-P SSRRQ7ROQTTQ>T41S7?>A/PP丁尸厂P厂P厂.金刚是窃贼。22、(1)不相容(2) 相容(P=1,R=Q=S=)(3) 不相容(4) 不相容23、(1)证：(QA(QVS)A(SQA(QAPO(PvV5)A('5vQ)八(Py八PLilJd

17、=/?v5<-5v-O,PyQ、p利用消解原理， PP -Pv-(7P-Q PvQPp、p=F P习题二1.解:(1)A(x):x是实数,B(x):x是有理数(Vx)(B(x)-*A(x)A-i(Vx)(A(x)fB(x)A(3x)(A(x)AB(x)(2) A(x):x是直线,F(x,y):x与y平行,G(x,y):x与y相交(Va)(Vb)(A(a)AA(b)-(F(a,b(a,b)(3) A(x):x是会员，B(x):x有意义，a:这个活动，F(x,v):x参加yB(a)-(Vx)(A(x)fF(x,a)或-j(Vx)(A(x)fF(x,a)-*-nB(a)(4) A(x):x是正

18、整数，B(x)：x是合数，C(x)：x是质数(Vx)(A(x)fB(x)VC(x)(5) A(x):x是存钱的人,F(x,y);x想有y,P：存钱没有利息,Q：人们不存钱,a:利息(Vx)(A(x)-F(x,a)A(P-Q)sdss亘点豈SS15二一)恳e(sAsbAlAsd皂Wif亠3STS三§丄E三gTf三wAsAlvsvsvs三磁.(zg邑Tl(svlMlTEls(z5=(匸三lrsd一sa三曲令3X蟲SA)亠SVWE一gs(s总二s£®w点owls痞s-ssdsg亘含破一ssd一ssutiIK督gssss二i)5. M：(1)A(x)!x=0»f

19、fx,y)=xy(VxXVy)A(f(Ky)_i*(Ak)vA(y)jA-A(x-1)Affx-bx+l)j可满建式(2) AW：x是诚实的人，实话，小林(Vx)(A5x'：rB(i)A7(喪)永假式(3) Ax):i不便宜，B(x):i是好货，a:小王买的衣股(Vi)A(x)AA(a)-B(a)永假式F(4) A(i):x是懂得人性本质的作SLBg注是真正的诗人上B：x能刘划人们内心世界D(i):x很高叭P(x,v；:y创作了y,a:移士比亚，b:哈姆雷特(Vx)(A(x)*D(xj)A(Hx)卜C(x)B(x)AP(a,b)A(Vx)(C(x)*A(x)AVx(卩鼠b)tB(幻)f

20、D(a)来真式6、(1)F,(2)A为F;B为T;C为T,E为F。7、(1)F,(2)T,(3)F,(4)T&解：个体域d实数集：p"y)：y=护；Q(my>09证：(1)(Vx)(Vy)P(x)>Q(y)o(Vx)(Vy)P(x)vQ(y)q(Vx)P(x)v(Vy)Q(y)(3x)P(x)V(Vy)Q(y)<=>(3x)P(x)>(Vy)Q(y)(3)(按定义证明)”S-(3y)(Vx)P(x,y)为真,则Gy)(Vx)P(x,y)为假，即对廿y,xeD,P(x,y)为艮P(x,y)为真所以(Vy)(3x)-P(x.y)为真：“u”设(Vy)

21、Qx)卜P(x,y)为真，即对VyGD,(衣)卜P(x,y)为真，因此对Vy,xGD,P(x,y)为假,即(3y)(Vx)P(x,y)为假,所以-(3y)(Vx)P(x,y)为真。FA)O(ZE)(AA)v3d(xA)0(za)o*(za)(ae)>sd(XA)VE(zasza)ae)T(x)d(XA)s丄愎曰aloMS(A)dV(x)d)(AA)(NA)Isd)?)v(x)d)QA)c(A)d(Am)>(3d)(xrn)(sd(AE)A(x)d(XA)o(sduE)Tsd(XA)(一)曲二(AX)Jvsd)(AA)(XA)(1A)0v(x)dj(ze(>)UA)012.ii

22、E：设G=Gx)(Vy)P(x,y)为永真式,则3cED,3(Vy)P(c,y)为永真式，af(x)；DtD；f(x)eDr即P(c,f(c)为真，由f(x)的任意性，Gx)P(xf(x)j为永真式。及(珂P卜f(x)为永真式，则3c6D,3P(c,f(c)为真，又由f(x)的任意也对VyWD,构造不同的f(x),3f(c)=y,BP(Vy)P(c,y)为真，(3x)(Vy)P(x,y)为永真式，13.if：(1)在斛孵下，Qx)帥)P(x)AQ(y)睚1，必有a,bED，mP(a)AQ(b)取1.3aGD,畀(a)般h；.(3x)P(x)M1,由定几筆含关緘立：i在斛孵下，M(3i)P(x)

23、AQigi1,|0|)P(x)AQ(a)|l(,分二种飙；i) (3x)P(x)=0,朋无论Q(a)为何if,(3x)P(x)tQ(a：般1.ii) Q(a)二0,(3x)P(x)=1,|(3x)P(x)->-Q(a)lt1,由叙，畫緘系成立。14.判别下面各式是否成立,并说明理由。(1) P(x)A(Vx)Q(x)=>(3x)lpWAQ(x)(2) Qx)P(x)->(yx)Q(x)=>(px)P(x)->Q(x)(3) (vx)P(x)Q(x)=>(3x)P(x)(vx)Q(x)解：(I)不成立，因为鞠訓左端不是帧(2)不成立,因为当Gx)P(x)=lj

24、xP(x)二1时，翹式的左制真值为1：T，ET，Ir51usT，IPT，1T，1U5丁OI16. lit:：2）反lit法） (*2(工)0(训 (卜(7&)tvg)(VxXP(x)aQ(x) r(.v)Aox) %) (w)尸(x) (vxjr(x)>(Vx)<?(A) g)Qx) )Oah)o口17、(1)错误，应换元，即 (V.v)P.v)>0(x) P(y)Q(x)正确(3)错误，a、b应是同一个常元(4)错诵.因为AP(x)vA72(a)中兀并不是自由出现错込國为在(3.y)P(aJ->g(.v冲*前件是命题，ifii后fl'不是命题(6) 错

25、误，因为3、b并不是同一个常童(7) 错误，和酚的顺序不兀应先使用ES.再使用LS18、(2)证：首先，将结论否定作为前提加入到原有前提中R(x)A(Kr)PU)A(3.v)y(.r)A(玉)(即仪(工“用(工)O(V.r)-r(.r)V(Va)-(P(a)v0(x)vJ!(jr)a(3w)P(w)a(Bv)g(v)G(V.r)(VhXVyX(F(x)'V/(x)a(P(x)v(9(a-)v(,x)尸仏)/xX仞)八卜宜W卜一X(vr)Q(V.rXVhXV.1L)(-P(.v)vZCy)a(尸0(x)vA(x)aP(a)/削占:|A(-左(ii刃/?(y)Ska1em范式了勺奨为卜PW

26、yR（小P(x)vQ(X)rRxP(a尺("Z?(h)vR(y)P(x)R(x)R（x），代换k/sj代换c/i/?(!)代换k/w）-7?(c)代换（c/y>习题二一6-尊待丄卩?寺二二卩豆二0二三二于&二亭a二邑口号(一)砖xm2AU2BJihmZAEMlnAlnAU常書lff呼An:評(2m62An2F負2A皿二2BuxlnAiaIrlBU爲AnB=>魚2言"-Tw迄二二1彥雷忑芳豐空了2严一产摯(一)芍S矇iT曹驴湃BgaHlom订一盒56.关系性质£r2r3r5自反性VVX反自反性X-XXJ对称性XJVJX反对称性J><X

27、J传递性JJJXJ10.(3："=>"R是对称的，设x,eR则”X/?=>IV)eRv<j,x>e/?_1.<x,j>e/?=><J,x>R,3|-R-'=R6<="RReR»ftl/?»的定乂，(y,x)eRgwK,即R是对称的。(5)“n”R是传递的，对V<x,z>G/e2ByeA9<>eR<j,z>e/?/.<>e7?即R?=R<=MR匸R,对V<.v,y>e/?<j,z>e/?,由R的定义，有

28、vx,d"匚R/.<x,z>eR,即R是可传递的o13.解:-./?=/；!U/?2，fl/?!A/?2=<I)R"nWA=AJA2.R；=IAiR号=S，需3|m,5=>m=15,即n=16/?16=/?6U7?l6=/?iU/?2故使Rm=Rn的最小正整数加=1，“15、解:00100100()00(100()、010000000MR=0000100000000100000000100000000100()010(1(LBQDIF.(3)证：/(JElrti归纳法可i正：对va*u尺“4)证：(證*=忌卡/?+Br(n)=厂z?Jj=iAG*=(

29、心)尸=f(心护由H纳法nJUE：V/GA+(/?)'-/(/?)»=2.G(Jt)y=fw)=心)=旷j=i/j/?O/?*=/?+'/?*=/4U/(/f)/?o/?*=/?o(zJu(尺)=R0fAU斤0/(>?)=/?LJ/?o#(/?)=才(a)=/?+习题五I.LIL:A：(6心亡jV*R=(«,b(gd)|adbc 口反f+.由A11勺kE义，ab=ba匕N二(“丄乂匕上)e艮 刘称性设(“")：(<7,刀)匚R、则ad=beLiIJc:b=da.(c?t/),(£jjZ?)c/? fL通件设(站i，方i)*(q

30、i"I)丘用，wd=ci（巧M1心）e；?,则ci2二Zqcidtl=byc2（J=b£?,c2=>ad=gj几（刍丄"（空歩心）隹R3. 解：v川=1,2,3.4,So=1,2,4,（3设Ax124,A2=3几R=（14）4b2）X1-4X2,1）/2-2）X2,4）,（44）,（4,2>,（44）X33）4、解：每个集合的划分就可以确定一个等价关系二集合有多少个划分就可以确定多少个等价关系不同的划分的个数为:=1+24-1+C;+1=15（4<41（4）b>不同的等价关系个数等于不同的划分个数，所以不同的等价关系个数为15. R叽K星A

31、上的等价关系 R7是A上的等价关系 riR-心)是A上的等价关系 Rg八是A上的等价关系9-解:A=cr9h9c<£u>10.解：翼含A上的空关实e、恒等关蔡匚都是争价关襄和假序关襄，13.证：i)口屁生.对VAGBAz(A.Z>)/?7?的自反性)显然(fr.A)(A,A)eii)反对称性对e/i(0“)eRQ()仙4)eRPUExHI(fi.b)GR.(h.u)GR,由R的反对称性，=0=/>11i)传选性对Vtf.ft.ceB设(a.h)?en(BxB),Qf.c/eri(BxB).>1!.(u.R(fr?c)«R由R的传谡性，(

32、1;.t)GR显然(GC)wBxEL5.解:A=Ia,6,cfc/IQ)"Gc)£N)M(a,b)M(a,i)M(a,")MIA,c)S|A.JIM(e9d)S(q上,S(cr,t,d三>,t.dJ5242)习题六1)对Vb、b2gB,bHb2.仙是满射，3aPa2eA,?f(ax)=hlf(a2)=h2由g(x)的定义，ajGgCbjXajeg(b2)>且ajCg(b2),a2gg(l否则，ajeg(b2),a2eg(bj),有f(al)=b2,f(a2)=b与函数的定义相矛盾，：g(b)护g(b2),即&何为单射2)而g(x)为单射时，对V

33、beB,并不能保证g(b)工0,f(x)不一定是满射1K解：设A=BiB-fis1）单射：（山11JC：；xnd2）满射：（m2nJ可以看成暮m个不同的球胶到m个盒子里，所以3)双射：nJ=n2!f:ATB;BTC(1) 反证法:设不是单射，3x学兀4肩f(x)=f(x2)即g。J|)=g(At)=g(fg)=go/(X2)与g。.伪单射矛盾(2) go/*满射；.对比GG3aj°/(x)=(/(x)=：4V(x)=yeB3yeB,3g(y)=z即g为满射习题十1、设G由(1)检结论可得个（n,m简单图。证明：匚-监，等号成立当且仅当G是完全图证眛先证强m<C阂为G是筒单用，所

34、以G的结点度上風m何也叮"丄G图肘总点度上限为max(S(d(v)<nmax(d(v»<rt|n-l)c根蠢程手定理卩G图边的匕限为max|m)<"*”1)/2.所以mWC右(2) m=Cj=!G是完全用因为G具有I:限边tL假设有结贞的点度小fnd,®么G的总度董就小于上限值,边蠶就小于上限化与条件矛鼠硕G的毎个第点豹点度都为nG为完全用，G是完全用=)m=Cq因为G是完全此折以每个弟点的点度为nJ总度数为n|n4r瞬担手足理，图G的边数m皿.2、设G是一个(n,n+1)的无向图，证明G中存在顶点u,d(u)>3。证明：反证法，

35、假设巾EGt(d(u<2),则g的总点度上限为max(刀(d(u)<2n,根据握手定理，图边的上限为max(m)<2n/2=n。与题设m=n+1矛盾，因此，G中存在顶点u,d(u)>3。3、确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来：(1) (320,1,5);(2)(6,3,3,2,2)(3) (4,4,2,2,4);(4)(7,6,8,3,9,5)解：除序列(1)不是图序列外，其余的都是图序列。因为在(1)中，总和为奇数，不满足图总度数为偶数的握手定理。可以按如下方法构造满足要求的图：序列中每个数字ai对应一个点，如果序列数字是偶数，那么就在对

36、应的点上画ai/2个环，如果序列式奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以(2)为例说明：(6,3,3,2,2)对应图G的点集合帖g乃月刑4吐v2每个节点对应的环数(6/2,(3-1)/2,(3-1)/2,2/2,2/2)(3,1,1,1,1)将奇数3,3对应的节点V2,V3一组，画一条连线其他序列可以类似作图，当然大家也可以画图其他不同的图形。4、证明：在(n,m)图中2m/n<o证明：图的点度数是一组非负整数d(v1),d(v2)d(vn)，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的

37、术语及为：最大值为,最小值为3,平均值=(d(v1)+d(v2)+d(vn)/n=2m/n，所以2m/n<o5、证明定理。(U)+_(LI)=2III,ll十(L1)<L_(tl)=IIIu&VueVueV【定理】对于任何(n,m有向图G=(V,E),ueV证明：有向图中，每条有向边为图贡献一度出度，同时贡献一度入度，所以总出度和入度相等，并和边数相等。因此，上述关系等式成立。6我G是(乩用)箱单二部酊证明：m'4训本翻，帅只需要说明fl阶的简单二紳的翊帕尢值J即可。Aan阶脯単二部豁其两部分触集合分别为VI.吃那么|Vi|+|V2|=n,此种飙当G为完全二部图时有

38、量多的边亂即max(m)=|V1|V2|(7j-max(m=(n-|V2|)|此大It及为n阶二部图的边的上限值,其上限值为当|V2|=n/2S®(|cmax(max|m|)=丄尸以n阶二部用hm),m£匕447、无向图G有21条边，12个3度数结点，其余结点的度数均为2,求G的阶数n。解：根据握手定理有：21=(3X12+2(n-12)/2，解次方程得n=15。10、判断图中的两个图是否同构，并说明理由。解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯的3度点只有1个1度点为其邻接点。因此这两个图不可能同构。13、设有向图D=如下图所示(1)在

39、图中找出所有长度分别为123,4的(至少用一种表示法写出它们，并以子图形式画出它们。)(2) 在图中找出所有长度分别为3,4,5,6的回路，并以子图形式画出它们。解:(1)C=AeiBegCe5AC=AeiBe7Ce6DezAC=ADA兀的AC-Ae4Be3Ce6De2A2)子图略长度为三的回AeiAeiAeiA,AeiAegDesA,AetBeTCesA,AeiBesCesA长度为四的回路:AAAAA,AUDA,AABe7CA,AABeeCA,ABemABcaCDA长反为五的回跻：AAAAAAtAAAADA,AAABezCA.AAABesCA,AABe<DA,AABe.CDAADADA

40、,AAAeBe-CesA,AAAejBejCe：A(ADAoiB(?；Ce：A;ADAe.：Be；Ce=AB15、若u和v是图G中仅有的两个奇度节点，证明u和v必是连通的。证明：反证法，假设u和v不连通，那么它们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度节点。根据握手定理，一个图中奇度点的个数为偶数。而两个连通分支中，奇度点的个数为奇数。矛盾。矛盾的产生是由于假设不连通导致的，因此,题设结论成立。!?.S(n,单用G猜足m>-l)(u-2),证丙G必是连通紀!(n-l)(n-2)加非连i|肓单雲I证叭假妣不连通辛分支GhG2Gk,那么他伽般的最大值(m)=S

41、-1)n|/2<Z(n3-1)(n-1)/2=(n-1)/2X(r.-1)=(B(n-k)/2t只有3k=lH，才能觎戢要求，G是连逋馭如梆恥合分成两个点集，和儿V2|卄1也成如下的有两个分支帥連通解图山口1,(|G2=KrH扁牋设条件18、设G施阶数不小于3的连通图。证明下面四条命题相互等价：(1) G无割边；(2) G中任何两个结点位于同一回路中；(3) G中任何一结点和任何一边都位于同一回路中；(4) G中任何两边都在痛一回路中。证明：(1)=>(2)因为G连通，且G无割边，所以任意两个结点u，v,都存在简单道路p=u.wv。又因为G无割边，所以，删除边wv后，子图依然连通，

42、即w,v存在简单道路p'，以此类推，可以找到一个核p每条边都不相同的p''=v.u，这样p和p''就构成了一条回路。证明：(2)=>(3)因为G中任意两个结点都位于同一回路中，所以任意结点u和任意边e的两个端点v1,v2都分别在两个回路C1,C2中，如果C1-C2二u.v1.v2.u，那么将回路中v1.v2，用v1v2=e替换，就得到新的回路，并满足要求。如果C1mC2C1=u.v1.u,C2=u.v2.u，那么构成新的道路P=u.v1u.v2.u，在其中将重复边剔除，得到新的回路C3,其中包含v1,v2结点，可以讲回路中v1.v2用v1v2=e替

43、换，就得到新的回路，并满足要求。证明：（3）=（4）对任意两条边e1,e2其端点分别为u1,u2,v1,v2.根据（3）存在回路8=u1.v1v2u1,C2=u2v1v1.u2.那么可以形成新的闭道路P二u1.v1v2.u2v1v2u1，在其中将重复边剔除，得到新的回路C3,其中包含e2和u1,u2结点，可以将回路中u1.u2用u1u2二el替换，就得到新的回路，包含e1,e2,满足要求。证明：（4）=（1）因为任意两条吧都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不连通，分支中的任何一对不再同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边。19.G=（V,E）是

44、点度均为偶数的连通图切证明：对任何vGV（G-v）gld（v）0证明：Gr最多产生dw）个奇数度点，又因为每个连適分支中奇数度点的个数是G-v的连通分支最少有两条边和¥相连，所以总连通分支数小于等于d（v）/2i21.证明：在非平凡连逋圏G中丄为割边的充要条件是它不包含于G的任何圈中证明：1）£为割边不包含于G的任何圈中假设e包含在某一匮Ci中，那么删除此边，但边关联的两个第接点依然以没有破坏原图的连逍性j因此不是割边，矛盾，所以愷设不成立.既厂不包含何圈中：2）e不包含于G的任何圈中“£为割边像设芒为割边，那么删除此边，兰成子便依然连Mo关联的两个邻接点路存在此

45、基本道路连同“构成一个圈与题讪护盾所以假设不成立，旺芝为¥根据1）,2）可知，题设结论成立23、证明：在具有n（n2）个结点的简单无向图G中，至少有两个结点的度数相同。证明：此题可用鸽巢原理，因为n个结点的简单无向图G中，结点的度数只可能是0,1,2.n-1这n个数，又因为如果有结点的度数为0，那么就不可能有结点的度为n-1，反之亦然。所以n个结点，最多有n-1中度数，其中必有至少2个结点的度数相同。24、设G是5>2的简单图。证明：G中必有长度至少为5+1的图。证明：设p=uv是满足题设要求图G中的最长基本道路，那么d(u),d(v)都应该大于等于5。那么u,v的邻接点都应该

46、在道路p上，否则此道路可以延长，与其是最长路假设矛盾。如果u,v是邻接点，那么可以构成一个圈c=uvu，其长度5+1.如果u,v不是邻接点，那么从p的终点开始删除点，知道其为u的邻接点为止，得到道路p',可知道路p'，依然保持u的所有邻接点都在p'上的性质，所以可构成一个圈c'=u.uu,其长度5+1，证毕。25、证明：G是单向连通图当且仅当存在一条包含G中全部结点的有向道路。证明：假设不存在包含全部结点的有向道路，那么设p=v1v2.v,k是G中最长的有向道路，且u结点不包含在此有向道路中。u和此道路中任何中间结点都不可能双向可达，且u不能到达V1，且vk也不

47、能到达u,否则，此最长路克扩充。那么忧郁道路上的每个结点和u都单向可达,所以此最长路和u之间的可达关系必然如下图所示：2k为偶数k为奇数当k为偶数时，道路克扩充为儿，而当k为奇数时，不管'匚与u之间是如火热单向可达的，都可以构造出更长的有向道路，矛盾，所以G中一定存在包含所有结点的有向道路。26、解：标注如下所示:u4u5,u7u8,u8u9。根据标记后的图，可求得割点分别为：u4,u7,u8,割边分别为:27、求图的全部强分图和单向分图。解：标图重新标记如下:010000D000010000001000010000000001那么此图的邻接矩并为A=011000000通过计盲0001

48、100010001000100000(11001to00000000_T11111110111111110111111110111111110分图矩阵为，Q=11111111011111111111111110111111110000000(101因此，此图有两个强分图，一个包含一个结点v9,个包含其他的8个结点。由于两个强分图之间存在有向道路，因此全部9个结点，构成了单向分图。28、证明：一个联通无向简单图中，任意两条边最长路至少有一个公共顶点。证明：假设两条最长路p仁v1v2vk,p2二u1u2uk没有公共点，那么链条道路上的点集之间就有道路相连，否则就不是连通图了。设此道路起点是pl上m点，终点是p2上w点，可根据如下情况进行调论：（1）m,w是p1,p2的中间结点，那么可构成新道路p=v1v2.m.w.uk，此路至少比pl长1,矛盾。（2）假设m和w不能均分p1,p1，那么可以将两个长路段和m,w之间的道路进行拼接，那么可得到比pl长的道路，与p1,p2是最长路矛盾。因此任意两条最长路至少有一个公共点。29、证明：若G是n阶无向简单图，G中每一对不相邻的顶点的度数之和至少是n-1,则G是连通图。证明：假设G不是连通图，G1,G2是G的两个连通分支，分别为n1,n2阶连通无向简单子图，则n1+n2wn。对G1中任