离散数学总复习资料4

1、离散数学总复习资料一、鸽笼原理与容斥原理1求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于。证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于。#2对一列个不同整数，任意排列，证明一定存在长为的上升子序列或下降子序列。证：设此序列为：，从开始上升子序列最长的长度为，下降子序列最长的长度为，每一个都对应了。若不存在长为的上升子序列或下降子序列，那么，形如的不同点对至多有个，而有个，则由鸽笼原理知，必有同时对应，由于，若，则至少比大1，若，则至少比大1，这均与矛盾。故原命题成立。#3求中不被3、4、5整

2、除的个数。解： 设表示中被3整除的数的集合，表示中被4整除的数的集合，表示中被5整除的数的集合，则， ，进而有故有即中不被3、4、5整除的个数为40。#4有100个学生，其中60个爱看小说，30个爱下棋，10个既爱看小说，又爱下棋，5个既爱看小说，又爱跳舞，没有既爱下棋，又爱跳舞的，三种活动都不爱的有10个，问有几个学生爱跳舞？解：设全体学生的集合为，爱看小说的学生集合为，爱下棋的学生集合为，爱跳舞的学生集合为，则依题意有， ，从而，。另一方面，根据容斥原理，我们有，即有，故，即有15个学生爱跳舞。#二、数理逻辑5求的主析取、主合取范式。解：取真为：(1,1)，(0,0)，(0,1)；故的主析

3、取范式为；取假为：(1,0)；故的主合取范式为：。6求的主析取、主合取范式。解：取真为：(1,1,1)，(0,0,1)，(0,1,1)，(1,0,0)，(1,0,1)；故的主析取范式为； 取假为：(1,1,0),(0,1,0),(0,0,0)；故的主合取范式为：。7（1）将式子“并非跑的最快的马吃的最多”翻译成用谓词和量词表达的逻辑式子。(2)将式子“爱因斯坦于1952年写完狭义与广义相对论浅说”翻译成用谓词和量词表达的逻辑式子。解：（1）：马； ：跑的最快的马； ：吃的最多的马。上式表示为： （2）设：爱因斯坦； ：1952； ：狭义与广义相对论浅说； ：于年写完；则原式子可翻译成逻辑式子。

4、8求下述公式的前束范式和Skolem标准形。解：=故该公式的前束范式为；Skolem标准形为。#9将下列命题符号化，并证明其论证是否正确。（1）不存在白色的乌鸦；北京鸭是白色的。因此，北京鸭不是乌鸦。解：令是白色的；：是乌鸦；：是北京鸭。则上述命题可符号化为：下面，我们证明上述命题是正确的。（1） （P）（2） （US）（3） （CP）（4） （分离规则）（5） （量词转换律）（6） （US）（7） （T，（4）（8） （9） （UG）#（2）符号化下列语句，并用演绎法加以证明。 大熊猫都产在中国，欢欢是大熊猫，所以，欢欢产在中国。解：令是大熊猫；：产在中国；：欢欢。则上述命题可符号化为： 下

5、面，我们证明上述命题是正确的。（1） （P） （2） （US） （3） （P） （4） （分离规则） 三、二元关系10(1)举出正整数集上一种关系,它是等价关系但不是偏序关系;(2) 举出正整数集上一种关系,它是偏序关系但不是等价关系。(3)画出集合上整除关系的Hasse图。（4）等价关系与划分关系解：（1）正整数集上模3的同余关系。（2）正整数集上的整除关系。（3） 24 12 8 6 4 3 2 111(1)举出正整数集上一种二元关系,它是等价关系又是偏序关系;(2) 画出的Hasse图 ,其中。解：（1）正整数集上的恒等关系。（2） 6 4 3 2 112设，定义上的一个二元关系如下：（

6、1）画出的关系图，并写出的关系矩阵；（2）求，；（3）求，。解：（略）13（1）设A=1,2,3，R=<1,2>,<2,3>，求R的闭包关系r(R)，s(R)，t(R)，并画出R，r(R)，s(R)，t(R)的关系图。（2）设是正整数集关于整除关系作成的偏序集，的子集，求的极小元、极大元、上界、下界、最小上界、最大下界。解：（略）（3）设A=1, 2, 3, 4, 5，找出A上的等价关系R，此关系R能够产生划分：1, 2, 3, 4, 5，并画出R的关系图解：R=<1, 1>, <1, 2>, <2, 1>, <2, 2>

7、, <4, 4>, <4, 5>, <5, 4>, <5, 5>, <3, 3> 42153v3四图论14（1）画一个图，使它既有欧拉回路，又有哈密顿回路；（2）画一个回路图，使它既无欧拉回路，又无哈密顿回路。解：（1） （2） 或 15（1）画一个图，使它有欧拉回路，无哈密顿回路；（2）画一个回路图，使它无欧拉回路，有哈密顿回路。解：（1） （2） 16证明小于30条边的简单平面图至少有一个顶点的度数小于5。证：（反证法）假设小于30条边的简单平面图中每一个顶点的度数大于等于5，从而此时顶点数与边数满足；另一方面，由于此时图的每一个

8、区域至少由3条边围成，从而由Euler公式推论知，此时顶点数与边数满足；故有，进而有，这与已知条件产生矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于5。#17证明具有6个顶点和12条边的连通简单平面图，它的每个区域都是由三条边围成。证： 由题意及欧拉公式知，其区域数为。若有一个区域不是由三条边围成，则至少由4条边围成，从而8个区域至少需要25条边才能围成，即图中的边数不少于25/2=12.5, 这与已知条件12条边产生矛盾，故它的每个区域都是由三条边围成。#18设， 任意顶点的次（度）不少于2，且任意两个相邻区域只有一条公共边的简单平面图，证明其着色数不少于3。解：（略）19用算法寻

9、找下图中顶点到的最短路径。 g 2 h 2 i 2 j 2 1 1 2 2 1 d 2 e 2 f 2 1 1 2 b 1 c 2 1 a解：从出发第一短的点为，距离为1，路径为；从出发第二短的点为或，距离为2，路径为或；从出发第四短的点为或，距离为3，路径为或；从出发第五短的点为或或，距离为4，路径为或（或）或。故顶点到的最短路径为。#20求分别用前序、中序、后序遍历（周游）下图。 6 2 10 1 4 7 11 3 5 9 8 解：前序6-2-1-4-3-5-10-7-9-8-11 中序1-2-3-4-5-6-7-8-9-10-11 后序1-3-5-4-2-8-9-7-11-10-6 21

10、求出下图的最小生成树。 21 1 2 1 22 1 3 3 2解： 1 1 1 1 1 1 2 1 或 1 2 2 2 22设7个字母在通讯中出现的频率如下， ，编一个相应的二元前缀码，使通讯中出现的符号尽可能少，并画出对应的二元树。解：该二元前缀码对应的Huffman树为： 100 40 60 20 20 25 35 10 10 10 15 5 5 从而对应的二元前缀码为：。#23给定树叶的权分别为1，4，9，16，25，36，49，64，81，100，试构造一棵最优树。解：（略）24.握手原理及其应用。25.将字母a，a，a，a，a，b，c，d，e进行排列，使任两个a都不相邻，有多少种排法

11、？若b，c，d，e中任两个字母都不相邻，又有多少种排法？解：将字母a，a，a，a，a，b，c，d，e进行排列，使任两个a都不相邻，即在连写aaaaa的aa中间共4个空隙中插入b，c，d，e，因此共有种排法；若将字母a，a，a，a，a，b，c，d，e进行排列，其中b，c，d，e中任两个字母都不相邻，即在连写aaaaa的aa中间及头尾共6个空隙中插入b，c，d，e，因此此时共有种排法。26.设简单图G=<V, E>，如下图所示，求：(1) 邻接矩阵，(2) 图G中长度为2通路的个数和回路的总数v3v2v1v4解：(1) 邻接矩阵： (2) ， ， G中长度为3的通路有21条，回路有9条

12、27命题“福州是福建的省会当且仅当鸟会飞”的真值为 真 28由下面的置换写出相应的置换的积 (1,4)(2,6,5)(3) 。29. 令A=1, 2, , 10，则A关于模3的等价关系R的商集为 A/R = 1, 4,7，10, 2, 5, 8, 3, 6，9 30. 给出一个如图所示的有向连通图。 （1）写出它的邻接矩阵 ； （2）写出它的可达矩阵； （3）图中长度为3的路一共有多少条？ 解：（1） 邻接矩阵为 图4 ； （2）可达矩阵为 （3） ， ， 中所有元素之和为32，故有32条长3为的路； 31. 容斥原理指的是 有限集 满足 32.最优树是指含有权值的树叶，若其叶层数为， 最小的二元树33偏序关系与划分的关系为： 一个偏序关系至少可以确定一个划分，一个划分至少可以确定一个偏序关系34.最小生成树是指 连通图中边权之和最小的生成树。 35. 找出一种9个a，9个b，9个c的圆形排列，使由字母（a，b，c）组成，长度为3的27个字的每个字只出现一次。解：以aa，ab，ac，ba，bb，bc，ca，cb，cc为顶点（9个），aaa，aab，aac，aba，abb，abc，aca，acb，acc，baa，bab，bac，bba，bbb，bbc，bca，bcb