2022年离散数学必备知识点总结 2.docx

精品_精品资料_总结 离散数学学问点其次章 命题规律1. ,前键为真,后键为假才为假. < >,相同为真,不同为假.2. 主析取范式：微小项 m 之和.主合取范式：极大项 M之积.3. 求微小项时,命题变元的确定为 1,否定为 0,求极大项时相反.4. 求极大微小项时,每个变元或变元的否定只能显现一次,求微小项时变元不够合取真,求极大项时变元不够析取假.5. 求范式时,为保证编码不错, 命题变元最好按 P,Q,R 的次序依次写.6. 真值表中值为 1 的项为微小项,值为0 的项为极大项.可编辑资料 - - - 欢迎下载精品_精品资料_7.n 个变元共有2 n 个微小项或极大项,这2n 为02n -1刚好为化简完可编辑资料 - - - 欢迎下载精品_精品资料_后的主析取加主合取.8. 永真式没有主合取范式,永假式没有主析取范式.9. 推证包蕴式的方法 => ：真值表法. 分析法假定前键为真推出后键为真,假定前键为假推出后键也为假 10. 命题规律的推理演算方法： P 规章, T 规章真值表法.直接证法.归谬法.附加前提法.第三章 谓词规律1. 一元谓词：谓词只有一个个体,一元谓词描述命题的性质. 多元谓词：谓词有 n 个个体,多元谓词描述个体之间的关系.2. 全称量词用包蕴 ,存在量词用合取 ;可编辑资料 - - - 欢迎下载精品_精品资料_3. 既有存在又有全称量词时,先消存在量词,再消全称量词.第四章集合1.N ,表示自然数集, 1,2,3 ,不包括 0.2. 基：集合 A 中不同元素的个数, |A|.3. 幂集：给定集合 A,以集合 A 的全部子集为元素组成的集合, PA .可编辑资料 - - - 欢迎下载精品_精品资料_4. 如集合 A 有 n 个元素,幂集 PA 有 2n 个元素, |PA|=2| A| = 2n .可编辑资料 - - - 欢迎下载精品_精品资料_5. 集合的分划： 等价关系 每一个分划都是由集合 A 的几个子集构成的集合.这几个子集相交为空,相并为全 A .6. 集合的分划与掩盖的比较：分划：每个元素均应显现且仅显现一次在子集中.掩盖：只要求每个元素都显现,没有要求只显现一次.第五章关系1. 如集合 A 有 m 个元素,集合 B 有 n 个元素, 就笛卡尔 A×B 的基数可编辑资料 - - - 欢迎下载精品_精品资料_为 mn, A 到 B 上可以定义2mn 种不同的关系.可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_2. 如集合 A 有 n 个元素,就 |A ×A|=n2 ,A 上有2n2个不同的关系.可编辑资料 - - - 欢迎下载精品_精品资料_3. 全关系的性质：自反性,对称性,传递性.空关系的性质：反自反性,反对称性,传递性.可编辑资料 - - - 欢迎下载精品_精品资料_全封闭环的性质：自反性,对称性,反对称性,传递性.4. 前域domR ：全部元素 x 组成的集合. 后域ranR ：全部元素 y 组成的集合.5. 自反闭包： rR=RU I x ;可编辑资料 - - - 欢迎下载精品_精品资料_对称闭包： sR=RU传递闭包： tR=RUR-1 ;R2 U R3 U可编辑资料 - - - 欢迎下载精品_精品资料_6. 等价关系：集合 A 上的二元关系 R 满意自反性,对称性和传递性, 就 R 称为等价关系.7. 偏序关系：集合 A 上的关系 R 满意自反性,反对称性和传递性, 就称 R 是 A 上的一个偏序关系.8. covA=<x,y>|x,y属于 A, y 盖住 x.9.微小元：集合 A 中没有比它更小的元素如存在可能不唯独.极大元：集合 A 中没有比它更大的元素如存在可能不唯独.最小元：比集合 A 中任何其他元素都小如存在就肯定唯独.最大元：比集合 A 中任何其他元素都大如存在就肯定唯独.10. 前提： B 是 A 的子集上界： A 中的某个元素比 B 中任意元素都大,称这个元素是 B 的上界如存在,可能不唯独 .下界： A 中的某个元素比 B 中任意元素都小,称这个元素是 B 的下界如存在,可能不唯独 .上确界：最小的上界 如存在就肯定唯独 . 下确界：最大的下界 如存在就肯定唯独 .可编辑资料 - - - 欢迎下载精品_精品资料_第六章函数1. 如|X|=m,|Y|=n, 就从 X 到Y 有 2mn 种不同的关系,有nm 种不同的函数.可编辑资料 - - - 欢迎下载精品_精品资料_2. 在一个有 n 个元素的集合上,可以有同的函数,有 n.种不同的双射.2n2种不同的关系,有nn 种不可编辑资料 - - - 欢迎下载精品_精品资料_n3. 如|X|=m,|Y|=n ,且 m<=n ,就从 X 到 Y 有Am 种不同的单射.可编辑资料 - - - 欢迎下载精品_精品资料_4. 单射： f:X-Y ,对任意x1 , x2 属于 X, 且x1 x2 ,如 fx1f x2.可编辑资料 - - - 欢迎下载精品_精品资料_满射： f:X-Y ,对值域中任意一个元素y 在前域中都有一个或多个元素对应.双射： f:X-Y ,如 f 既是单射又是满射,就f 是双射.5. 复合函数： fog=gfx;6. 设函数 f:A-B ,g:B-C ,那么假如 f,g 都是单射,就 fog 也是单射.假如 f,g 都是满射,就 fog 也是满射.假如 f,g 都是双射,就 fog 也是双射.假如 fog 是双射,就 f 是单射, g 是满射.可编辑资料 - - - 欢迎下载精品_精品资料_第七章代数系统1. 二元运算：集合 A 上的二元运算就是A2 到 A 的映射.可编辑资料 - - - 欢迎下载精品_精品资料_2. 集合 A 上可定义的二元运算个数就是从 A×A 到A 上的映射的个数, 即从从 A×A 到 A 上函数的个数,如 |A|=2, 就集合 A 上的二元运算的可编辑资料 - - - 欢迎下载精品_精品资料_个数为 22* 2 = 24 =16 种.3. 判定二元运算的性质方法：封闭性：运算表内只有所给元素.交换律：主对角线两边元素对称相等.幂等律：主对角线上每个元素与所在行列表头元素相同.有幺元：元素所对应的行和列的元素依次与运算表的行和列相同.有零元：元素所对应的行和列的元素都与该元素相同.4.同态映射：<A,*>,<B,>, 满意 fa*b=fafb, 就 f 为由<A,*> 到<B,>的同态映射.如 f 是双射,就称为同构.第八章群1. 广群的性质：封闭性.半群的性质：封闭性,结合律.含幺半群 独异点：封闭性,结合律,有幺元. 群的性质：封闭性,结合律,有幺元,有逆元.2. 群没有零元.3. 阿贝尔群 交换群：封闭性,结合律,有幺元,有逆元,交换律.4. 循环群中幺元不能是生成元.5. 任何一个循环群必定是阿贝尔群.可编辑资料 - - - 欢迎下载精品_精品资料_第十章格与布尔代数1. 格：偏序集合 A 中任意两个元素都有上、下确界.2. 格的基本性质：1) 自反性aa对偶: aa2) 反对称性ab b a=> a=b对偶:ab b a=> a=b3) 传递性ab b c=>ac对偶:ab b c=>ac4) 最大下界描述之一ab a对偶 avb a Abb对偶 avb b5）最大下界描述之二c a,c b=>cab对偶 ca,c b=>cavb6) 结合律abc=abc对偶 avbvc=avbvc7) 等幂律aa=a对偶 ava=a可编辑资料 - - - 欢迎下载精品_精品资料_8) 吸取律aavb=a对偶 avab=a9) ab <=>ab=aavb=b10) ac,bd=>ab cdavb cvd11) 保序性bc=>ab acavb avc 12 ） 安排不等式avbc avbavc对偶 abvc abvac 13 ）模不等式ac<=>avbc avbc3. 安排格：满意 abvc=abvac 和 avbc=avbavc .4. 安排格的充要条件：该格没有任何子格与钻石格或五环格同构.5. 链格肯定是安排格,安排格必定是模格.6. 全上界：集合 A 中的某个元素 a 大于等于该集合中的任何元素, 就称 a 为格<A,<=> 的全上界,记为 1.如存在就唯独 全下界：集合 A 中的某个元素 b 小于等于该集合中的任何元素, 就称 b 为格<A,<=> 的全下界,记为 0.如存在就唯独 7. 有界格：有全上界和全下界的格称为有界格,即有0 和 1 的格.8. 补元：在有界格内,假如 ab=0,avb=1 ,就 a 和 b 互为补元.9. 有补格：在有界格内,每个元素都至少有一个补元.10. 有补安排格 布尔格：既是有补格,又是安排格.可编辑资料 - - - 欢迎下载精品_精品资料_11. 布尔代数：一个有补安排格称为布尔代数.第十一章图论1. 邻接：两点之间有边连接,就点与点邻接.2. 关联：两点之间有边连接,就这两点与边关联.3. 平凡图：只有一个孤立点构成的图.4. 简洁图：不含平行边和环的图.5. 无向完全图：n 个节点任意两个节点之间都有边相连的简洁无向图. 有向完全图 :n 个节点任意两个节点之间都有边相连的简洁有向图.6. 无向完全图有 nn-1/2 条边,有向完全图有 nn-1 条边. 7.r- 正就图：每个节点度数均为 r 的图.8. 握手定理：节点度数的总和等于边的两倍.9. 任何图中,度数为奇数的节点个数必定是偶数个.10. 任何有向图中,全部节点入度之和等于全部节点的出度之和.11. 每个节点的度数至少为2 的图必定包含一条回路.可编辑资料 - - - 欢迎下载精品_精品资料_12. 可达：对于图中的两个节点vi , v j,如存在连接vi 到vj的路,就称 vi可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_与vj 相互可达,也称vi 与vj是连通的.在有向图中,如存在vi 到vj 的可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_路,就称vi 到vj可达.可编辑资料 - - - 欢迎下载精品_精品资料_13. 强连通：有向图章任意两节点相互可达.单向连通：图中两节点至少有一个方向可达.可编辑资料 - - - 欢迎下载精品_精品资料_弱连通：无向图的连通. 弱连通必定是单向连通 14. 点割集：删去图中的某些点后所得的子图不连通了,假如删去其他几个点后子图之间仍是连通的,就这些点组成的集合称为点割集.割点：假如一个点构成点割集,即删去图中的一个点后所得子图是不连通的,就该点称为割点.可编辑资料 - - - 欢迎下载精品_精品资料_15. 关联矩阵： MG , mij是 vi 与ej关联的次数,节点为行,边为列.可编辑资料 - - - 欢迎下载精品_精品资料_无向图：点与边无关系关联数为0,有关系为 1,有环为 2. 有向图：点与边无关系关联数为0,有关系起点为 1 终点为 -1, 关联矩阵的特点：无向图：行：每个节点关联的边,即节点的度.列：每条边关联的节点. 有向图：全部的入度 1=全部的出度 0;16. 邻接矩阵： AG , aij 是vi 邻接到 vj 的边的数目,点为行,点为列.17. 可达矩阵： PG ,至少存在一条回路的矩阵,点为行,点为列.可编辑资料 - - - 欢迎下载精品_精品资料_PG=AG+A2 G+A3 G+A4 G可编辑资料 - - - 欢迎下载精品_精品资料_可达矩阵的特点： 说明图中任意两节点之间是否至少存在一条路, 以及在任何节点上是否存在回路.AG 中全部数的和：表示图中路径长度为1 的通路条数.A2 G 中全部数的和：表示图中路径长度为2 的通路条数.A3 G 中全部数的和：表示图中路径长度为3 的通路条数.可编辑资料 - - - 欢迎下载精品_精品资料_A4 G 中全部数的和：表示图中路径长度为4 的通路条数.PG 中主对角线全部数的和：表示图中的回路条数.18. 布尔矩阵： BG , vi 到vj 有路为 1,无路就为 0,点为行, 点为列.19. 代价矩阵：邻接矩阵元素为 1 的用权值表示,为 0 的用无穷大表示,节点自身到自身的权值为 0.20. 生成树：只拜访每个节点一次,经过的节点和边构成的子图.21. 构造生成树的两种方法：深度优先.广度优先. 深度优先：选定起始点 v0 .可编辑资料 - - - 欢迎下载精品_精品资料_挑选一个与v0 邻接且未被拜访过的节点v1 .可编辑资料 - - - 欢迎下载精品_精品资料_从 v1 动身按邻接方向连续拜访,当遇到一个节点所有邻接点均已被拜访时, 回到该节点的前一个点, 再寻求未被拜访过的邻接点,直到全部节点都被拜访过一次.广度优先：选定起始点 v0 .可编辑资料 - - - 欢迎下载精品_精品资料_拜访与v0 邻接的全部节点v1 , v2 , , vk ,这些作为可编辑资料 - - - 欢迎下载精品_精品资料_第一层节点.在第一层节点中选定一个节点 v1 为起点.重复,直到全部节点都被拜访过一次.22. 最小生成树：具有最小权值 T 的生成树.23. 构造最小生成树的三种方法：克鲁斯卡尔方法.管梅谷算法.普利姆算法.可编辑资料 - - - 欢迎下载精品_精品资料_（1） 克鲁斯卡尔方法将全部权值按从小到大排列.先画权值最小的边,然后去掉其边值.重新按小到大排序.再画权值最小的边,如最小的边有几条相同的,挑选时要满意不能显现回路,然后去掉其边值.重新按小到大排序.重复,直到全部节点都被拜访过一次.（2） 管梅谷算法 破圈法在图中取一回路,去掉回路中最大权值的边得一子图.在子图中再取一回路, 去掉回路中最大权值的边再得一子图.重复,直到全部节点都被拜访过一次.（3） 普利姆算法可编辑资料 - - - 欢迎下载精品_精品资料_在图中任取一点为起点v1,连接边值最小的邻接点v2 .可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_以邻接点v2 为起点,找到v2 邻接的最小边值,假如最小边值可编辑资料 - - - 欢迎下载精品_精品资料_比v1 邻接的全部边值都小 除已连接的边值 ,直接连接,否就退回 v1 ,连接 v1 现在的最小边值 除已连接的边值 .重复操作,直到全部节点都被拜访过一次.24. 关键路径例 2 求PERT 图中各顶点的最早完成时间 , 最晚完成时间 , 缓冲时间及关键路径 .解：最早完成时间TEv1=0 TEv2=max0+1=1可编辑资料 - - - 欢迎下载精品_精品资料_TEv3=max0+2,1+0=2 TEv4=max0+3,2+2=4 TEv5=max1+3,4+4=8 TEv6=max2+4,8+1=9 TEv7=max1+4,2+4=6 TEv8=max9+1,6+6=12最晚完成时间TLv8=12 TLv7=min12-6=6 TLv6=min12-1=11 TLv5=min11-1=10 TLv4=min10-4=6TLv3=min6-2,11-4,6-4=2TLv2=min2-0,10-3,6-4=2TLv1=min2-1,2-2,6-3=0缓冲时间TSv1=0-0=0 TSv2=2-1=1 TSv3=2-2=0 TSv4=6-4=2 TSv5=10-8=2 TSv6=11-9=2可编辑资料 - - - 欢迎下载精品_精品资料_TSv7=6-6=0 TSv8=12-12=0关键路径 :v1-v3-v7-v825. 欧拉路：经过图中每条边一次且仅一次的通路. 欧拉回路：经过图中每条边一次且仅一次的回路. 欧拉图：具有欧拉回路的图.单向欧拉路：经过有向图中每条边一次且仅一次的单向路.欧拉单向回路：经过有向图中每条边一次且仅一次的单向回路.26.（ 1）无向图中存在欧拉路的充要条件：连通图.有 0 个或 2 个奇数度节点.（2） 无向图中存在欧拉回路的充要条件：连通图.全部节点度数均为偶数.（3） 连通有向图含有单向欧拉路的充要条件：除两个节点外,每个节点入度 =出度.这两个节点中, 一个节点的入度比出度多 1,另一个节点的入.可编辑资料 - - - 欢迎下载精品_精品资料_度比出度少 1.（ 4）连通有向图含有单向欧拉回路的充要条件： 图中每个节点的出度 =入度.27. 哈密顿路：经过图中每个节点一次且仅一次的通路. 哈密顿回路：经过图中每个节点一次且仅一次的回路. 哈密顿图：具有哈密顿回路的图.28. 判定哈密顿图（没有充要条件） 必要条件：任意去掉图中 n 个节点及关联的边后, 得到的分图数目小于等于 n. 充分条件：图中每一对节点的度数之和都大于等于图中的总节点数.29. 哈密顿图的应用：支配圆桌会议.方法：将每一个人看做一个节点,将每个人与和他能沟通的人连 接,找到一条经过每个节点一次且仅一次的回路哈密顿图 ,即可.30. 平面图：将图形的交叉边进行改造后,不会显现边的交叉,就是平面图.31. 面次：面的边界回路长度称为该面的次.32. 一个有限平面图,面的次数之和等于其边数的两倍.33. 欧拉定理：假设一个连通平面图有v 个节点, e 条边, r 个面,就v-e+r=2 .34. 判定是平面图的必要条件： 如不满意,就肯定不是平面图 设图G 是v 个节点,e 条边的简洁连通平面图, 如v>=3 ,就 e<=3v-6 .可编辑资料 - - - 欢迎下载精品_精品资料_35. 同胚：对于两个图 G1,G2 ,假如它们是同构的,或者通过反复插入和除去 2 度节点可以变成同构的图,就称G1 ,G2 是同胚的.36. 判定 G 是平面图的充要条件：图 G 不含同胚于 K3.3 或 K5 的子图.37. 二部图：无向图的节点集合可以划分为两个子集V1 , V2.图中每条边的一个端点在 V1 ,另一个就在 V2 中. 完全二部图：二部图中V1 的每个节点都与 V2 的每个节点邻接. 判定无向图 G 为二部图的充要条件：图中每条回路经过边的条数均为偶数.38. 树：具有 n 个顶点 n-1 条边的无回路连通无向图.39. 节点的层数：从树根到该节点经过的边的条数.40. 树高：层数最大的顶点的层数.41. 二叉树：二叉树额基本结构状态有 5 种.二叉树内节点的度数只考虑出度,不考虑入度.二叉树内树叶的节点度数为 0,而树内树叶节点度数为 1.二叉树内节点的度数 =边的总数 只算出度 .握手定理“节点数=边的两倍”是在同时运算入度和出度的时成立.可编辑资料 - - - 欢迎下载精品_精品资料_二叉树内节点的总数 =边的总数 +1.位于二叉树第 k 层上的节点,最多有2k 1 个k>=1 .可编辑资料 - - - 欢迎下载精品_精品资料_深度为 k 的二叉树的节点总数最多为 2 k -1 个,最少 k 个k>=1 .可编辑资料 - - - 欢迎下载精品_精品资料_假如有n0 个叶子,n2个 2 度节点,就n0 = n2 +1 .可编辑资料 - - - 欢迎下载精品_精品资料_42. 二叉树的节点遍历方法：先根次序（ DLR ）.中根次序（ LDR ）.后根次序（ LRD ）.43. 哈夫曼树：用哈夫曼算法构造的最优二叉树.44. 最优二叉树的构造方法：将给定的权值按从小到大排序.取两个最小值分支点的左右子树 左小右大 ,去掉已选的这两个权值,并将这两个最小值加起来作为下一轮排序的权值.重复,直达全部权值构造完毕.45. 哈夫曼编码：在最优二叉树上,根据左0 右 1 的规章,用 0 和 1代替全部边的权值.每个节点的编码：从根到该节点经过的0 和 1 组成的一排编码.可编辑资料 - - - 欢迎下载