离散数学必备知识点总结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=0TSv8=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 组成的一排编码。可编辑资料 - - - 欢迎下载