离散数学习题(23页).doc

《离散数学习题(23页).doc》由会员分享，可在线阅读，更多相关《离散数学习题(23页).doc（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-离散数学习题-第 23 页第一章习题1. 1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）是无理数。（2）5能被2整除。（3）现在开会吗？（4）x+50（5）这朵花真是好看！（6）2是素数当且仅当三角形有三条边。（7）雪是黑色的当且仅当太阳是从东方升起。（8）2000年10月1日天气晴好。（9）太阳系以外的星球上有生物。（10）小李在宿舍里。（11）全体起立。（12）4是2的倍数或是3的倍数。（13）4是偶数且是奇数。（14）李明和王华是同学。（15）蓝色和黄色可以调配成绿色。1.2 将上题中的命题符号化，并讨论他们的真值。1. 3判断下列各命题的真值。（1） 若2+2

2、=4，则3+3=6；（2） 若2+2=4，则3+36；（3） 若2+2=4，则3+3=6；（4） 若2+2=4，则3+3=6；（5） 2+2=4，当且仅当3+3=6；（6） 2+2=4，当且仅当3+36；（7） 2+24，当且仅当3+3=6；（8） 2+24，当且仅当3+36；1. 4将下列命题符号化，并讨论其真值。（1） 如果今天是1号，则明天是2号；（2） 如果今天是1号，则明天是3号；1. 5将下列命题符号化。（1） 2是偶数不是素数；（2） 小王不但聪明而且用功；（3） 虽然天气冷。老王还是来了；（4） 他一边吃饭，一边看电视；（5） 如果天下大雨，他就乘公交汽车来；（6） 只有天下大

3、雨，他才乘公交汽车来；（7） 除非天下大雨，否则他不乘公交汽车来；（8） 不经一事，不长一智；1. 5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1） p(qr);（2） (pr)(ps); （3）（p(qr)(pq)(rs);(4)(p(qrp)(rs);1.6设p：2+3=5。 q：大熊猫产在中国。 r：复旦大学在广州。求下列复合命题的真值：（1）(pq)r（2）(r(pq)p（3）r(pqr)（4）(pqr)(pq)r)1.7用真值表判断下列公式的类型：方法不限。（1）p(pqr)（2）(pq)q（3）(qr)r（4）(pq)(qp)（5）(pr)(pq)（6）(pq

4、)(qr)(pr)（7）(pq)(rs)1. 8用等值演算法证明下列等值式。(1) (pq)(pq)p;(2) (pq)(pr)(p(qr);(3) (pq)(qp)(pq)1. 9设 A,B,C 为任意的命题公式。(1) 已知ACBC,问AB吗？(2) 已知ACBC,问AB吗？(3) 已知AB, 问AB吗？1.10求下列命题公式的主析取范式，主合取范式，成真赋值，成假赋值。1.11通过求主析取范式判断下列各组命题公式是不是等值。1.12有一探测队有3名队员，有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜；已说：这不是铁，是锡；丙说：这不是锡，是铁；经实验鉴定后发现，其中一人两个

5、判断是正确的，一个人判断对一半，一个人的判断全错了，根据以上的情况判断矿样的种类。1.13判断下列的推理是不是正确，先将命题符号化，在写出前提和结论，然后在进行判断。（1）如果今天是1号，则明天是5号，今天是1号，所以明天是5号。（1）如果今天是1号，则明天是5号，明天是5号，所以今天是1号。（1）如果今天是1号，则明天是5号，明天不是5号，所以今天不是1号。（1）如果今天是1号，则明天是5号，今天不是1号，所以明天不是5号。1.14构造下面的推理的证明。1.15如果他是理科学生，他必学好数学，如果他不是文科学生，他必是理科学生，他没有学好数学，所以他不是文科学生。判断上面的推理是不是正确，并

6、且证明你的结论。1.16给定命题公式如下；上述公式的成真赋值A，成假赋值为B，公式的类型为C。供选择的答案: 无 全体赋值 010，100，101，111 010，100，101，110，111B: 无 全体赋值 000，001，011， 000，010，110C: 重言式 矛盾式 可满足式1.17给定命题公式如下；上述公式的主析取范式中含的极小项的个数为A，主合取范式含的极大项的个数为B，成真值的赋值为C供选择的答案A 2 3 5 0 8B 0 8 5 3 C 000,001,110; 001,011,101,110,111; 全体赋值 无1.18给定下列三组前提。上述前提中，（1）的逻辑结

7、论（有效结论）为A，（2）的逻辑结论为B，（3）的逻辑结论C。供选择的答案A,B,C: r q s 1.19设计一个符合下列要求的室类照明控制的线路，在房间的门外、门类及其床头分别装一个可以控制同一个电灯F的3个开关A,B,C, 当且仅当一个开关的搬键向上或3 个开关的搬键都向上时候电灯亮，则F的逻辑关系式可以化简为A供选择的答案A: 1.20某电路中有一个灯泡和三个开关A,B,C。已知在且仅在下述四种情况下灯亮：（1）C的扳键向上，A,B的扳键向下。（2）A的扳键向上，B,C的扳键向下。（3）B,C的扳键向上，A的扳键向下。（4）A,B的扳键向上，C的扳键向下。设F为1表示灯亮，p,q,r分

8、别表示A,B,C的扳键向上。（a）求F的主析取范式。（b）在联结词完备集,上构造F.（c）在联结词完备集,上构造F.1.21一个排队线路，输入为A,B,C，其输出分别为FA,FB,FC。本线路中，在同一时间内只能有一个信号通过，若同时有两个和两个以上信号申请输出时，则按A,B,C的顺序输出。写出FA,FB,FC在联结词完备集,中的表达式。第二章习题2.1在一阶逻辑中将下列命题符号化. （1）鸟都会飞翔. （2）并不是所有人都爱吃糖. （3）有人爱看小说. （4）没有不爱看电影的人. 2.2 在一阶逻辑中将下列命题符号化，并指出个命题的真值.个体域分别为 （a）自然数集合N（N中含O）. （b）

9、整数集合Z. （c）实数集合R. （1）对于任意的x，均由 (2 )存在x，使得x+2=0. (3 ) 存在x，使得5x=1. 2.3 在一阶逻辑中将下列命题符号化. （1）每个大学生不是文科生就是理科生.（2）有些人喜欢所有的花.（3）没有不犯错误的人.（4）在北京工作的人未必就是北京人.（5）任何金属都可以溶解在某种液体中.（6）凡对顶角都相等.2.4在一阶逻辑中将下面命题符号化，并分别讨论个体域限制为(a),(b)时命题的真值：（1）对于任意的x，均有x2-2=(x+)(x-)。（2）存在x，使得x+5=9。其中(a)个体域为自然数集合，(b)个体域为实数集合。2.5将下列各式翻译成自然

10、语言，然后再不同领域中却定它们的真值.个体域分别为（a）实数集合(b)整数集合(c)正整数集合(d)（非0 实数集合）2.6设个体域D=a,b,c，消去下列各式的量词：(1) xy(F(x)G(y)(2) xy(F(x)G(y)(3) xF(x)yG(y)(4) x(F(x,y)yG(y)2.7设个体域D=1,2，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。(1) x(F(x)G(x)(2) x(F(x)G(x)2.8给定解释I如下：(a) 个体域D=3,4。(b) (x)为(3)=4，(4)=3。(c) (x,y)为(3,3)=(4,4)=0，(3,

11、4)=(4,3)=1。 试求下列公式在I下的真值：(1) xyF(x,y)(2) xyF(x,y)(3) xy(F(x,y)F(f(x),f(y)2.9在自然推理系统F中构造下面推理的证明：(1) 前提：x(F(x)(G(a)R(x)，xF(x)结论：x(F(x)R(x)(2) 前提：x(F(x)G(x)，xG(x)结论：xF(x)(3) 前提：x(F(x)G(x)，x(G(x)R(x)，xR(x)结论：xF(x)2.10在自然推理系统F中，证明下面推理：(1) 每个有理数都是实数，有的有理数是整数，因此有的实数是整数。(2) 有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不是

12、无理数。(3) 不存在能表示成分数的无理数，有理数都能表示成分数，因此有理数都不是无理数。2.11(1) 试给出解释，使得在下具有不同的真值（2）试给出解释，使得在下具有不同的真值2.12给出解释，使下面的两个公式在解释下面为假，从而说明这两个公式都不是逻辑有效式（用真式）2.13设个体域，在D=a,b,c 下D验证量词否定等值式2.15设个体域，在D=a,b,c,消去下列公式中的量词。2.16求下列各式的前束范式，要求使用自由变换换名规则。2.17 构造下面推理的证明（1）前提； 结论：（3） 前提：）结论：2.18取个体域为整数集，给定下列各公式在上面的公式中，真命题为A, 假命题为B供选

13、择的答案A: (1),(3),(4),(6) (3),(4),(5) (1),(3),(4),(5)(3),(4),(6),(7)B: (2),(3),(6) (2),(6),(8)(1),(2),(6),(7)(2),(6),(8),(7)2.19在一阶逻辑中给出下面4个推理2.20在一阶逻辑中构造下面的推理证明每个喜欢步行的人都不喜欢坐汽车， 每个人或者喜欢坐汽车或自行车，有的人不喜欢自行车，所以有的人不喜欢步行。命题符号化： F(x): x 喜欢步行,G(x):x 喜欢坐汽车,H(x):x 喜欢自行车.在上述推理中，（2）后用的推理规则为A，（4）后面用的推理规则为B，（5）用的推理规则

14、是（2）（4）所得到的推理规则C,（8）用的推理规则是（5）和（7）得到的推理规则D供选择的答案A,B,C,D UI, EI, UG, EG,拒取式假言推理析取三段论第三章习题集合与二元关系3.1.选择适当的谓词表示下列集合：(1)小于5的非负整数(2)奇整数集合(3)10的整倍数的集合2.用列元素法表示下列集合：(1)S1x|x是十进制的数字(2)S2x|x2x5(3)S3x|xxZ3x3(5)S5|x，yZ0x2-1y03.2.设F表示一年级大学生的集合，S表示二年级大学生的集合，M表示数学专业学生的集合，R表示计算机专业学生的集合，T表示听离散数学课学生的集合，G表示星期一晚上参加音乐会

15、的学生的集合，H表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么？请从备选的答案中挑出来。 (1)所有计算机专业二年级的学生在学离散数学课。(2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉。(3)听离散数学课的学生都没参加星期一晚上的音乐会。(4)这个音乐会只有大学一、二年级的学生参加。(5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会。备选答案：TGH GHT SRTHGT TG FSGGFS S-(RM)G GS-(RM)3.3.确定下列命题是否为真：(1)(2)(3)(4)(5)a，ba，b，c，a，b，

16、c(6)a，ba，b，c，a，b (7)a，ba，b，a，b(8)a，ba，b，a，b3.4已知A=,求AP(A)。3.5对于任意集合A,B,C，若ABAC,是否一定有BC成立？为什么？ 3.6设A,B,C,D是任意集合，(1) 求证(AB)(CD)=(AC)(BD)。(2) 下列等式中哪个成立？那些不成立?对于成立的给出证明，对于不成立的举一反例。(AB)(CD)=(AC)(BD)(A-B)(C-D)=(AC)-(BD) 3.7设A,B为任意集合，证明若AA=BB，则 A=B。3.8列出从集合A=1，2到B=1的所有的二元关系。3.9列出集合A=2，3，4上的恒等关系IA，全域关系EA，小于

17、或等于关系LA，整除关系DA。3.10.列出集合A=，上的包含关系。3.11.设A=1，2，4，6，列出下列关系R: (1) R=|x，yAx+y2(2) R=|x，yA|x-y|=1(3) R=|x，yAx/yA(4) R=|x，yAy为素数3.12.Ri是X上的二元关系，对于xX定义集合Ri(x)=y|xRiy。显然Ri(x)X。如果X=-4，-3，-2，-1，0，1，2，3，4，且令R1=|x，yXxyR2=|x，yXy-1xy+2R3=|x，yXx2y求R1(0)，R1(1)，R2(0)，R2(-1)，R3(3)。3.13.设A=0，1，2，3，R是A上的关系，且R=，给出R的关系矩阵

18、和关系图。3.14设=,=,求AB,AB,domA,dom(AB),ranA,ranB,ran(AB),fld(A-B) 3.15设R=,求RR,R-1 ,R0,1,R1,2。3.16 设A=,求A-1,A2,A3,A,A,A,A,A。3.17 设A=a,b,c,d，R1,R2为A上的关系，其中R1=,R2=,求R1R2, R2R1,R12,R23。3.18设A=a,b,c，试给出A上两个不同的关系R1和R2,使得 R12=R1, R23=R2 3.19证明定理7.4的(1)，(2)，(4)。3.20证明定理7.5的(2)，(3)。3.21设R1和R2为A上的关系，证明： （1）(R1R2)-

19、1=R1-1R2-1 （2）(R1R2)-1=R1-1R2-1第四章习题代数系统4.1、列出以下运算的运算表：(1) A=1,2,，xA，x是x的倒数，即x=.(2) A=1,2,3,4,x,yA有xy=max(x,y),max(x,y)是x和y之中较大的数。4.2、判断下列集合对所给的二元运算是否封闭：(1) 整数集合Z和普通的减法运算(2) 非零整数集合Z*和普通的除法运算(3) 全体nn实矩阵集合Mn(R)和矩阵加法及乘法运算，其中n2(4) 全体nn实可逆矩阵集合关于矩阵加法和乘法运算，其中n2(5) 正实数集合R+和运算，其中运算定义为：,R+,ab=ab-a-b(6) nZ+,nZ

20、=nz|zZ.nZ关于普通的加法和乘法运算。(7) A=a1,a2,.,an,n2.运算定义如下：ai,ajA,aiaj=ai.(8) S=2x-1|xZ+关于普通的加法和乘法运算。(9) S=0,1,S关于普通的加法和乘法运算。 (10)S=x|x=2n,nZ+，S关于普通的加法和乘法运算4.3、对于上题中封闭的二元运算判断是否适合交换律、结合律和分配律。4.4、对习题2中封闭的二元运算找出它的单位元，零元和所有可逆元素的逆元。4.5、S=QQ,Q为有理数集，*为S上的二元运算，,S有*=(1) *运算在S上是否可交换，可结合？是否为幂等的？(2) *运算是否有单位元，零元？如果有，请指出，

21、并求S中所有可逆元素的逆元。4.6、R为实数集，定义以下六个函数f1,.,f6.x,yR有f1()=x+y,f2()=x-y,f3()=xy, f4()=max(x,y),f5()=min(x,y), f6()=|x-y|(1) 指出哪些函数是R上的二元运算。(2) 对所有R上的二元运算说明是否为可交换、可结合、幂等的。(3) 求所有R上二元运算的单位元、零元以及每一个可逆元素的逆元。4.7、令S=a,b,上有四个二元运算：*,和,分别由表10.8确定。表10.8(1) 这四个运算中哪些运算满足交换律、结合律、幂等律(2) 求每个运算的单位元、零元及所有可逆元素的逆元。4.8、设S=1,2,.

22、,10,问下面定义的运算能否与S构成代数系统?如果能构成代数系统则说明*运算是否满足交换律、结合律，并求*运算的单位元和零元。(1) x*y=gcd(x,y),gcd(x,y)是x与y的最大公约数。(2) x*y=lcm(x,y),lcm(x,y)是x与y的最小公倍数。(3) x*y=大于等于x和y的最小整数。(4) x*y=质数p的个数，其中xpy. 4.9、下面各集合都是N的子集，它们能否构成代数系统V=的子代数：(1) x|xNx可以被16整除(2) x|xNx与8互质(3) x|xNx是40的因子(4) x|xNx是30的倍数 4.10、设V=，其中+和分别代表普通加法和乘法，对下面给

23、定的每个集合确定它是否构成V的子代数，为什么？(1) S1=2n|nZ(2) S2=2n1|nZ(3) S3=1，0，1 4.11、设V1=,其中xy表示取x和y之中较大的数。V2=,其中x*y表示取x和y之中较小的数。求出V1和V2的所有子代数。指出哪些是平凡子代数，哪些是真子代数。 第五章几个典型的代数系统5.1.设A=0,1,试给出半群的运算表,其中为函数的复合运算。5.2.设G=a+bi|a,bZ,i为虚数单位,即i2=-1.验证G关于复数加法构成群。5.3.设Z为整数集合,在Z上定义二元运算如下：x,yZ,xy=x+y-2 问Z关于运算能否构成群？为什么？ 5.4.设A=x|xRx0

24、,1.在A上定义六个函数如下：f1(x)=x, f2(x)=x-1, f3(x)=1-x,f4(x)=(1-x)-1, f5(x)=(x-1)x-1, f6(x)=x(x-1)-1 令F为这六个函数构成的集合,运算为函数的复合运算。(1) 给出运算的运算表。(2) 验证是一个群。5.5.设G为群,且存在aG,使得 G=ak|kZ, 证明G是交换群。5.6.证明群中运算满足消去律. 5.7.设G为群,若xG有x2=e,证明G为交换群。5.8.设G为群,证明e为G中唯一的幂等元。5.9.证明4阶群必含2阶元。5.10设A=a+bi|a,bZ,i2=-1,证明A关于复数的加法和乘法构成环,称为高斯整

25、数环。5.12.(1) 设R1,R2是环,证明R1与R2的直积R1R2也是环。(2) 若R1和R2为交换环和含幺环,证明R1R2也是交换环和含幺环。5.13. 判断下列集合和给定运算是否构成环、整环和域,如果不能构成,说明理由。(1) A=a+bi|a,bZ,其中i2=-1,运算为复数的加法和乘法。(2) A=-1,0,1,运算为普通加法和乘法。(3) A=M2(Z),2阶整数矩阵的集合，运算为矩阵加法和乘法。(4) A是非零有理数集合Q*,运算为普通加法和乘法。5.14.设G是非阿贝尔群,证明G中存在元素a和b,ab,且ab=ba. 5.15.设H是群G的子群,xG,令xHx-1=xhx-1

26、|hH, 证明xHx-1是G的子群,称为H的共轭子群。5.16.设 (1) G上的二元运算为矩阵乘法,给出G的运算表(2) 试找出G的所有子群(3) 证明G的所有子群都是正规子群。5.17.设G是有限群，K是G的子群，H是K的子群,证明G:H=G:KK:H. 5.18.令G=Z,+是整数加群。求商群Z/4Z,Z/12Z和4Z/12Z. 5.19.对以下各小题给定的群G1和G2以及f:G1G2,说明f是否为群G1到G2的同态。如果是,说明G是否为单同态,满同态和同构,并求同态像f(G1)和同态核kerf.(1) G1=,G2=,其中R*为非零实数的集合,+和分别表示数的加法和乘法。f:ZR*,f

27、(x)=(2) G1=,G2=,其中+和分别表示数的加法和乘法A=x|xC|x|=1,其中C为复数集合。f:ZA,f(x)=cosx+i sinx(3) G1=,G2=,+和以及A的定义同(2).f:RA,f(x)=cosx+i sinx 5.20.设f是群G1到G2的同构,证明f-1是G2到G1的同构。5.21.图中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。5.22.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。(1) L=1,2,3,4,5(2) L=1,2,3,6,12(3) L=1,2,3,4,6,9,12,18,36(4) L=1,2,22,.,2n,

28、nZ+ 5.23.(1)画出Klein四元群的子群格。(2)画出模12的整数群Z12的子群格。(3)画出3元对称群S3的子群格。 5.24.设L是格,求以下公式的对偶式:(1) a(ab)a(2) a(bc)(ab)(ac)(3) b(ca)(bc)a 5.25.设L是格,a,b,cL,且abc,证明 ab=bc5.26.针对图13.10中的格L1,L2和L3,求出他们的所有子格。 图13.105.27.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些补元。5.28.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说明理由。5.29.对以下各小题给定的集合和运算判断它们是哪

29、一类代数系统(半群,独异点,群,环,域,格,布尔代数),并说明理由。(1) S1=0，1,-1，运算为普通加法和乘法。(2) S2=a1,a2,.,an,ai,ajS2,ai*aj=ai.这里的n是给定的正整数,且n2.(3) S3=0,1,*为普通乘法。(4) S4=1,2,5,7,10,14,35,70,和*分别表示求最小公倍数和最大公约数运算。(5) S5=0,1,2,*为模3加法,为模3乘法。5.30.设B是布尔代数,B中的表达式f是 (ab)(abc)(bc) (1)化简f.(2)求f的对偶式f* 。5.31.设是布尔代数，在B中化简以下表达式：上定义二元运算*，a,bB, （1）(

30、ab)(ab)(ab) （2）(ab)(a（bc)c 5.32.对于n=1,.,5,给出所有不同构的n元格,并说明哪些是分配格、有补格和布尔格。5.33.设是布尔代数,在B上定义二元运算,x,yB有xy=(xy)(xy)问能否构成代数系统？如果能,指出是哪一种代数系统。为什么？ 5.34.设G1为循环群,f是群G1到G2的同态,证明f(G1)也是循环群。5.35.设G=是15阶循环群。(1) 求出G的所有的生成元。(2) 求出G的所有子群。5.36.设,是5元置换,且 (1) 计算,-1,-1,-1(2) 将,-1,-1表成不交的轮换之积。(3) 将(2)中的置换表示成对换之积,并说明哪些为奇

31、置换,哪些为偶置换。5.37设A=1,2,5,10,11,22,55,110是110的正因子集，A, 构成的偏序集，其中 为整除关系。（1）画出偏序集A, 的哈斯图。（2）说明该偏序集是不是构成布尔代数，为什么？第六章习题 图论基础6.1下列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？（1）1，1，1，2.3 (2)2,2,2,2,2 (3)1,2,3,4,5 (4)1,3,3,36.2设有向简单图D的度数为2，2，3，3，入度列0，0，2，3，试求D的除度列。6.3设是4阶有向简单图，度数列为3，3，3，3.它的入度列9或出度列）能为1，1，1，1吗？6.4设( )为一

32、正整数序列， 互不相同，问此序列能构成n阶无向图的度数列吗？为什么？6.5下面无向图中有几个顶点？（1）16条边，每个顶点都是2度顶点.（2）21条边，3个4度顶点，其余的都是3度顶点.（3）24条边，各顶点的度数是相同的.6.6 35条边 ，每个顶点的度数至少为3的图最多有几个顶点?6.7设n阶无向简单图中，（G）=n-1，问 （G）应为多少？6.8一个n（n）阶无向简单图中，为奇数，已知中有各奇度顶点，问的补图中有几个奇度顶点？6.9设是阶有向简单图，是的子图，已知的边数（），问的边数为多少？6.10画出的所有非同构的子图，其中有几个是子图？生成子图中有几个是连通图？6.11设为阶简单图（

33、无向图或有向图），为的补图，若，则称为自补图，的生成子图中有几个非同构的自补图？6.12设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G中至少有几个顶点？在最少顶点的情况下，写出G的度数列、(G)、(G). 6.13设n阶图G中有m条边，证明：(G)2m/n(G). 6.14设无向图中有6条边，3度与5度顶点各一个，其余的都是2度顶点，问该图有几个顶点？ 6.15证明空间中不可能存在有奇数个面且每个面都有奇数条棱的多面体。 6.16阶2-正则图有几种非同构的情况？ 6.17设n阶无向图为3-正则图，且边数m与n满足2n-3=m，问这样的无向图有几种非同构的情况？6.18

34、画出阶有完全图所有非同构的子图，问其中有几个是生成子图？生成子图中有几个是自补图？6.19设均为阶无向简单图，他们均由两条边，他们能彼此均非同构吗？为什莫？6.20已知阶无向图中有条边，各顶点的度数均为，又已知，问在同构的意义下，是唯一的吗？又若为简单时，是否唯一？6.22在的边上涂上红色或蓝色，证明对于任意一种随意的涂法，总存在红色或蓝色？6.23试寻找个阶有向简单图，使得强连通图；为单向连通图，但不是强连通图；而是弱连通图，但不是单向连通图，当然，更不是强连通图6.24设-和-分别为无向连通图G的点割集.G-的连通图分支个数k一定为几？G-l连通分支数也是定数吗？6.25有向图D如图7.1

35、9所示.求D中长度为4的通路总数，并指出其中有多少条是回路？又有几条是-到-的通路？6.26现有3个4阶4条边的无向简单图G1,G2,G3,证明它们中至少有两个是同构的。 6.27设G是n阶自补图，证明n=4k或n=4k+1，其中k为正整数。 6.28设G是n阶无向简单图，n3且为奇数，证明G与中奇度顶点的个数相等。 6.29已知在完全二部图Kr,s中，rs.(1)Kr,s中含有多少种非同构的圈？(2)Kr,s中至多有多少个顶点彼此不相邻？(3)Kr,s中至多有多少条边彼此不相邻？(4)Kr,s的点连通度为几？边连通度为几？ 第七章习题欧拉图7.1画出完全2部图-.7.2设G为n（n-1），至

36、少用几种颜色给G的顶点染色，使相邻的顶点颜色不同？7.3完全二部图-中，边数m为多少？7.4完全二部图-的匹配数为多少？7.5今有工人甲.乙.丙去完成三项任务a，b，c.已知工人甲能胜任a，b，c三项任务；工人乙能胜任a，b两项任务；工人丙能胜任b，c两项任务.你能给出一种安排方案，使每个工人各自去完成一项他们能胜的任务吗？7.6画一个无向欧纳图，使它具有：（1）偶数个顶点，偶数条边；（2）奇数个顶点，奇数调变；（3）偶数个顶点，奇数条边；（4）奇数个顶点，偶数条边；7.7画一个有向的欧纳图，要求同8.6。7.8画一个无向图，使它是：（1）既是欧纳图，又是哈密尔顿图；（2）是欧纳图，而不是哈密

37、尔顿图；（3）是哈密尔顿图，而不是欧纳图；（4）既不是欧纳图，也不是哈密尔顿图.7.9画一个有向图，要求同8.8。7.10若D为有向图欧纳图，则D一定为强连通图.其逆命题成立吗？7.11在什莫条件下无向图-（ ）为哈密尔顿图？又在什莫条件下为欧纳图？7.12有割点的无向图G不可能为哈密尔顿图.G也不一定不是欧纳图吗？7.13判断下列命题是否为真？(1)完全图Kn(n3)都是欧拉图。(2)n(n2)阶有向完全图都是欧拉图。(3)完全二部图Kr,s(r,s均为非0正偶数)都是欧拉图。 7.14在k(k2)个长度大于或等于3的圈(全为无向的或全为有向的)之间至少加多少条新边(有向的加有向边)才能使所

38、得图为欧拉图？ 7.15证明：若有向图D是欧拉图，则D是强连通的。 7.16完全图Kn(n1)都是哈密顿图吗？ 7.17设G是无向连通图，证明：若G中有桥或割点，则G不是哈密顿图。 7.18设G为n阶无向简单图，边数m=(n-1)(n-2)+2，证明G是哈密顿图。再举例说明当m=(n-1)(n-2)+1时，G不一定是哈密顿图。 7.19今有2k(k2)个人去完成k项任务。已知每个人均能与另外2k-1个人中的k个人中的任何人组成小组(每组2个人)去完成他们共同熟悉的任务，问这2k个人能否分成k组(每组2人)，每组完成一项他们共同熟悉的任务？ 7.20K5带权图如下图所示，求图中最短哈密顿回路。

39、第八章习题 树8.1证明下面3个图都是平面图。 8.2下面3个图都是平面嵌入，先给图中各边标定顺序，然后求出图中各面的边界和次数。 8.3设G是n阶m条边的简单平面图，已知m30，证明(G)4. 8.4设n阶m条边的平面图是自对偶图，证明m=2n-2. 8.5证明：平面图G的对偶图G*是欧拉图当且仅当G中每个面的次数均为偶数。 8.6求下面3个图的点色数。 8.7 无向图G如图所示：求G的支配数0，点覆盖数0，点独立数0，边覆盖数1，匹配数1. 8.8 证明图中的最大匹配一定是极大匹配，但反之不真。 8.9 证明：对于任意的无向简单图G，均有0. 8.10 n位教员要教n门课程，已知每位教员至少能教两门课程，而每门课程至多有两位教员能教，问能否每位教员教一门课且每门课都有人教？ 8.11 设二部图G=为k-正则图，其中k1，证明G中存在完美匹配。