离散数学必备知识点总结3.docx

《离散数学必备知识点总结3.docx》由会员分享，可在线阅读，更多相关《离散数学必备知识点总结3.docx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备总结离散数学学问点其次章命题规律1.，前键为真，后键为假才为假。，相同为真，不同为假。2.主析取范式：微小项 m 之和。主合取范式：极大项M之积。3.求微小项时，命题变元的确定为1，否定为 0，求极大项时相反。4.求极大微小项时，每个变元或变元的否定只能显现一次，求微小项时变元不够合取真，求极大项时变元不够析取假。5.求范式时，为保证编码不错， 命题变元最好按P,Q,R 的次序依次写。6.真值表中值为 1 的项为微小项，值为0 的项为极大项。可编辑资料 - - - 欢迎下载精品名师

2、归纳总结7.n个变元共有2 n 个微小项或极大项，这2n 为02n -1刚好为化简完可编辑资料 - - - 欢迎下载精品名师归纳总结后的主析取加主合取。8.永真式没有主合取范式，永假式没有主析取范式。9.推证包蕴式的方法 = ：真值表法。 分析法 假定前键为真推出后键为真，假定前键为假推出后键也为假10. 命题规律的推理演算方法：P 规章， T 规章真值表法。直接证法。归谬法。附加前提法。第三章谓词规律1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质。 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系。2.全称量词用包蕴 ，存在量词用合取 ;可编辑资料 - - - 欢迎下载精品名师

3、归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备3.既有存在又有全称量词时，先消存在量词，再消全称量词。第四章集合1.N ，表示自然数集， 1,2,3，不包括 0。2.基：集合 A 中不同元素的个数， |A|。3.幂集：给定集合 A，以集合 A 的全部子集为元素组成的集合，PA 。可编辑资料 - - - 欢迎下载精品名师归纳总结4.如集合 A 有 n 个元素，幂集 PA

4、 有 2n 个元素， |PA|=2| A| = 2n 。可编辑资料 - - - 欢迎下载精品名师归纳总结5.集合的分划： 等价关系 每一个分划都是由集合A 的几个子集构成的集合。这几个子集相交为空，相并为全A 。6.集合的分划与掩盖的比较：分划：每个元素均应显现且仅显现一次在子集中。掩盖：只要求每个元素都显现，没有要求只显现一次。第五章关系1.如集合 A 有 m 个元素，集合 B 有 n 个元素， 就笛卡尔 AB 的基数可编辑资料 - - - 欢迎下载精品名师归纳总结2为 mn， A 到 B 上可以定义2mn 种不同的关系。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - -

5、 欢迎下载精品名师归纳总结2.如集合 A 有 n 个元素，就 |A A|=n2 ，A 上有2n 个不同的关系。可编辑资料 - - - 欢迎下载精品名师归纳总结3.全关系的性质：自反性，对称性，传递性。空关系的性质：反自反性，反对称性，传递性。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备全封闭环的性质：自反性，对称性，反对称性，

6、传递性。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属于 A， y 盖住 x 。9.微小元：集合 A 中没有比它更小的元素 如存在可能

7、不唯独 。 极大元：集合 A 中没有比它更大的元素 如存在可能不唯独 。 最小元：比集合 A 中任何其他元素都小 如存在就肯定唯独 。 最大元：比集合 A 中任何其他元素都大 如存在就肯定唯独 。10. 前提： B 是 A 的子集上界： A 中的某个元素比B 中任意元素都大，称这个元素是B 的上界如存在，可能不唯独 。下界： A 中的某个元素比B 中任意元素都小，称这个元素是B 的下界如存在，可能不唯独 。上确界：最小的上界 如存在就肯定唯独 。下确界：最大的下界 如存在就肯定唯独 。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第

8、3 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备第六章函数21.如|X|=m,|Y|=n, 就从 X 到 Y 有 2mn 种不同的关系，有 n m 种不同的函数。可编辑资料 - - - 欢迎下载精品名师归纳总结2.在一个有n个元素的集合上，可以有2n 种不同的关系，有n n 种不可编辑资料 - - - 欢迎下载精品名师归纳总结同的函数，有 n.种不同的双射。m3.如|X|=m,|Y|=n ，且 m=n ，就从 X 到 Y 有 A n 种不

9、同的单射。可编辑资料 - - - 欢迎下载精品名师归纳总结4.单射： f:X-Y ，对任意x1 , x2 属于 X, 且x1 x2 ，如 fx1 f 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

10、 是满射。第七章代数系统1.二元运算：集合A 上的二元运算就是A2 到 A 的映射。2. 集合 A 上可定义的二元运算个数就是从AA 到 A 上的映射的个数，即从从 AA 到 A 上函数的个数，如 |A|=2, 就集合 A 上的二元运算的可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备可编辑资料 - - - 欢迎下载精品名师归纳总

11、结个数为2 2* 2 = 24 =16 种。可编辑资料 - - - 欢迎下载精品名师归纳总结3. 判定二元运算的性质方法：封闭性：运算表内只有所给元素。交换律：主对角线两边元素对称相等。幂等律：主对角线上每个元素与所在行列表头元素相同。有幺元：元素所对应的行和列的元素依次与运算表的行和列相同。有零元：元素所对应的行和列的元素都与该元素相同。 4.同态映射：, 满意 fa*b=fafb,就 f 为由 到的同态映射。如f 是双射，就称为同构。第八章群1.广群的性质：封闭性。半群的性质：封闭性，结合律。含幺半群 独异点 ：封闭性，结合律，有幺元。 群的性质：封闭性，结合律，有幺元，有逆元。2.群没有

12、零元。3.阿贝尔群 交换群 ：封闭性，结合律，有幺元，有逆元，交换律。4.循环群中幺元不能是生成元。5.任何一个循环群必定是阿贝尔群。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备第十章格与布尔代数1.格：偏序集合 A 中任意两个元素都有上、下确界。2.格的基本性质：1) 自反性a a对偶: aa2) 反对称性a b b a=

13、a=b对偶 :ab b a= a=b3) 传递性a b b c=a c对偶 :ab b c=ac4) 最大下界描述之一ab a对偶 avb a Ab b对偶 avb b5）最大下界描述之二c a,c b=cab对偶 ca,c b=cavb6) 结合律abc=abc对偶 avbvc=avbvc7) 等幂律aa=a对偶ava=a可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - -

14、- - - - -名师举荐细心整理学习必备8) 吸取律aavb=a对偶avab=a9) a b ab=aavb=b10) ac,b d=ab cdavb cvd11) 保序性bc=ab acavb avc 12 ） 安排不等式avbc avbavc对偶abvc abvac 13 ）模不等式acavbc avbc3.安排格：满意 abvc=abvac和 avbc=avbavc。4.安排格的充要条件：该格没有任何子格与钻石格或五环格同构。5.链格肯定是安排格，安排格必定是模格。6.全上界：集合 A 中的某个元素 a 大于等于该集合中的任何元素，就称 a 为格 A, 的全上界，记为1。 如存在就唯独

15、 全下界：集合A 中的某个元素b 小于等于该集合中的任何元素，就称 b 为格A, 的全下界，记为0。 如存在就唯独 7.有界格：有全上界和全下界的格称为有界格，即有0 和 1 的格。8.补元：在有界格内，假如ab=0,avb=1 ，就 a 和 b 互为补元。9.有补格：在有界格内，每个元素都至少有一个补元。10. 有补安排格 布尔格 ：既是有补格，又是安排格。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总

16、结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备11. 布尔代数：一个有补安排格称为布尔代数。第十一章图论1.邻接：两点之间有边连接，就点与点邻接。2.关联：两点之间有边连接，就这两点与边关联。3.平凡图：只有一个孤立点构成的图。4.简洁图：不含平行边和环的图。5.无向完全图：n 个节点任意两个节点之间都有边相连的简洁无向图。 有向完全图 :n 个节点任意两个节点之间都有边相连的简洁有向图。6.无向完全图有 nn-1/2条边，有向完全图有nn-1 条边。 7.r- 正就图：每个节点度数均为r 的图。8.握手定理：节点度数的总和等于边的两倍。9.任何图中，度数为奇数

17、的节点个数必定是偶数个。10. 任何有向图中，全部节点入度之和等于全部节点的出度之和。11. 每个节点的度数至少为2 的图必定包含一条回路。可编辑资料 - - - 欢迎下载精品名师归纳总结12. 可达：对于图中的两个节点vi , v j，如存在连接vi 到 vj的路，就称 vi可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结与 v j 相互可达，也称vi 与 v j是连通的。在有向图中，如存在vi 到 vj 的可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结路，就称vi 到v j可达。可编辑资料 -

18、 - - 欢迎下载精品名师归纳总结13. 强连通：有向图章任意两节点相互可达。单向连通：图中两节点至少有一个方向可达。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备弱连通：无向图的连通。弱连通必定是单向连通 14. 点割集：删去图中的某些点后所得的子图不连通了，假如删去其他几个点后子图之间仍是连通的，就这些点组成的集合称为点割集

19、。割点：假如一个点构成点割集，即删去图中的一个点后所得子图是不连通的，就该点称为割点。可编辑资料 - - - 欢迎下载精品名师归纳总结15. 关联矩阵： MG ， mij是 vi 与ej关联的次数，节点为行，边为列。可编辑资料 - - - 欢迎下载精品名师归纳总结无向图：点与边无关系关联数为0，有关系为 1，有环为 2。有向图：点与边无关系关联数为0，有关系起点为1 终点为 -1，关联矩阵的特点：无向图：行：每个节点关联的边，即节点的度。列：每条边关联的节点。有向图：全部的入度 1=全部的出度 0;16. 邻接矩阵： AG ， aij 是 vi 邻接到 vj 的边的数目，点为行，点为列。17.

20、 可达矩阵： PG ，至少存在一条回路的矩阵，点为行，点为列。可编辑资料 - - - 欢迎下载精品名师归纳总结PG=AG+A2 G+A3 G+A4 G可编辑资料 - - - 欢迎下载精品名师归纳总结可达矩阵的特点： 说明图中任意两节点之间是否至少存在一条路，以及在任何节点上是否存在回路。AG 中全部数的和：表示图中路径长度为1 的通路条数。A2 G 中全部数的和：表示图中路径长度为2 的通路条数。A3 G 中全部数的和：表示图中路径长度为3 的通路条数。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 9 页，共 16 页 - - -

21、 - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备A4 G 中全部数的和：表示图中路径长度为4 的通路条数。PG 中主对角线全部数的和：表示图中的回路条数。18. 布尔矩阵： BG ， vi 到v j 有路为 1，无路就为 0，点为行， 点为列。19. 代价矩阵：邻接矩阵元素为1 的用权值表示，为0 的用无穷大表示，节点自身到自身的权值为0。20. 生成树：只拜访每个节点一次，经过的节点和边构成的子图。21. 构造生成树的两种方法：深度优先。广度优先。 深度优先：可编辑资

22、料 - - - 欢迎下载精品名师归纳总结选定起始点v0 。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结挑选一个与v0 邻接且未被拜访过的节点v1 。可编辑资料 - - - 欢迎下载精品名师归纳总结从 v1 动身按邻接方向连续拜访，当遇到一个节点所有邻接点均已被拜访时， 回到该节点的前一个点， 再寻求未被拜访过的邻接点，直到全部节点都被拜访过一次。广度优先：可编辑资料 - - - 欢迎下载精品名师归纳总结选定起始点v0 。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结拜访与v0 邻接的全部节点v

23、1 , v2 , vk ,这些作为可编辑资料 - - - 欢迎下载精品名师归纳总结第一层节点。可编辑资料 - - - 欢迎下载精品名师归纳总结在第一层节点中选定一个节点v1 为起点。可编辑资料 - - - 欢迎下载精品名师归纳总结重复，直到全部节点都被拜访过一次。22. 最小生成树：具有最小权值T 的生成树。23. 构造最小生成树的三种方法：克鲁斯卡尔方法。管梅谷算法。普利姆算法。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 10 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳

24、总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备（1）克鲁斯卡尔方法将全部权值按从小到大排列。先画权值最小的边，然后去掉其边值。重新按小到大排序。再画权值最小的边，如最小的边有几条相同的，挑选时要满意不能显现回路，然后去掉其边值。重新按小到大排序。重复，直到全部节点都被拜访过一次。（2）管梅谷算法 破圈法 在图中取一回路，去掉回路中最大权值的边得一子图。在子图中再取一回路， 去掉回路中最大权值的边再得一子图。重复，直到全部节点都被拜访过一次。（3）普利姆算法可编辑资料 - - - 欢迎下载精品名师归纳总结在图中任取一点为起点v1 ，连接边值

25、最小的邻接点v2 。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结以邻接点v2 为起点，找到v2 邻接的最小边值，假如最小边值可编辑资料 - - - 欢迎下载精品名师归纳总结比 v1 邻接的全部边值都小 除已连接的边值 ，直接连接，否就退回v1 ，连接 v1 现在的最小边值 除已连接的边值 。重复操作，直到全部节点都被拜访过一次。24. 关键路径例 2求 PERT 图中各顶点的最早完成时间,最晚完成时间 ,缓冲时间及关键路径 .解：最早完成时间TEv1=0 TEv2=max0+1=1可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师

26、精选 - - - - - - - - - -第 11 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备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 TLv

27、4=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可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 12 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心

28、整理学习必备TSv7=6-6=0 TSv8=12-12=0关键路径 :v1-v3-v7-v825. 欧拉路：经过图中每条边一次且仅一次的通路。 欧拉回路：经过图中每条边一次且仅一次的回路。欧拉图：具有欧拉回路的图。单向欧拉路：经过有向图中每条边一次且仅一次的单向路。欧拉单向回路：经过有向图中每条边一次且仅一次的单向回路。26.（ 1）无向图中存在欧拉路的充要条件：连通图。有0 个或 2 个奇数度节点。（2）无向图中存在欧拉回路的充要条件：连通图。全部节点度数均为偶数。（3）连通有向图含有单向欧拉路的充要条件：除两个节点外，每个节点入度=出度。这两个节点中， 一个节点的入度比出度多1，另一个节点

29、的入。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 13 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师举荐细心整理学习必备度比出度少 1。（ 4）连通有向图含有单向欧拉回路的充要条件：图中每个节点的出度 =入度。27. 哈密顿路：经过图中每个节点一次且仅一次的通路。 哈密顿回路：经过图中每个节点一次且仅一次的回路。哈密顿图：具有哈密顿回路的图。28. 判定哈密顿图（没有充要条件） 必要条件：任意

30、去掉图中 n 个节点及关联的边后， 得到的分图数目小于等于n。 充分条件：图中每一对节点的度数之和都大于等于图中的总节点数。29. 哈密顿图的应用：支配圆桌会议。方法：将每一个人看做一个节点，将每个人与和他能沟通的人连 接，找到一条经过每个节点一次且仅一次的回路哈密顿图 ，即可。30. 平面图：将图形的交叉边进行改造后，不会显现边的交叉，就是平面图。31. 面次：面的边界回路长度称为该面的次。32. 一个有限平面图，面的次数之和等于其边数的两倍。33. 欧拉定理：假设一个连通平面图有v 个节点， e 条边， r 个面，就v-e+r=2 。34. 判定是平面图的必要条件：如不满意，就肯定不是平面

31、图设图 G 是 v 个节点，e 条边的简洁连通平面图， 如 v=3 ，就 e=1 。深度为 k 的二叉树的节点总数最多为2 k -1 个，最少 k 个k=1 。可编辑资料 - - - 欢迎下载精品名师归纳总结假如有n0 个叶子，n2 个 2 度节点，就n0 = n2 +1 。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 15 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - -

32、- - - - -名师举荐细心整理学习必备42. 二叉树的节点遍历方法：先根次序（ DLR ）。中根次序（ LDR ）。后根次序（ LRD ）。43. 哈夫曼树：用哈夫曼算法构造的最优二叉树。44. 最优二叉树的构造方法：将给定的权值按从小到大排序。取两个最小值分支点的左右子树 左小右大 ，去掉已选的这两个权值，并将这两个最小值加起来作为下一轮排序的权值。重复，直达全部权值构造完毕。45. 哈夫曼编码：在最优二叉树上，根据左0 右 1 的规章，用 0 和 1代替全部边的权值。每个节点的编码：从根到该节点经过的0 和 1 组成的一排编码。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 16 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载