离散数学题库

试题总汇数理逻辑部分1、判断下列句子中哪些是命题（1）2是素数（2）血是黑色的（3）2+3=5（4）明年10月1日是晴天（5）3能被2整除（6）这朵花多好看呀！（7）明天下午有会吗？（8）请关上门！（9）X + y 5（10）地球外的星球上也有人2、将下列命题符号化（1）3不是偶数（2）2是素数和偶数（3）李芳学过英语或日语（4）如果角A和角B是对顶角，则角A等于角B（5）李平虽然聪明，但不用功（6）李平不但聪明，而且用功（7）小王是游泳冠军或者百米赛跑冠军（8）小王现在在宿舍或者在图书馆（9）选小王或者小李中的一人当班长（10）如果我上街，我就去书店看看，除非我很累（11）如果明天天气好，我们去郊游。否则，不去郊游（12）你爱我，我就嫁给你3、判断下列命题公式是否等值（1）（pq）与pq（2）（pq）与pq4、验证下列等值式（1）p（qr）（ pq）r（2）p（ pq）（pq）5、用等值演算法解决下面问题：A、B、C、D 4人百米竞赛。观众甲、乙、丙预报比赛的名次为，（1）甲：C第一，B第二。（2）乙：C第二，D第三。（3）丙：A第二，D第四。比赛结束后发现甲、乙、丙每人报告的情况都是给对一半。试问，实际名次如何？6、求下面命题公式的主析取范式和主合取范式（1）（pq）r）p7、利用真值表求主析取范式和主合取范式（1）（pq）r8、逻辑推理证明（1）前提：pr，qs，pq。结论：rs。（2）前提：pq，pr，st，sr，t。结论：q（3）前提：p（qr），sp，q。结论：sr。（4）前提：p（rs）q），p，s。结论：q9、给定语句如下：（1）15是素数（2）10能被2整除，3是偶数（3）你下午有会吗？（4）2x+3 0（5）2是素数或是合数（6）这个男孩真勇敢呀！（7）如果2+2=6，则5是奇数（8）只有4是偶数，3才能被2整除（9）明年5月1日是晴天（10）圆的面积等于半径的平方与的乘积以上10个语句中，是简单命题的为A，是复合命题的为B，是真命题的为C，是假命题的为D，真值待定（真值客观存在，只是现在不知道）的命题为E。A：（1）、（4）、（8）（4）、（6）、（9）、（10）（1）、（9）、（10）B：（3）、（10）（2）、（5）、（7）、（8）（7）、（8）C：（2）、（5）、（9）、（10）（7）、（8）、（10）（2）、（9）、（10）（5）、（7）、（8）、（10）D：（1）、（2）、（8）（1）、（2）（1）、（5）E：（4）、（9）（9）（7）、（8）10、判断公式类型（1）（pq）（pq）（2）（pq）（pq）（qp）（3）（pq）q（4）（pp）q（5）p（pq）（6）（pp）（qq）r）（7）（pq）p）p（8）（pq）（pq）（9）（pq r）（p qr）（10）（pq）r11、给定命题公式如下：（pq）（pq）该命题公式的主析取范式中含极小项的个数为A，主合取范式中含极大项的个数为B，成真赋值个数为C，成假赋值个数为D。A、B、C、D：（1）0,（2）1,(3)2,(4)3,(5)412、一公安人员审查一件盗窃案，已知的事实如下：（1）甲或乙盗窃了录音机（2）若甲盗窃了录音机，则作案时间不能发生在午夜前（3）若乙的证词正确，则午夜时屋里灯光未灭（4）若乙的证词不正确，则作案时间发生在午夜前（5）午夜时屋里灯光灭了推理证明，谁盗窃了录音机。13、设p=1，q=0，r=1，s=0，有下列命题公式（1）（pq）（sr）（2）（pqrs）(sq)（3）（pqr）（ps）那么，（1）的真值为 ；（2）的真值为 ；（3）的真值为 ；14、对于下面的语句，（1）只要43，就有32（2）只要43，就有32（3）只有43，才有32（4）只有43，才有32（5）除非43，否则32（6）43仅当32（7）43当且仅当32则，他们的真值是（1） （2） （3） （4） （5） （6） （7） 。15、设A是含n个命题变项的公式，下面4个结论中，哪个是错误的？（1）若A的主析取范式中含2n 个极小项，则A是重言式（2）若A的主合取范式中含2n 个极大项，则A是矛盾式（3）若A的主析取范式中不含任何极小项，则A的主析取范式为0（4）若A的主合取范式中不含任何极大项，则A的主合取范式为016、已知命题公式A含有3个命题变项，其成真赋值为000，010，100，110。则A的主析取范式为 ，主合取范式为 。17、判断下列语句是否为命题，如是命题请指出是简单命题还是复合命题，并讨论真值（1）是无理数（2）5能被2整除（3）现在开会吗？（4）x+50（5）这朵花真好看呀！（6）2是素数当且仅当三角形有3条边（7）血是黑色的当且仅当太阳从东方升起（8）2008年10月1日天气晴朗（9）太阳系以外的星球上有生物（10）小李在宿舍里（11）全体起立（12）4是2的倍数或是3的倍数（13）4是偶数且是奇数（14）李明与王华是同学（15）蓝色和黄色可以调配成绿色18、将下列命题符号化，并讨论其真值（1）如果今天是1号，则明天是2号（2）如果今天是1号，则明天是3号19、设A、B、C为任意的命题公式（1）已知 ACBC，问AB吗？（2）已知 ACBC，问AB吗？（3）已知 A B，问AB吗？20、设计一个符合如下要求的室内照明控制线路：在房间的门外、门内及床头分别装有控制同一个电灯F的3个开关A、B、C。当且仅当一个开关的键向上或3个开关的键都向上时电灯亮。则F的逻辑关系式可化简为 。（1）ABC （2）ABC（ABC） （3）AB（AC）（4）C（AB）21、将下列语句用谓词表达式符号化（1）2是素数且是偶数（2）如果2大于3，则2大于4（3）凡是有理数均可表成分数（4）有的有理数是整数（5）没有不吃饭的人（6）素数不全是奇数（7）一切人都不一样高（8）有的自然数无先驱数（9）有些人喜欢所有的花（10）任何金属都可以溶解在某种液体中（11）凡是对顶角都相等22、指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约束出现（1）x（F（x）yH（x，y）（2）x F（x）G（x，y）（3）xy（R（x，y）L（x，y）x H（x，y）23、给定解释I如下：1）DI=2，32）DI中特定元素a=23）函数f（x）为f（2）=3，f（3）=24）谓词F（x）为F（2）=0，F（3）=1； G（x，y）为G（ i，j）=1，i，j=2，3； L（x，y）为L（ 2，2）= L（ 3，3）=1；L（ 2，3）= L（ 3，2）=0在解释I下，求下列各式的值。（1）x（F（x）G（x，a）（2）x（F（f（x）G（x，f（x）（3）xy L（x，y）24、求下列公式的前束范式（1）xF（x）x G（x）（2）xF（x）x G（x）（3）xF（x）x G（x）（4）xF（x）x G（x）25、设F（x）：x是人，G（x）：x爱吃糖。有人给出语句“不是所有人都爱吃糖”的4种谓词表达式：（1）x（F（x）G（x）（2）x（F（x）G（x）（3）x（F（x）G（x）（4）x（F（x）G（x）正确的答案是 。26、给出解释I，使下面两个公式在解释I下均为假，从而说明这两个公式都不是永真式（1）x（F（x）G（x）（xF（x）x G（x）（2）（xF（x）x G（x）x（F（x）G（x）27、取个体域为整数集，给定下列公式（1）xy（x*y=0）（2）xy（x*y=1）（3）yx（x*y=2）（4）xy z（x y = z）（5）x y = - y + x（6）xy（x *y = y）（7）x（x*y = x）（8）xy（x + y = 2y）在上面的公式中，真命题的为A，假命题的为B。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）集合部分1、下列命题（1）；（2）；（3）；（4）正确的是 ；错误的是 。2、计算一下幂集（1）P（）；（2）P（）；（3）P（，）；（4）P（1，2，3）3、证明（1）（A-B）B=AB；4、化简 （ABC）（AB）- （A（B - C）A5、已知：AB=AC，证明：A = B6、求在1到1000之间不能被5和6，也不能被8整除的数的个数7、某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另一种球（指篮球或排球），求不会打这三种球的人数。8、设F表示一年级大学生的集合，S表示二年级大学生的集合，R表示计算机科学系学生的集合，M表示数学系学生的集合，T表示选修离散数学的学生的集合，L表示爱好文学的学生的集合，P表示爱好体育运动的学生的集合，则下列各句子所对应的集合表达式分别是：（1）所有计算机科学系二年级的学生都选修离散数学。A（2）数学系的学生或者爱好文学或者爱好体育运动。B（3）数学系一年级的学生都没有选修离散数学。C（4）只有一、二年级的学生才爱好体育运动。D（5）除去数学系和计算机科学系二年级的学生外都不选修离散数学。EA、B、C、D、E：T（MR）S；RST；（MF）T =；MLP；PFS；S -（MR）P9、设S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5。确定在以下条件下X可能与S1,S5中哪个集合相等。（1）若XS5 = ，则A（2）若XS4但XS2 = ，则B（3）若XS1但XS3，则C（4）若X - S3= ，则D（5）若XS3但XS1，则EA、B、C、D、E：X=S2或者S3；X= S4或者S5；X=S1，S2或者S4；X与其中任何集合都不等；X=S2；X=S5；X=S3或者S5；X=S2或者S4；10、设A、B、C为任意集合，判断下述命题是否恒真，如果恒真给出证明，否则举出反例。（1）AB=ACB=C（2）AB=AB=（3）A（B - C）=（AB）-（AC）（4）（AB）（B - A）= B11、设A、B为集合，试确定下列各式成立的充分必要条件：（1）A B = B（2）A B = B - A（3）AB = AB12、求使得以下集合等式成立时，a，b，c，d应该满足的条件：（1）a，b=a，b，c（2）a，b，a=a，b（3）a，b，c=a，d（4）a，b，c=b（5）a，b，c=13、计算AB、AB、A - B、AB（1）A=a，b，c，B=c，d（2）A=a，b，c，c，a，b，B=a，b，c，b（3）A=x|xNx3，B=x|xNx2（4）A=x|xRx1，B=x|xZx1（5）A=x|xZx0，B=x|xZx214、设|A|=3，|P（A）|=64，|P（AB）|=256，求：|B|，|AB|，|A - B|，|AB|15、设A=1，2，求：P（A）A16、设A、B、C、D为任意集合，判断以下等式是否成立，若成立给与证明，否则，举出反例。（1）（AB）（CD）=（AC）（BD）（2）（AB）（CD）=（AC）（BD）（3）（A - B）（C - D）=（A - C）（B - D）（4）（AB）（CD）=（AC）（BD）17、设F、G是N上的关系，其定义为：F=|x，yNy =x2；G=|x，yNy =x+1；求：G-1、FG、GF、F1，2、F1，218、设F=，求：FF，Fa，Fa。19、设A=a，b，c，d，R=，。给出R、r（R）、s（R）、t（R）的关系图。20、设A=1，2，3，求出A上的所有的等价关系21、设A=1，2，3，11，12，R为A上整除关系，画出哈斯图。22、画出的哈斯图。23、R是X上的二元关系，对于xX定义集合：R（x）=y|xRy显然R（x） X。如果X=-4，-3，-2，-1，0，1，2，3，4，且令R1=|x，yXx y，R2=|x，yXy -1 x y +2，R3=|x，yXx2 y，则下列集合满足（1）R1（0）=A（2）R2（0）=B（3）R3（3）=C（4）R1（1）=D（5）R2（-1）=EA、B、C、D、E：；-4，-3，-2，-1；-2，-1；-1，0，1；-1，0；1，2，3；2，3，4；0，1，2，3；1，2，3，4；以上结果都不对24、设S=1，2，3，定义SS上的等价关系R，SS有：a + d = b + c则由R产生了SS的一个划分。在该划分中共有A 个划分块，其中最大的块有B 个元素，并且含有元素C 。最小的划分块有D 块，每块含有E 个元素。A、B、D、E：1；2；3；4；5；6；9；C：1；25、设S=0，1，F是S中的字符构成的长度不超过4的串的集合，即F=，0，1，00，01， ，1111，其中表示空串。在F上定义偏序关系R：x，yF，有Rx 是y的前缀。例如，00是001的前缀，但01不是001的前缀。（1）偏序集的哈斯图是A；（2）的极小元是B；（3）的最大元是C；（4）GF，G=101，1001，则G的最小上界是D ，最大下届是E 。A：链；树；既不是链，也不是树；B、C、D、E：；0；0、1和；不存在；10；1；111126、设S=1，2，则S上可定义A 个不同的二元关系，其中B 个等价关系，C 个偏序关系，Is是D ，是E 。A、B、C：1；2；3；4；8；16；D、E：等价关系但不是偏序关系；偏序关系但不是等价关系；等价关系和偏序关系；既不是等价关系也不是偏序关系；27、下面给定5个函数，其中单射而非满射的有A ，满射而非单射的有B ，双射的有C ，既不单射，又不满射的有D 。设R为实数集合，Z为整数集合，R+、Z+分别表示正实数和正整数集合。f：RR，f（x）= -x2+2x-1；f：RZ+，f（x）=lnx；f：RZ，f（x）=，表示不大于x的最大整数；f：RR，f（x）=2 x+1；f：R+R+，f（x）=28、对于给定集合A和B，构造从A到B的双射函数。（1）A=Z，B=N，其中Z，N分别表示整数集和自然数集；（2）A=，2，B=-1，1的实数区间29、（1）设S=1，2，R为S上的二元关系，且xRy。如果R=Is，则A ；如果R是数的小于等于关系，则B ；如果R=Es，则C 。（2）设有序对 与有序对相等，则x=D ，y=E 。A、B、C：x与y可任意选择1或2；x=1，y=1；x=1，y=1或2；x=y=2；x=2，y=2；x=y=1或x=y=2；x=1，y=2；x=2，y=1；D、E：3；9； -230、设S=，R为S上的关系，其关系矩阵是，则（1）R的关系表达式是A；（2）domR=B ；ranR=C ；（3）RR中有D 个有序对；（4）R-1的关系图中有E 个环。A：，；，；B、C：1，2，3，4；1，2，4；1，4；1，3，4；D、E：1；3；6；731、设S=1，2，9，10，是S上的整除关系，则的哈斯图是A ，其中最大元是B ，最小元是C ，最小上界是D ，最大下界是E 。A：一棵树；一条链；以上都不对；B、C、D、E：；1；10；6，7，8，9，10；6；0；不存在32、设R的关系图如所示，试给出r（R）、s（R）、t（R）的关系图。33、画出下列集合关于整除关系的哈斯图。（1）1，2，3，4，6，8，12，24（2）1，2，8，934、设A=a，b，B=0，1，（1）求P（A）和BA；（2）构造一个从P（A）到BA的双射函数。代数系统部分1、设Z+=x|xZx0，*表示求两个数的最小公倍数的运算，则（1）4*6=A；（2）*在Z+上B；（3）对于*运算的幺元是C ，零元是D ；（4）在Z+中E；A：24；12；B：只满足交换率；只满足结合律；满足交换率、结合律和幂等律；C、D：0；1；不存在；E：不存在逆元；只有唯一的逆元2、在有理数集合Q上定义二元运算*，x，yQ有 x * y = x + y - xy则（1）2*（-5）=A ，7*1/2 = B 。（2）*在Q上是C；（3）关于*的幺元是D；（4）Q中满足E；A、B：4；7；-13；C：可结合的；不可结合的；D：1；0；E：所有的元素都有逆元；只有唯一的逆元；xQ，x1时，有逆元x-1。3、设V1=，V2=，其中S1=a，b，c，d，S2=0，1，2，3。和*由运算表1和表2给出。定义同态：S1S2，且 （a）=0，（b）=1，（c）=0，（d）=1，则（1）V1中的运算A ，其幺元是B ，V2中的运算*C ；（2）是D ，V1在下的同态像是E ；A、C：满足交换律，不满足结合律；不满足交换律，满足结合律；满足交换律，满足结合律；B：a；d；D：单同态；满同态；以上两者都不是；E：；4、设V1=，其中xy表示取x和y之中较大的数，V2=，其中x*y表示取x和y之中较小的数。（1）V1含有A 个子代数，其中平凡的真子代数有B 个；V2含有C 个平凡的子代数。（2）积代数V1V2中有D 个元素，其幺元是E 。A、B、C、D：0；1；2；3；4；5；6；E：；5、设S=a，b，则S上可以定义A 个二元运算，其中有4个运算f1，f2，f3，f4，其运算表如下：则只有B 满足交换律，C 满足幂等律，D 有幺元，E 有零元。A：4；8；16；2；B、C、D、E：f1和f2；f1、f2和f3；f3和f4；f4；f1；f2；6、设S=1，2，9，10，问下面定义的二元运算*是否为S上的二元运算？（1）x*y = gcd（x，y），x与y的最大公约数；（2）x*y = lcm（x，y），x与y的最小公倍数；（3）x*y =大于等于xy的最小整数；（4）x*y =max（x，y）；（5）x*y =质数P的个数，其中xpy。7、设V = 是代数系统，其中R*为非零实数的集合。分别对下述小题讨论运算是否可交换、可结合，并求幺元和所有可逆元素的逆元。8、某二进制通信编码由4个数据位x1、x2、x3、x4和3个校验位x5、x6、x7构成，它们的关系如下： x5=x1x2x3；x6=x1x2x4；x7=x1x3x4；其中为异或运算。（1）设S为所有满足上述关系的码字的集合，且x，yS，有xy =(x1y1,x2y2，,x7y7)，那么是一个A 。（2）设x，yS，定义H（x，y）=，那么当xy时，H（x，y）B 。（3）使用该种码可查出接收码中包含的所有kC 位错误。（4）使用该种码可纠正接收码中包含的所有kD 位错误。（5）如果接收到1000011，且知有一位出错，那么出错位是第E 位。A：半群，但不是群；群；环，但不是域；域；前4种都不对；B、C、D、E：1；2；3；4；5；6；7；0；9、对以下定义的集合和运算判断它们是不是代数系统。如果是，是哪一种？（1）S1=1，1/2，2，1/3，3，1/4，4，*为普通乘法，则S1是A ；（2）S2=a1，a2，an，n2，aiR，i=1，2，n， ai，ajS2，有aiaj=ai，则S2是B ；（3）S3=0，1，*为普通乘法，则S3是C ；（4）S4=1，2，3，6，为整除关系，则S4是D ；（5）S5=0，1，+、*分别为模2加法和乘法，则S5是E 。A、B、C、D、E：半群，但不是独异点；是独异点，但不是群；群；环，但不是域；域；格，但不是布尔代数；布尔代数；代数系统，但不是以上7种；不是代数系统；10、图6-5给出一个格L，则（1）L是A 元格；（2）L是B ；（3）b的补元是C ，a的补元是D ，1的补元是E 。A：5；6；B：分配格；有补格；布尔格；以上都不对；C、D、E：不存在；c和d；0；c；11、设是布尔代数，（1）a，bB，公式f为b（a（a（bb）,在B中化简f；（2）在B中等式（ab）（ab）=0 成立的条件是什么？12、对以下定义的集合和运算判断它们能否构成代数系统？如果能，请说明是构成哪一种代数系统？（1）S1=0，1，2，n，+为普通加法，则S1是A ；（2）S2=1/2，0，2，*为普通乘法，则S2是B ；（3）S3=0，1，2，n-1，n为任意给定的正整数，且n2，*为模n乘法，为模n加法，则S3是C ；（4）S4=0，1，2，3，为小于等于关系，则S4是D ；（5）S5=Mn（R），+为矩阵加法，则S5是E ；A、B、C、D、E：半群，不是独异点；独异点，不是群；群；环，不一定是域；域；格，不是布尔代数；布尔代数；代数系统，不是以上7种；不是代数系统；13、（1）设G=0，1，2，3，若为模4乘法，则构成A ；（2）若为模4加法，则是B 阶群，且是C 。G中的2阶元是D ，4阶元是E 。A：群；半群，不是群；B：有限；无限；C：Klein群；置换群；循环群；D、E：0；1和3；2；14、（1）设是布尔代数，则L中的运算和A ，运算的幺元是B ，零元是C ，最小的子布尔代数是由集合D 构成；（2）在布尔代数L中的表达式 （ab）（abc）（bc）的等价式是E ；A：适合德.摩根律、幂等律、消去律和结合律；适合德.摩根律、幂等律、分配律和结合律；适合结合律、交换律、消去律和分配律；B、C：0；1；D：1；0，1；E：b（ac）；（ac）（ab）；（ab）（abc）（bc）；15、下列各集合对于整除关系都构成偏序集，判断哪些偏序集是格？（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；16、设A=1，2，3，4，5，构成群，其中为集合的对称差。（1）求解方程1，3X=3，4，5；（2）令B=1，4，5，求由B生成的循环子群；17、设A=1，2，5，10，11，22，55，110是110的正因子集，构成偏序集，其中为整除关系。（1）画出偏序集的哈斯图；（2）说明该偏序集是否构成布尔代数，为什么？18、在图6-7所示的3个有界格中哪些元素有补元？如果有，请指出该元素的所有的补元。P154图论部分1、（1）（3，3，2，3）、（5，2，3，1，4）能成为图的度数序列吗？为什么？（2）已知图G有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？2、（1）画出4个顶点3条边的所有可能非同构的无向简单图；（2）画出3个顶点3条边的所有可能非同构的有向简单图；3、给定下列各图：（1）G1=，其中，V1=（a，b，c，d，e），E1=（a，b），（b，c），（c，d），（a，e）；（2）G2=，其中，V2=V1，E2=（a，b），（b，e），（e，b），（a，e），（d，e）；（3）G3=，其中，V3=V1，E3=（a，b），（b，e），（e，d），（c，c）；（4）G4=，其中，V4=V1，E4=，；（5）G5=，其中，V5=V1，E5=，；（6）G6=，其中，V6=V1，E6=，；在以上6个图中，A 为简单图，B 为多重图。A：（1），（3），（6）；（3），（4），（5）；（1），（2），（4）；（1），（4）B：（2），（4），（5）；（2），（5）；（4），（5）4、给定下列各顶点度数序列：（1）（2，2，2，2，2）；（2）（1，1，2，2，3）；（3）（1，1，2，2，2）；（4）（0，1，3，3，3）；（5）（1，3，4，4，5）；以上5组数中，A 可以构成无向简单图的度数序列。A：（1），（3），（4）；（1），（2）；（1），（3）；（3），（4），（5）；5、完全图K4的所有非同构的生成子图中，0条边的有A 个；1条边的有B 个；2条边的有C 个；3条边的有D 个；4条边的有E 个；5条边的有F 个；6条边的有G 个；A、B、C、D、E、F、G：0；1；2；3；4；5；6、设G为9阶无向图，每个顶点的度数不是5就是6，证明：G中至少有5个6度顶点或者至少6个5度顶点。7、画出5阶7条边的所有非同构的无向简单图。8、下列各组数中，哪些 能构成无向图的度数列？哪些 能构成无向简单图的度数列？（1）1，1，1，2，3；（2）2，2，2，2，2；（3）3，3，3，3；（4）1，2，3，4，5；（5）1，3，3，3；9、设有向简单图D的度数列为2，2，3，3，其中入度列为0，0，2，3，出度列为 。10、设D是4阶有向简单图，度数列为3，3，3，3，它的入度列能为1，1，1，1吗？ （能或者不能）11、下面各无向图中有几个顶点？（1）16条边，每个顶点都是2度顶点；（2）21条边，3个4度顶点，其余都是3度顶点；（3）24条边，各顶点的度数是相同的；12、一个n（n2）阶无向简单图G中，n为奇数，已知G中有r 个奇数度顶点，问G的补图中有几个奇数度顶点？13、画出K4的所有非同构的字图，其中有几个是生成子图？生成子图中有几个是连通图？14、画出3阶有向完全图所有非同构的子图，问其中有几个是生成子图？生成子图中又有几个是自补图？15、设G1、G2、G3均为4阶无向简单图，它们均有两条边，它们能彼此均非同构吗？为什么？16、在K6的边上涂上红色或蓝色。证明对于任意一种随意的涂法，总存在红色K3或者蓝色K3。17、（1）非同构的无向的4阶自补图有A 个；（2）非同构的无向的5阶自补图有B 个；A、B：0；1；2；3；18、给定有向带权图如图所示，P175图中b到a的最短路径的权为A ；b到d的最短路径的权为B ；b 到e的最短路径的权为C ；b到g的最短路径的权为D ；A、B、C、D：4；5；6；7；8；9；10；19、某中学有3个课外小组：物理组、化学组、生物组。今有张、王、李、赵、陈5名同学。若已知：（1）张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员；（2）张为物理组成员，王、李、赵为化学组成员，王、李、赵、陈为生物组成员；（3）张为物理组和化学组成员，王、李、赵、陈为生物组成员；问在以上3中情况下能否各选出3名不兼职的组长？20、在图8-17所示的各图中，A 为欧拉图，B 为哈密顿图。P185A、B：（a），（b），（c）；（d），（e），（f）；（c），（e）；（b），（c），（d），（e），（f）；（b），（c），（d），（e）；21、在图8-18所示的各图中，是二部图的为A ，在二部图中存在完美匹配的是B ，它的匹配数是C 。P186A、B：（a）；（b）；（c）；（d）；（e）；（f）；（a），（b）；（b），（f）；（c），（d），（e）；（d），（e）；C：1；2；3；4；22、图8-19所示的平面嵌入中，面数为A ，次数最高的面的次数为B ，次数最低的面的次数为C ，总次数为D 。A、B、C：5；6；7；8；9；10；11；1；D：24；26；28；23、画出完全二部图K13，K24，K22。24、完全二部图Krs中，边数为 ，匹配数1为 。25、今有工人甲、乙、丙去完成三项任务a、b、c。已知甲能胜任a、b、c三项任务；乙能胜任a、b两项任务；丙能胜任b、c两项任务。你能给出一种安排方案，使每个工人各去完成一项他们能胜任的任务吗？26、画一个无向欧拉图，使它具有：（1）偶数个顶点，偶数条边；（2）奇数个顶点，奇数条边；（3）偶数个顶点，奇数条边；（4）奇数个顶点，偶数条边；27、画一个无向图，使它是：（1）是欧拉图，是哈密顿图；（2）是欧拉图，不是哈密顿图；（3）不是欧拉图，是哈密顿图；（4）不是欧拉图，不是哈密顿图；28、今有a、b、c、d、e、f、g7个人，已知如下事实：a：会讲英语；b：会讲英语和汉语；c：会讲英语、意大利语和俄语；d：会讲日语和汉语；e：会讲德语和意大利语；f：会讲法语、日语和俄语；g：会讲法语和德语；试问：这7个人要围成一圈，应如何排座位，才能使每个人都能和他身边（相邻）的人交谈？29、彼得森图如图8-23所示。证明它不是二部图，也不是欧拉图，更不是平面图。P18930、证明图8-24所示图G是哈密顿图，但不是平面图。P18931、图8-25所示图G为平面图，试给出它的一个平面嵌入，它是极大平面图吗？P18932、（1）完全图Kn（n1）都是欧拉图，这个命题真值为A；（2）完全图Kn（n1）都是哈密顿图，这个命题真值为B；（3）完全二部图Knm（n1，m1）都是欧拉图，这个命题真值为C；（4）完全二部图Knm（n1，m1）都是哈密顿图，这个命题真值为D；A、B、C、D：真；假；33、6个顶点11条边的所有可能的非同构的连通的简单的非平面图有A 个，其中有B 个含子图K33，有C 个含与K5同胚的子图。A、B、C：1；2；3；4；5；6；7；8；34、图9-3所示的图G中，实线边所构成的子图是G的一颗生成树T，求T对应的基本回路和基本回路系统，基本割集和基本割集系统P19335、（1）求带权为1、3、4、5、6的最优二元树；（2）求带权为2、3、5、7、8、8的最优二元树；36、计算非同构无向树的个数。（1）2个顶点非同构无向树的有A 颗；（2）4个顶点非同构无向树的有B 颗；（3）6个顶点非同构无向树的有C 颗；（4）7个顶点非同构无向树的有D 颗；A、B、C、D：1；2；4；6；7；8；9；10；11；12；37、（1）在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，则该树有A 个4度顶点；（2）在一棵树中有2个4度顶点，3个3度顶点，其余都是树叶，则该树有B 片树叶；（3）一棵树中有ni个顶点的度数为i，i=2，3，k，而其余的顶点都是树叶，则该树中有C 片树叶。A、 B：1；2；3；4；5；6；7；8；9；10；C：；38、图9-16给出两个带权图。P200（1）图（a）中最小生成树的权为A；（2）图（b）中最小生成树的权为B；10；14；15；21；22；24；25；26；27；28；39、用Huffman算法求带权为2、3、5、7、8的最优二元树T。（1）T的权为A ；（2）T中有B 片树叶，C 个2度顶点，D 个3度顶点，E 个4度顶点，（3）T的高度为F 。A：40；45；50；55；60；B、C、D、E、F：0；1；2；3；4；5；6；7；8；40、（1）求一个带权为1、2、3、4、5、5.5、7.5的最优三元树，其权为A；（2）求一个带权为1.5、2.5、3、4、5、6的最优三元树，其权为B；A、B：30；35；37；45；47；48；48.5；50；52；55；41、设无向树T有3个3度、2个2度顶点，其余顶点都是树叶，树叶顶点数为 。42、设无向树T有7片树叶，其余顶点的度数均为3，求T中3度顶点数？画出所有具有此种度数的非同构的无向树。45、画出度数列为1，1，1，1，2，2，4的所有非同构的7阶无向树。46、在图9-20所示的无向图G中，实线边所示的子图为G的一棵生成树T，求G对应于T的基本回路系统和基本割集系统。P20347、求图9-21所示两个带权图的最小生成树，并计算它们的权。P20348、计算非同构的根数的个数。（1）2个顶点非同构的根数为A 个；（2）3个顶点非同构的根数为B 个；（3）4个顶点非同构的根数为C 个；（4）5个顶点非同构的根数为D 个；A、B、C、D：1；2；3；4；5；6；7；8；9；10；