离散习题答案-冯伟森

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

2、整除，Q这个整数能被2和3整除。P-Q设R: 一个整数能被3整除，S:这个整数的个位数之和也能被 3整除。RHS2、 ( 1)命题 T 2 )命题 T/F 3 )不是命题，因为真值无法确定。 4 )命题T 5 )不是命题。 6 )命题T 7 )命题T/F 8 )不是命题，是悖论。 、(1)证：(PA Q V (PA Q) V (PA Q) ( (PA Q A (PA Q) V (PA Q (PV Q A (PV Q) V (PA Q (PV (QV Q) V (PA Q (PV (PA Q P(3)证：P (QV R)PV (QVR)PV QV RV R (PV Q V (RV R) (6Q)

3、 V ( PR)6、 解：如果PV QQ/ R,不能断定PR因为当Q=T寸，PV Q& R恒成立。如果PA Q0 R,不能断定PR因为当Q=F时，PA Q0 R恒成立。如果 PR 则 PR8、把下列各式用T等价表示出来：(1)解：(PA Q VP (PT Q T ( P TQ) V (PT P)(PT Q) T ( PTQ) T (PT Q T (PT Q) T (PT P) T (PT P)(1)解：(6 ( QV R)A -P (PV ( QV R) -P (PT P) V (QV (RT R) A (PT P) (PT P) V ( (QT Q) (RT R) A (PT P)(PT P

4、) V (PT P) T (QT Q T (RT R) T ( RT R) T (QT Q T (RT R) a (PT P)(PT P) T (PT P) T (QT Q) (RT R) T (RT R) T (QT Q T (RT R) T (RT R)T (PT P) T (PT P)T (PT P) T (QT Q T (RT R) T (RT R) T (QT Q T(RT R) T (RT R) T ( PT P)9、 证： PV QPyQ(P) -QPA Q( PV Q (6 Q而，V, A是功能完备集，, 7是功能完备集，,一不能互相表示，故 , 7是最小功能完备集。cCT也是

5、最小功能完备集c10、证：由书上的表1.16可知，“ ”对应的真值表含2个1和2个0,而对应的 真值表也含2个1和2个0, V对应的真值表含3个1和1个0,人对应的真值表含1个1和 3个0,所以，“V”无法用“ ”和来表示，同1“A”也无法用“ ”和来表 不，因此， , 不是功能完备集。10、解：（1） a）真值表法PQR5Q/ RQA RtS(P- ( Q 八 RfS)0000Q110001011001001100110110100011010101101101010111111100001110010I1101001110110111100011110101111101001111111由

6、表中可以看出,i)使公式(PT (QARtS)取值1时的解释所对应的全部极小项为:(PAQAR八S),(P八Q八RAS),(PAQARAS),(P/V ARAS) , (-PAQA-RA-S),(PAQARAS),(P八QAR/VS),( QARAS) , (-QAPA-RA-S) , (-QAPA-RAS) , (-QAPARA-S), APARAS),(RAQAP八S),(RAQAPAS), (SAQ八RAP),由定理 18 主析取限为:(PAQAR八S) V (P/Q八RAS) V (P八QAR八S) V (P/V ARAS) V (PAQ八R八S) V (-PAQA-RAS) V (-

7、PAQARA-S) V ( QARAS) V (QAP/W/W) V (QAPARAS) V (QAMR八S) V APARAS) V (RAQAP八S) V HRAQAPAS) V (SAQARAP) .ii)使公式(P4 (QAR-S)取值0时的解释所对应的全部极大项为:PVQVRVS由定理1.7,其主合取范式为:PVQVRVSc b)等价变换法P(QAR)-S)o PV(QAR) VS)opVQVRV S主合取范式o (PA (QVQ) A (RVR) A (SVS)V (QA (PVP) A (RVR) A (SVS)V (RA (PVP) A (QVQ) A (-SVS)V (SA

8、(PVP) A (QVQ) A (RVR)添加永真式o (P/QAR八S) V (PAQA-RAS) V (PAQ/R八S)V (PAQARAS) V (PAQ八RAS) V (PAQ八RAS) V (PAQ八RA S) V (-PAQARAS) V (QA PARAS) V (Q 八PARAS) V (QA7 AR 八S) V (QATARAS)V (QA P八RA S) V (QAPARAS) V ( APARA-S) V (-QAPARAS) V (R八Q八P 八S) V (RA Q八PA S) V (RAQAPAS) V (RAQAPAS) V (R八Q八PAS) V (RAQ八PA

9、S) V (RAQAP八S) V (-RAQAPAS) V (S八QARAP) V (S/QAR AP) V (SAQARAP) V (SA-QARAP) V (SAQA-RA-P) V (SAQA-RAP) V (SAQARA -P) V (SAQARAP) 合并相同的项=(PAQ/RAS) V (P八QARAS) V (P八-QARAS) V (P/- QARAS) V (P八Q八RA-S) V (PAQARAS) V (-PAQARA-S) V (7 AQARAS) V (QAP 八R 八S) V (QA PA R A S) V (QAPAR八S) V (八 QAPARAS) V (RA

10、QAPA S) V ( -RAQAPAS) V (SAQARAP)主折范式(3)等价变换法P - (R A (Q - P) oP V (R 八( Q V P) o P V (R AQ) V (R A P)o (P A (Q V Q) A (-R V R) V (R A Q A (P V P) V(R A P A (Q V Q)o P A Q A R) V P A Q A R) V ( P A Q A R) V ( P A Q A R) V (R A Q A P)V(RAQAP)V(RAPA-Q)V(RAPAQ)o ( P A Q A R) V ( P A Q A R) V P A Q A R)

11、 V P A Q A R) V (R A Q A P)V(RAPAQ)主析取范式P t (R A (Q t P) P V (R A (Q V P)o ( P V R) V (T) O P V Ro P V R V (Q A Q)( PY RVQ) A PVRVQ)主合取范式13* 解：(1) (P 一 Q) (PA Q) Q ( PV Q) V (P A Q) T A ( P V Q)白 P V Q( P - Q)八(Q - P)(P) V Q) A Q V P) 0 (P V Q) A Q V P： oPv(Q/Q)oP 不等价(2) (P T Q) A (P T R) o ( p VQ)

12、A PV R)P V (Q A R)P T (Q AR) Pv (Q AR)等价14、 解：由题设 A: A去，B: B去，C: C去，D D去则满足条件的选派应该是如下范式：(A- (CV D) A (BA Q A - (CA D)构造和以上范式等价的主析取范式(A T (CVD)A (B AC)A- (CAD) (AA E/ CAD)V(AABACAD)V( AABaC d：V A A B A C A D) V (A A BAG A D) V (A A B A CAD)V ( A A B A C A D) V (A A B A C A D)共有八个极小项，但根据题意，需根据题意，需派出两人

13、出差，所以，只有其中三项满足 要求：(AA BA CA D), (AA BA CA D), (AA BA CA D)即有三种方案：A和C去或者A和D去或者B和D去15、证：(1)由定理1.11 ,需证(Q - ( A ( PAQ)为永真式；(P Q) (P (P 八 Q)Io (P V Q) V P V (P 八 Q)(PVQ)V (PvP)/( P V Q)(P V Q) V (- P V Q) w T，(p - Q) = (p - (p 八 Q)(3)由定理1.11 ,需证PA-PARS为永真式1- PAPARiSoFARtSdFtSoT:.papar = s16、证：(1)性质1由定理1

14、.11和的定义，A-A是永真式，所以A=A(2)性质2由定理1.11 , A=B B=A AB和Bf是永真式，即人是永真式，由定理1.3, Av=B成立。(3)性质3由定理1.11 , VA=.AB是永真式，又 A是永真式，根据”的定 义，B必是永真式。17、 证：“二”，A=B是永真式，t A B Q A vB B)VAo B *A o T2 B = A“v二”因为上述等价式是可逆的，当B=A必有A=B18、解：设P:珍宝藏在东厢房Q藏宝的房子靠近池塘R：房子的前院栽有大柏树S:珍宝藏在还原正中地下T:后院栽有香樟树M珍宝藏在附近(后院)对语句符号化后得到以下蕴含式：CHP, R- P, Q

15、 RV S, T- M=?(Q P)八(R P) A Q A (R V S) A CT * M)0 Q A (Q 一P) A (R 一 P) A (R V S) A (T M )一P A (R 一 P) A (R V S) A CT M) P A ( P * R.) A (R V SJ A (T * M )R 八(RVS)八(T 一 M)S A (T * M)所以S为真，即珍宝藏在花园正中地下。19、 解：(1)不成立(P=0, Q=D(2)不成立(P=1, Q=R=0(3)不成立(P=0, Q=D(4)不成立(P=0, Q=1, R=0(5)不成立(P=1, Q=1, R=020、证：(1)

16、利用C项则P P (附加前提规则)PV Q PQ T FH -Q PCH-R T E23R TR CP规则(2)利用CP规则PP （附加前提规则）PVQTE3（PVQ （ RAS） PRAST15STE4SVETE3（SVE） 7 BPBT156BCP规则（4）（反证法）P （附加前提规贝日）TE3PT【5PT小T5T%T15T E3T E3T SC 1TI5T QEgP P） P P 一 R RR t Q）八（R t S） R - Q Q品.R S S（Q t E） A （S - B）Q Q t Ee s - bQ E BQ E A B（E八B）OFI O O21、把下列句子防疫成逻辑形式，

17、并给出证明。(1)如果资方拒绝增加工资，那么罢工不会结束；除非罢工超过一年，并且资方撤换了经理；现在资方拒绝了增加工资，罢工刚开始，判断罢工能否停止。(2)某公司发生了一起盗窃案，经仔细侦查，掌握了如下一些事实：被盗现场没留下任何痕迹；失窃时，小花或者小英正在卡拉 OW;如果失窃时小胖正在附近，他就会习惯性的破门而入偷走东西后扬长而去;如果小花正在卡拉OW唱歌，那么金刚是最大的嫌疑者；如果失窃时小胖不再附近，那么他的女友小英会和他一起外出旅游；如果失窃时小英正在卡拉 OW唱歌，那么瘦子是最大的嫌疑者 根据以上事实，请通过演绎推理找出偷窃者。(2) P:无任何痕迹失密时,小花在0K厅R：失窃时，

18、小英在0K厅S：失窃时，小胖在附近T：金刚是偷功者M：瘦子是偷窃者命题可符号化为: P* Q v R, S 尸.证：PS 一PISS RRQ7 RQQfTT二金刚是窃贼口22、（1）不相容Q T, 15i/tq 7? A/ PP丁PTPP厂相容(P=1, R=Q=S= 0(3)不相容(4)不相容 23、(1)证：(Q A (QV S) A (S- Q A ( Q A Po (Pv Q)A(R v S)八(Sv - Q)八(PvQ)八 Pl J = Pv Q, /? v S.Pvg, p利用消解原理; PP PvQP Q/v。P 5 尸八P=户口 习题二(1) ：A(x):x是实数，B(x):x

19、是有理数(Vx) (B(x)-A(x) A-i (Vx) (A(x)-B(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 ) A A (b ) - (F( a , b ( a , b )(3) A(x):x是会员，B(x):x有意义,a ：这个活动，F(x, y):x参加yB( a )-* (Vx) (A(x)-*F(x, a )或 Wx) (A(x)f F(x, a ) a )(4) A(x):x是正整数，B(x)： x是合数，C(x)： x是质数(Vx) (A(x)-B

20、 (x)VC (x)(5) A(x):x是存钱的人,F(x, y);x想有y,P：存钱没有利息，Q：人们不存钱,a:利息 (Vx) (A(x)-F(x, a) A (P-Q)2,(DP(O)AP(1)AP(2)A(R(O)VR(1)VR(2)P(0)Q(0)AP(1)4Q(1)aP(2)Q(2)(2) (-P(O)AP(1)A-P(2)V(Q(O)VQ(1)VQ(2)3.常睫毓频骁自般储螭雕P(x).(2) dW匆文势单支元;第一个他)的储域对P(x)AQ(x)卜纪个他触雕P(x(3)册是为4变元又是(由变元；机笼匆天变元;(*)(加城那(xj)AQ(川(血懈雕敞。4. M： (1) (Vx)

21、(3y)P(x,y) - Q(y,t)V(Yz)R(x,y,z)(2j (Vx)P(x)R(x) V Q(y) A (3x)R(x) (3z)S(t,z)5. M： ( 1) A(x)： x = 0, y)(Vx)(Vy) A(Ki y)J -*(A(x) V A(y) A- A(x - 1) A ffx - b x+ l)j可满足式(2) A：工是诚实的人，B(x);x讲实话,a；小林(Vx) ( A5x： f R )A E量？ 永假式(3) AG)：工不便宜，B(x):工是好货，a 士小王买的衣眼(Vi) 8(i)一白)A R ( 2 ) f B ( a )水假式F(4) A(：x是懂得人

22、性本质的作家泮:，是真正的诗人,C次能刻划人们内心世界,D(i) ： x很高明,PG-；： *创作了? a ：莎士比亚,b ：哈姆雷特 (Vx)(A(x) * D(xj) A (胃)( C(x) B(x) A P(a, b) A (Vx)(C(x) * A(x)A Vx(P(x, b) t B(x) t D(a)永真式6、(1) F, (2) A为 F; B为 T; C为 T, E为 F。7、(1) F, (2) T, (3) F, (4) T8、解：个体域D实数集：p(x，y)： y = e Q(y),v)。9,证:(1)(Vx)(Vy)P(x) Q(y)=(Vx)(Vy) P(x) V Q

23、(y)=(Vx)P(x) V (Vy)Q(y)(3x)P(x) V (Vy)Q(y)Q (Ex)P(x) 一 (Vy)Q(y)(3)(按定义证明)“=设 Gy)(Vx)P(x, y)为真，则6y)(Vx)P(x, y)为假，即对Vy, x W D, P(x, y)为假,P(x, y)为真,所以(Vy)Gx)卜 P(x，y)为真:设(Vy)Gx)卜 P(x, y)为真，即对VyED.(执)卜 P(x, y)为真，因此对Vy, xE D, P(x, y)为锻，即Gy)(Vx)P(x, y)为假，所以 By)(Vx)P(x, y)为真。11.解；(x)P(x)t Qy)P(y)= (Vx)P(x)

24、V (3y)P(y)Q (国乂 P(x) vGy)P(y)o (Vx)(P(x) A(Vy)( P(y)(Vx)(Vy)(P(x) A- P(y)skolem 范式(2) - (Vx)P(x) t (3y)(Vz)Q(y,明 (Vx)P(x) V (3y)(Vz)Q(y, z)j(Vx)P(x) A (Vy)Gz) Q(y, z)=(Vx)(Vy)Gz) (、P(x) A Q(y. z)(Vx)(Vy)(P(x) A Q (y, f(x, y)skolem 范式12证：=”设G = 0x)(Vy)P(x, y)为水真式，舶cED, 3 y)P(c, y)为水真露又f(x)； D-D,f(x)E

25、D,即 P(c, f(c)为真，由 f(x)的任意性，(3x)P(x, f(x)j 为水飘。“=”设(h)P(x, f(x)为永真式，则在ED, ”(c, f(c)为真，又由f(x)的任意性, 对VywD,构造不同的 f(x), 3 f(c) = y,即Wy)P(c, y)为真,(现叩什卜，y)为永真式。13.证：粽情嘴面的帆)N(y)jm嫡a, b&D,非(a)AQ(哪I) 0t. 3a6D, 3P(a)取信(3x)P(x)M1,由定义，窠含关系睚，(2)酶髀&硼(x)AQ斛馆 1? |01)P(x)AQ(a)|l1,分二种特拈i)(3x)P(x) = 0,财无饱Q(a)和if, Gx)P(

26、x) t Q(魏隹 1,II) Q(a) = 0, (3x)P(x) = L 则闽P(x)tQ(M，由定义,豁关系成立,14.判别下面氢是否成立，并说明理由。(1) P(x)A(Vx)Q(x)=(3x)lpWAQ(x)(2) (bx)P(x)-( yx)Q(x) =(yx)P(x)-Q(x)(3) (vx)P(x)Q(x)= (3x)P(x)(vx)Q(x)解：不成立,因为翻趟左瑞不是命题(2)不成立，因为当(*)P(x)=l, VxP(x)=l相第防弋的左喘的真值为1;T，ET，IT，ICS0 1M；P 1TJUSTO I16.证！： 2）反证法）色小-0(x)1(VxXp() t Q(x

27、卜蝴(P(x)f /Q(Vx X 尸(x )a Q(x)尸(X)八0(a )内*)(Mr)尸J)(Vxj/J(x) T (Vx)f?(A )(Vx) Qx0G)O 6(A-) 口17、(1)错误，应换元，即(V.Y)P.V)尸(、)T Q(x)正确(3)错误，a、b应是同一个常元（4）错误，因为在户（x）v（3x）0G）八AQR中*并不是H由出现 错误，因为在（3x）P（x） 以丫）中,前件是命题,而后件不是命题（6）错误.因为a、b并不是同一个常量（7）错误，和的顺序不，：_应先使用ES,再使用LS18、（2）证：首先，将结论否定作为前提加入到原有前提中f(3x)P(x)Q(x) 7?(x)

28、 a(Hx)F(.t)a(3x)0(x)a(玉X%XMD八仪)。(V.r ) - P(a ) v(V.v卜(P(_v)7 0& ) v R(x i| a)?() a旧hX寺Rh 人衣(y)0(v.r)(vh XVyX( 尸(工)m /(x)a( P(工卜Q(k)m M*)aP(w)a 7?(m)a( J?(w)v *o (v.rXvHX)( P(a:)v &%)八(尸0(*)* /i(x)A Pa) a。怙)人(一 (”+卜/?(y)Skcs 1 em 范式子句奥为卜 P(.r)v 尺(今- P(.r)v pU)v R(x P(a R(h),砍口卜一7?。)工尸(#卜代(*)火，代换氏匕)代换

29、”工/?(疗)v/?(r) 一冗3)，代换a”秋白)代换My二习题三16 .解：2A =0,町a, b,检 a,., (a. (b).他 a, bJ17 .证：贵 XE2&U2B,则 xE2&或 xE2 ：.x A或 x匚 B,明 xMUE, Ix6 2AljB,等号成立撼牌；AAB = 05(2) - = x62An2B=x62Aix62B=xcAKxB=xcAnB= x 2 吸“hWx2吗由于上树程是可逆机所以比2。2%18.#： (1)由于是求包仙奸斛教，轴上睚在去轴以雕下的个元和 分别取1个C个、一个元素舸四合逾司 牖第族巴什YC：二* 如也好a、b的子集个改为%z + C +&2+

30、” + %111； n 利卜,y)EAxxE V，：AB, ：xmj. yjeBxC, AxCBxCdu 1 C?0, ： AxC;O( BxCi J, ViAf VyEC, (x, y) A x CtJv AxCcBxC 1 (x, y)EBx, 0xBf (UH：习题四6.关系性质Rir2r3Rir5自反性JJJX反自反性XXXJ对称性XJJJX反对称性VXXJ传递性VJJXJ1 0.(3)=R 是对称的,设x, y) e R 则X) =X J) Rve /?-1.e /?= R , 即 Rx = Rc/By e 49 e 7? e /?/.e 7?即 R2 qR= M R? 0 R,对/

31、? /?,由 R-的定义，有 Vx,zw R? q R /. R ,即 R 是可传递的 c13.解：.,/?=&u2，且nW6：.胪=RUW”2 A = AJA2 .；= J 短=/义，.,需 3|m, 5|m =nt = 15 ,即 = 16/6 =此6 ua；6 =% u & =R故使Rm= H的最小正整数加二1, =1615、解：i/肝=?)=RU R 0 /()=,(a)=内习题五I . ilE :A ：(g 6 )门,右 e jV * R (, b (c. d) | ad = 6c自反性 由A的定义，ab = ba匕N.二(包 办()e R对称性 设R，始ad = beLi IJc:

32、b = da. (c, d I (出人)w 7?传递性 设(i ).(c/ ) e R ,则ii = bC(j Hi ) byC2 (J= b /j C2 = 口 t/r =方产7* *(/ * 力】),( 工丸a ) w R3. 解： K = 1,2,3.4,So = 1.2,4, 3设 Ax )l,2,4, 月2 = 3二 R 二(14 )4 b2 )X1 -4X2,1 )/2 -2),(2,4 ),(44 ),(4,2 ,(44)X33 )4、解：每个集合的划分就可以确定一个等价关系集合有多少个划分就可以确定多少个等价关系不同的划分的个数为:=1 + 24 -1 + C; + 1 = 1

33、5不同的等价关系个数等于不同的划分个数，所以不同的等价关系个数为15.R央K是X上的等价关系R 二是A上的等价关系riR -R.是A上的等价关系氏皿不是A上的等价关系9.解:A = cr9 h9c10.福：契合A上的空关友、恒等关蔡L都是等价关系和偏序关祭，13.证：i）自反性.时P8 w B U .4 , 二 （/.Z）w/?. （ 五的白反 性）显然(b,旭e RClHxBJi i)反对称性,对.方 G，8)e R(Bx8).Gmw RC(BxBi即(a/F)G/?.(,a)w R ,白R的反对称性，=a = h1 1 i)峙递性，对 Vtf.ft.ce B .(a.h) /en(BxB)

34、, Qf.cy /eri(BxB).儿 G.A)W R R .由R的传递性，Gc)w R显然(gc)w Bx B二(a,e) KC(3x)15.解：A = Ia,6,cfc/ Ix=似(皿八(a)!(仇3(/3(4公匕也?g 也打依 cd(4rMM。也 j Sqcr)|8S () d)(a,A)S(*cjS(cr,d) 仍,c)0 E.J I & 储,d) S(a,A,r)S (a,瓦d)S (a5l9U也 u,d) (fl由，c，d)习题六1)对Vbp b2 gB, b| Ab2二加是满射,，3aP a2 A,9 f(ax) = blf(a2) = b2由g(x)的定义，a! Gg(b!),

35、a2 Gg(b2), JLaj g(b2),a2 2 g(l 否则，如 a eg3), a2cg(b),有 f(al) = b2, f(a2) = b 与函数的定义相矛盾，/. g(bx) g(h2),即g为单射2)而g(x)为单射时，对VbeB,并不能保证g(b)“, f(x)不一定是满射11、解：设 A 二口1B =n21)单时：(Qi nj可以看成将山个不同的球放到一个盒子里,所以3)双射：nJ =n2!15、证:f：ArB,g：BTC(1)反证法：设不是单射，叫4w43 f(x)= f(x2)即g。的六g(加，)=g(的加g。/出)与g。/为单射矛盾(2”g/为满射:.对比eC, 3a

36、14小。川)=以/仆)=：4V(x) = yeB，力，凤 mg(J) ; z 即g为满射(3)由(1) (2)苗每论可将习题十1、设G是一个(n, m)简单图。证明：由-C ,等号成立当且仅当G是完全图证光任,论：m C因为G是简单图，IOG的结点度上限m州的人-LG图为总点度上限为max(2(d(v) n - max(dv) rt(n-l) 根靠握手定理,G 图边的匕限力 max|m) n(n*l)/24以 mW%(2) m = Cj =! G是完全图为G具有k限边裁，假设有要点的点慢小于n4邦么G的总度费就小于上限值,迫 重就小于上戢也与条件札臬所以，G的每个给点的点度都为N, G为完全图

37、, G是完全用二)m = Cq因为G是完全队所以每个错点的点度为同总度数为n(n4)r根据矍手定理,图G的边数m = C I2、设G是一个(n, n+1)的无向图，证明G中存在顶点u, d(u) A3。证明：反证法，假设Vu E G t (d(uW 2),则g的总点度上限为max(E (d(u) ) 2n, 根据握手定理，图边的上限为max(m) 2n/2=no与题设m=n+1矛盾，因此，G中存在顶点u, d(u ) A3。3、确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来：(1) (3,2,0,1,5 );(2) (6,3,3,2,2 )(3) (4,4,2,2,4 );(

38、4) (7,6,8,3,9,5 )解：除序列(1)不是图序列外，其余的都是图序列。因为在(1)中，总和为奇数，不满 足图总度数为偶数的握手定理。可以按如下方法构造满足要求的图：序列中每个数字ai对应一个点，如果序列数字是偶数，那么就在又t应的点上画ai/2个环，如果序列式奇数，那么在对应的点上画(ai-1 ) /2个 环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以(2)为例说明：力D6 ,3,32 2 )对应图G的点集合丫= v 123,745)V2 v： (3-1 ) /2 , (3-1 ) /2 , 2/2 , 2/2 ) = (3,1,1,1,1 )将奇数3,3对应的节点V2

39、, V3一组，画一条连线其他序列可以类似作图，当然大家也可以画图其他不同的图形。4、证明：在(n, mi)图中 8 2m/n Ao证明：图的点度数是一组非负整数d(v1),d(v2)d(vn),那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为4, 最小值为 S,平均值=(d(v1)+d(v2)+d(vn) ) /n=2m/n ,所以 8 2m/n Ao5、证明定理10.2。(U) +- ( li ) = 2 in , d 十(u) - L- (ti) = in【定理10.2】对于任何(n, mm有向图G= (V,E),u&VueV证明：有向

40、图中，每条有向边为图贡献一度出度，同时贡献一度入度，所以总出度和入度 相等，并和边数相等。因此，上述关系等式成立。6.役G是(入加简单二部图，证明：m 4 4明：槌日，琳及需要蒯n阶的斛二部的过疑重大值。目叽 Aa n饼州单二部图,其两部分轴窠令分别为VI. V2挪么I虚I + |V2| = n,此种胤I 当G为完全二部二队有最多的边机BP max(m)= |叫叫，翅为,1(叶中2|巾 此函教的最大dH n阶二部图的边的上限值，其上限值为当MM/2时取得,max(max|m|)= :户以 n 阶二部图m 4 匕 447、无向图G有21条边，12个3度数结点，其余结点的度数均为 2,求G的阶数n

41、。解：根据握手定理有：21= (3X12+2 (n-12) /2 ,解次方程得n=15。10、判断图10.29中的两个图是否同构，并说明理由。解：题中两个图不同构，因为左边图的唯一 3度点有2个1度点为其邻接点，而右图唯 的3度点只有1个1度点为其邻接点。因此这两个图不可能同构。13、设有向图D或口下图10.31所示D(1)在图中找出所有长度分别为1,2,3,4的(至少用一种表示法写出它们，并以子图形式画出它们。)(2)在图中找出所有长度分别为3,4,5,6的回路，并以子图形式画出它们。解：(1)C=AeiBe7Ce6DezAORAC=AeiBe8Ce5AC-Ae4Be3CebDe2AC=AD

42、A(2)子图略长度为三的回路：AeiA&iAeiAi AeiAegDe八足AeBe口Ce：A长度为四的回路：AAAAh AAADA, AABe7CA,AABe4A*ABeDABeDA长度为五的回路：AAAAAAt AAAADA, AAABezCA. AAABesCA, AABe；(口一1)(卜2),证明G必是连通心构造一个；(lD(l2)据联通解以I证明:假洪不连通,分支GL G2- Gk,都么研的边教的最雉max (m)二-1 ) n / 2 (2)因为G连通，且G无割边，所以任意两个结点u, v,都存在简单道路p=u.wv。又因为G 无割边，所以，删除边 wv后，子图依然连通，即 w, v

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

44、明：(3) = (4)对任意两条边e1,e2其端点分别为u1,u2,v1,v2.根据(3)存在回路 C1=u1v1v2u1,C2=u2vivlu2.那么 可以形 成新的 闭道路P=u1.v1v2u2v1v2u1，在其中将重复边剔除，得到新白回路C3,其中包含e2和u1,u2结点，可以将回路中u1.u2用u1u2=e1替换，就得到新的回路，包含 e1,e2,满足要求。证明：(4) = (1)因为任意两条吧都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不连通，分支中的任何一对不再同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边。19.设G-E)是点度均为偶数的连通图:证

45、明：对任何证明：Gr最多产生dlr)个奇数度点,又因为每个连通分支中奇数度点的个数是Gr的连通分支最少有两条边利v相连，所以总连通分支教小于等于d(v)/2i21.证明：在非平凡连通图。中，白为割边的充要条件是它不包含于G的任何圈中证明：1)。为割边G。不包含于G的任何圈中假设e包含在某一慝Ci中，那么删除此边,但边关联的两个细接点依然 以没有破坏原图的连通性因此不是割边，矛盾,所以假设不成立，既不包含 何圈中：2) e不包含于G的任何圈中= 为副边假设为割边，那么删除此边，生成子屋依然连送，c关联的两个邻接点 新存在，比基本道路连同构成一个网,与题设五盾,所以假设不成立，鹿为W 根据1), 2)可知，题设结怆成立23、证明：在具有n (n2)个结点的简单无向图G中，至少有两个结点的度数相同。证明：此题可用鸽巢原理，因为 n个结点的简单无向图 G中，结点的度数只可能是0,1,2.n-1这 n 个数，又因为如果有结点的度数为0，那么就不可能有结点的度为n-1 ，反之亦然。所以 n 个结点，最多有n-1 中度数，其中必有至少 2 个结点的度数相同。24、设G