离散数学（一）知识梳理
2023-03-15 16:55:22 2 举报AI智能生成
登录查看完整内容
离散数学（一）知识梳理
作者其他创作
大纲/内容
有限图
无限图
按顶点集大小
简单图：没有两条不同的边连接一对相同的顶点（默认是无向图）
多重图
伪图：包含环（连接同一顶点的边）或多重边的图
按边的重数
有向图
无向图
混合图
按边的方向
完全图 Kn：每对不同顶点之间都有一条边的简单图
圈图 Cn：围成一个圈的简单图
轮图 Wn：圈图中间加一个点并与圈上各点相连
n立方体图 Qn
特殊的图
图的分类
邻接/相邻：顶点与顶点的关系
关联/连接：顶点与边的关系
邻居 N(v)：具有相邻关系的所有顶点的集合
对有向图分为出度deg+(v)和入度deg-(v)两种
顶点上的环对顶点的度作出双倍贡献（2）
孤立点：度为0的点
悬挂点：度为1的点
度 deg(v)：与该顶点相关联的边的数目
基础术语
无向图中有偶数个度为奇数的顶点
有向图中入度=出度=边数
握手定理：顶点的度之和为边数的两倍
图的基础理论
邻接表：表头为所有顶点，表体为与该顶点相邻的所有顶点（从该点出发的边的终点）
无向图的邻接矩阵是对称的
伪图也可以用邻接矩阵来表示：不再是01矩阵，每项代表两个顶点之间边的条数
邻接表适合稀疏图（边较少），邻接矩阵适合稠密图
邻接矩阵：表示有无边相连的01矩阵（横看发射，竖看接收）
关联矩阵：纵轴为顶点，横轴为边的01矩阵，当二者有关联时取1
图的表示
顶点数/边数
对应顶点的度
长度为k的简单回路的存在性
图形不变量：在图的同构中保持不变的属性，判断不同构的关键
判断同构：构造一个双射关系f（找对应点）
图的同构
回路（圈）：在相同顶点开始和结束且长度大于0的通路【区分环的定义】
简单通路/回路：不重复地包含相同的边的通路或回路
路长：通路中经过的边的数量（顶点数-1）
font color=\"#dc2d1e\
通路：一系列边的序列
弱连通：有向图的基本无向图（去掉箭头的有向图）是连通的
不含割点的连通图称为不可分割图（如完全图Kn）
点割集/分割集：删除这个集合中的所有点后图的连通性被破坏
点连通度：非完全图的点连通度为点割集的最小顶点数，记作k(G)。k(G)越大就认为G的连通性越好。
若k(G)>=k则称G是k连通的
割点：删除该顶点和它所关联的边就破坏了图的连通性（产生更多连通分支）
边连通度：与点连通度的定义类似，也具有相似的概念，记作λ(G)
不等式：k(G)<=λ(G)<=min{deg(v)}
割边：删除该边就破坏了图的连通性
连通分支
连通性
图的连通性
定义：将简单图G的顶点分成两个不相交的非空集合V1，V2使得图中的所有边都从V1的一个顶点连接V2的一个顶点。（V1，V2）称为顶点集的一个二部划分
判定充要条件：图的着色数为2
匹配（M）：二分图中边的子集，要求在子集中没有两条边关联相同的顶点（即每个顶点至多只有一条边相连）。若顶点在匹配中有边相连，则称被匹配。
最大匹配：含有最多边数的一个匹配称为最大匹配
完全匹配：若V1中每个顶点都是匹配中边的端点（或|M|=|V1|），则称匹配M时从V1到V2的完全匹配
定理：二分图G中有一个V1到V2的完全匹配 当且仅当 对V1的所有子集A有|N(A)|>=|A|（其中N(A)表示A所有相邻点的集合）
霍尔婚姻定理：完全匹配的充要条件
应用：匹配问题
二分图/偶图
充要条件：含有至少2个顶点的连通多重图具有欧拉回路 当且仅当 它的每个顶点的度都为偶数
欧拉回路：包含每一条边的简单回路
充要条件：连接多重图具有欧拉通路但无欧拉回路 当且仅当 它恰有2个度为奇数的顶点
欧拉通路：包含每一条边的简单通路
欧拉图
没有已知的充要条件判断哈密顿回路
带有度为1的顶点的图没有哈密顿回路
狄拉克定理：G是n个顶点的简单图，且n>=3，若G中每个顶点的度都至少为n/2，则G有哈密顿回路
欧尔定理：G是n个顶点的简单图，n>=3，若G中每一对不相邻的顶点u、v来说，都有deg(u)+deg(v)>=n，则G有哈密顿回路
狄拉克定理是欧尔定理的推论
满足上述两定理可以判定有哈密顿图，但不满足不一定没有哈密顿回路
充分条件
哈密顿回路：经过G中每个顶点恰好一次的简单回路
哈密顿通路：经过G中每个顶点恰好一次的简单通路
哈密顿图
加权图：每条边赋上一个数的图
1. 用0标注起点，∞标注其他点，并把起点纳入点集S
2. 检索与点集内所有点相邻的所有点，找出从起点到这些点的路径并算出路径长度（可以借助对点集内点的标记值来快速计算）
3. 得到路径最短的一个点，用这个最短路径值标记这个点并将这个点纳入点集S
4. 重复上述步骤，直到把所求终点也纳入点集
当这个过程持续到所有顶点都加入在点集中就可以求出a到所有顶点的最短通路的长度
狄克斯特拉算法 【构造最短通路】
TSP（旅行商）问题：弗洛伊德算法【求最短通路长度；不能构造】
最短通路问题
定义：若可以在平面中画出一个图而边没有任何交叉，则这个图是平面图。这种画法被称为这个图的平面表示。
欧拉公式证明一个图的所有平面表示都把平面分成相同数目的面，其中包括一个无界的面
Kn 当 n>=5 时都不是平面图
推论1：若G是连通平面简单图且v>=3，则e<=3v-6（证明K5不是平面图）
推论2：若G是连通平面简单图，则G中有度数不超过5的顶点
推论3：若G为连通平面简单图且v>=3，且没有长度为3的回路，则font color=\"#faf200\
欧拉公式：G是带e条边和v个顶点的连通平面简单图，设r是G的平面图表示中被分割出的面数，则满足r=e-v+2 【？证明】
同胚：若两个图可以从相同的图经过一系列初等细分得到，则称这两个图同胚
库拉图斯基定理：若一个图包含font color=\"#faf200\
平面图问题
图的着色数：着色一个图所需要的最少颜色数，记作x(G)
四色定理：平面图的着色数不超过4
完全图Kn的着色数：x(Kn)=n
图着色问题
理论知识
基本概念考察
欧拉图和哈密顿图的判断和构造
二分图和匹配的判断和应用
判断平面图
着色问题
平面图
构造最短通路：狄克算法
求最短通路长度：弗洛伊德算法
计算邻接矩阵
利用邻接矩阵分析图特征
图的邻接矩阵
图的同构判断
题型
图论部分
定理：一个无向图是树 当且仅当 它的每对顶点之间存在唯一简单通路
定义：树是没有简单回路的连通无向图（一定是简单图）
森林：不含简单回路但不连通的图
有根树：指定每条边的方向为离开根的方向生成的有向图，称为有根树
父母/孩子/兄弟
树叶：没有孩子的顶点
内点：有孩子的顶点
根：指定树的某个顶点为特殊顶点，称为根
二叉树
有序二叉树可以分为左子树和右子树
有序树可以被递归定义
有序根树
层数/高度：从根到任意顶点的最长通路的长度
定义：高度为h的m叉树的所有树叶都在最下两层，则这棵树是平衡的
平衡m叉树
树的基本理论
带有n个顶点的树含有n-1条边【证明：数学归纳法】
【以下定理证明基于：n=mi+1；n=i+l】
已知顶点数n：i=(n-1)/m 个内点；l=[(m-1)n+1]/m 个树叶
已知内点数i：n=mi+1 个顶点；l=(m-1)i+1 个树叶
已知树叶数l：n=(ml-1)/(m-1) 个顶点；i=(l-1)/(m-1)个内点
带有i个内点的满m叉树含有n=mi+1个顶点【满m叉树得顶点数、内点数、叶子数具有知一求二的性质】
在高度为h的m叉树中至多有m^h个树叶【证明：数学归纳法-小于满m叉树】
树的性质
二叉搜索树：二分查找法
？定义：用变长的位数来给字母编码，需要保证一个字母的比特串永远不出现在另一个字母比特串的开头部分，这样的编码被称为前缀码。
作用：较短的比特串用来编码出现频繁的字母，而较长的用来编码不经常出现的字母，达到节省存储空间的目的。
左0右1：通向左子树的边标记为0，通向右子树的边标记为1
单向延申：树叶全部位于左子，右子除了最后的叶子全部用于延申树
从根解码：读出根到终点的的结点的路径即为所求前缀码
构造方法：用二叉树表示前缀码
前缀码
定义：该算法用一个字符串中符号的出现频率（用这个符号出现的次数除以这个字符串的长度）作为输入，产生一个这个 字符串的一个前缀码作为输出。
作用：产出占用位数最少的前缀码编码树，是数据压缩中的基础算法。该算法是贪心算法。
1. 给定符号及其频率，把所有符号作为顶点和频率作的顶点的权构成一个森林
2. 把具有最小总权值的树合成一个新树，引入一个新根，根结点的权值为两个子树的权值和，其中权值大的树作为左子树，权值小的树作为右子树
3. 重复上述步骤，直至森林缩小为单个树
构造方法
哈夫曼编码
树的应用
前序遍历
中序遍历
后序遍历
树的遍历：注意遍历方式和X缀表示法的关系
定理：简单图是连通的 当且仅当 它有生成树
定义：G是简单图，G的生成树是包含G的每个顶点的G的子图
深度优先搜索/回溯
宽度/广度优先搜索
？构造生成树【数据结构图论中已经写过代码】
定义：连通加权图里的最小生成树是具有边的权之和最小的生成树
1. 选择图中权最小的边添加到树中
2. 添加与已在树中顶点关联的且不会形成简单回路的权最小的边
3. 已经添加了n-1条边时就停止
普林（Prim）算法
2. 添加不会形成简单回路的权最小的边（没有要求和树中顶点相连）
克鲁斯卡尔算法
最小生成树
生成树
树部分
用命题变量来表示原子命题
用命题联结词来表示连词
命题符号化问题
利用真值表判断
利用已知的公式进行推理判断
定理：A为含有n个命题变元的命题公式，若A的主析取范式含有2^n个极小项，则A为重言式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为矛盾式；若A的主合取范式含有2^n个极大项，则A为矛盾式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为重言式
翻译：一个命题公式化成主范式后，若所有项都分布在主析取范式中（主合取范式为1）则为重言式；若所有项都分布在主合取范式中（主析取范式为0）则为矛盾式；若均有分布，则为可满足式。【思想来源：真值表法求主范式】
一个质析取式是重言式的充要条件是其同时含有某个命题变元及其否定式；一个质合取式是矛盾式的充要条件是其同时含有某个命题变元及其否定式
一个析取范式是矛盾式当且仅当它的每项都是矛盾式；一个合取范式是重言式当且仅当它的每项都是重言式
利用主析取和合取范式判断
命题公式的类型判断
1. 利用条件恒等式消除条件（蕴含和双条件）联结词，化简得到一个范式
2. 在缺项的质项中不改变真值地添加所缺项，化简得到一个主范式
3. 找出包含所有命题变元排列中剩余项，凑出另一个主范式（思想上类似于真值表法）
等值演算法
1. 画出命题公式真值表
主析取范式：真值为1的所有项，每一项按对应01构成极小项
主合取范式：真值为0的所有项，每一项按对应01构成极大项
2. 根据真值表结果求出主范式
真值表法
求（主）析取或合取范式
形式证明：命题逻辑的论证是一个命题公式的序列，其中每个公式或者是前提，或者是由它之前的公式作为前提推得的结论，序列的最后一个是待证的结论，这样的论证也称为形式证明。
把非条件语句全部转为条件语句
利用条件的逆否命题和双条件的拆分
利用重言式/矛盾式来不改变真值地添项
核心方法
形式证明与命题推理
？根据已知命题构造满足一定真值组合条件的命题表达式
真值表的应用
命题逻辑题型
特性谓词
存在量词/全称量词
涉及谓词的命题符号化问题
对于一个谓词逻辑公式，给每个谓词符号指定一个具体谓词，每个自由变量取定其个体域中的个体，称为这个谓词逻辑公式的一个解释。一个谓词逻辑公式，如果它在每个解释的真值均为真，则称其为永真式。
A≡ B当且仅当A↔B为永真式；；A⇒B当且仅当A→B为永真式。
判断谓词公式的真值/谓词公式关系式对错判断
全称示例US：∀xA(x) ⇒A(x)
全称生成UG：A(x)⇒ ∀xA(x)
存在示例ES：∃xA(x) ⇒A(c) （c为特定解释）
存在生成EG：A(c)⇒ ∃xA(x)
推理规则（将量词去掉，将谓词逻辑的推理化作命题逻辑的推理）
谓词逻辑推理证明的检错和纠错
谓词逻辑题型
合取（Conjunction）：交集，且运算
析取（Disjunction）：并集，或运算
异或
否定/非
条件
双条件
逻辑运算符/联结词
命题公式的逻辑等价
命题公式的蕴含关系
重言式/永真式
矛盾式
可满足式/可能式
命题公式分类
原子命题：不能继续拆分的命题（包括否命题）
质合取式：若干原子命题的合取
质析取式：若干原子命题的析取
质XX式
析取范式：质合取式的析取
合取范式：质析取式的合取
最小项：包含所有项的合取式
最大项：包含所有项的析取式
主析取范式：每项质合取式都是最小项
主合取范式：每项质析取式都是最大项
主范式
XX范式
范式（Normal Form）【判断：看最外层的运算符】
交换律
结合律
p∨ (q∧r) ≡ (p ∨q) ∧(p ∨r)
p∧(q ∨r) ≡ (p ∧q) ∨(p ∧r)
分配律
p→ q≡ ¬p∨ q
p↔ q≡ (p ∧ q)∨ (¬p∧ ¬q)
命题运算律
附加律：p ⇒ p ∨ q
化简律：p ∧ q ⇒ p
推理规则
谓词：定义运算关系f
量词：定义x取值范围（论域）
二者共同决定真值y
由上述元素构成命题函数
与函数对比：y=f(x)
全称量词
特称量词/存在量词
唯一性量词
量词种类
大写字母表示谓词
小写字母表示个体（命题函数中个体出现的次序很重要）
命题函数表示方式
引入特性谓词来代替论域声明
特性谓词和普通谓词应用不同的字母体系来表示
∀xP(x) ⇝ ∀x(A(x)→ P(x))
∃xP(x) ⇝ ∃x(A(x)∧ P(x))
特性谓词表示方式
论域与特性谓词
谓词和量词
基础知识
逻辑和证明部分
包含
相等
集合关系判断和证明
幂集
交并补
差集
集合运算
集合的划分：详见关系中等价类部分
基数：描述集合大小的量，在有限集中等于集合元素的个数，记作|A|
无限集A与B有相同的基数（大小相同） 当且仅当 存在从A到B的双射（一一对应）
若存在A到B的内射（一对一），则有|A|<=|B|；且当A与B有不同的基数时|A|<|B|
无限集的大小比较
概念
阿里夫零：定义自然数集的基数为阿里夫零
和自然数集具有相同的基数的无限集是可数的，基数为阿里夫零
证明方法：和自然数集构造一个双射函数
可数集的判断
？不可数集的证明
集合的基数
集合部分
定义域：A
陪域：B【注意不是值域，因为B中可能没有满射】
定义：F:A→B 相当于对A的每个元素恰好唯一指派B的一个元素，又称映射或变换【一个自变量不能对应多个因变量，反之可以】
值域：A中元素的所有像的集合
像：定义域中元素经变换后在值域中对应的元素
原像：变换前在定义域中的元素
函数的概念
递增/递减：定义域和陪域都是实数集子集
严格递增/递减
1. 令f(a)=f(b)推出a=b，证明不成立则反之
2. 严格单增/单减的函数一定是单射函数
证明方法
单射/一对一/入射/内射（one-to-one/injection） ：对任意f(a)=f(b)有a=b，即单调性（一个因变量不能对应多个自变量，即不存在多箭头）
证明方法：设任意元素b属于B，通过b=f(a)导出a，并证明a属于A，证明不成立则在B中找到一个无法在A中找到原像的元素
满射/映上（onto/surjection）：一个函数是满射 当且仅当 对每个b有a使得f(a)=b，即B被射满（陪域和值域相等）
双射/一一对应（one-tone correspondence/bijection）：既是单射又是满射，即A中元素和B中元素一一对应
函数的性质
前提条件：f:A→B为双射函数，故一一对应关系被称为可逆的(invertible)
反函数
符号顺序：从左到右为定义域的传递，即最外层在最左侧
前提条件：传递过程中前一个函数的值域一定包含于后一个函数的定义域（子集关系）
函数合成/复合函数
恒等函数
复杂函数
函数的应用
函数部分
函数与关系：函数是一种特殊的关系
集合的关系：集合与自身的关系是自身和自身的笛卡尔积的子集
两次求逆等于自身
转置和求逆可以互换顺序
不满足德摩根律
逆关系：有序对反序的关系
关系的概念
自反性：对于所有元素均有aRa
对称性：若aRb存在，则bRa一定存在
反对称性：只有在两个元素相等时才能满足aRb存在时bRa也存在【对称与反对称的概念不是对立的，可以同时具有或同时不具有】
传递性：若aRb，bRc，则有aRc
关系的性质
交并补差
定义：已知aRb、bSc，R与S的合成使有序对（a，c）组成的集合，要求a∈A，c∈C且存在b∈B使aRb，bSc
与函数合成的区别：没有要求前一个的值域必须是后一个定义域的子集，只需要存在特定元素满足条件即可（定义域不要求占满）
构造方法：画图，只看起点和终点
关系的幂运算：递归地定义R的n次幂为R的n次组合到自身
关系的合成（复合关系）
关系的组合
表示定义在一个集合上的关系的矩阵式一个方阵
方阵的主对角线上所有元素都等于1，则R是自反的
方阵关于主对角线对称，则R是对称的
方阵关于主对角线对称的位置不同时出现1，则R是反对称的
布尔积：用矩阵乘法法则做且运算
合成关系的矩阵等于原关系的布尔积，也适用于关系幂的计算
关系合成的矩阵
关系矩阵：ai与bj有关系时关系矩阵的（i，j）项为1，否则为0
每个顶点都有环，则R是自反的
每一条边都存在同顶点的方向相反的边，则R是对称的
图中不存在两条方向相反的边，则R是反对称的
图中不存在不能构成三角形的三条连续边，则R是传递的
关系图：每个元素看成点，每个有序对看成一条带有箭头的弧，自身到自身的弧用环来表示
关系的表示
定义：集合上包含R的，具有性质P的最小关系S（所有A上的具有性质P的关系都包含S）
求法：R ∪ 对角关系
自反闭包 r（R）
求法：R ∪ R的逆关系
对称闭包 s（R）
路径：一系列边的序列；在同一点开始和结束的长度大于等于1的路径称为回路或圈
关系Ｒ的传递闭包等于连通性关系R*
连通性关系：关系图中所有路径的总和（R*是所有R^n的并集）
关系矩阵乘法：R*的关系矩阵=所有R^n的关系矩阵的并
内部顶点：路径中除了起点和终点外的所有顶点
下缀n为当前结果中路径的最大内点数
继承型：存在一条vi到vj的且内部顶点在k-1个顶点中的路径（Wk-1矩阵中对应值已经为1）
中转型：新增的顶点vk使存在vi到vk和vk到vj的且这两条路径的内部顶点在前k-1个顶点中（Wk-1矩阵中这个新增元素有对应射入和射出）
算法：wij(k)=wij(k-1)∪(wik(k-1)∩wkj(k-1))
计算方法：采用递推的方法利用上一个矩阵求下一个矩阵，第一个矩阵W0为R的关系矩阵，最后一个矩阵Wn为R的连通性关系（传递闭包）
沃舍尔算法
求传递闭包的算法
传递闭包 t（R）
分类
关系的闭包
满足等价关系的元素往往具有某些共同的性质
最广泛使用的等价关系是模m同余关系
等价关系：同时具有自反性、对称性、传递性的关系
代表元：一个等价类的任何元素都可以作为这个类的代表元
等价类：R是定义在A上的等价关系，与A中一个元素有关系的所有元素的集合叫做a的等价类，记作[a]R或[a]
设R是定义在集合A上的一个等价关系，R的所有等价类的并集就是集合A
a∈A有a属于且仅属于一个等价类 等价于 不同等价类没有交集
等价类构成划分：可用集合的每个划分来构成等价关系，两个元素满足等价 当且仅当 它们在划分的同一子集中
划分和等价关系/等价类有一一对应关系
集合的划分：不相交的非空子集且所有子集的并集为自身的集合（本质：集合的集合）
等价关系/类
良序：全序且S的每个非空子集都有一个最小元素，则称S为良序集（有下限非无限）
良序归纳原理：从整个集合的最小元素开始递推证明命题（类似数学归纳法）
全序：当S中每对元素都是可比的，则S称为全序集或线序集/链，R为全序或线序
移除自反关系产生的环
移除传递边（跨点边）
确定一个方向，让所有边都满足这个方向，然后移除箭头
画法
哈塞图中指向上面的边与覆盖关系中的有序对相对应【哈塞图就是覆盖关系的表示】
覆盖关系可以还原偏序集：偏序集为覆盖关系的传递闭包的自反闭包
哈塞图：移除偏序关系中默认存在的边的最简图
极大元和极小元都可以有多个，它们对应图上的最高/最低层级，而同层可以有多个结点
极大/小元：不小/大于这个偏序集的任何其他元素
最大元和最小元若存在则一定是唯一的
最大/小元：大/小于每个其他元素的元素
上下界可以不是唯一的
必须指定一个子集才能确定上下界
上/下界：找到一个元素大/小于或等于偏序集的子集A中的所有元素，这个元素称为A的一个上/下界
判断：主要看有没有同级
最小上界/最大下界：若存在则唯一
格：每对元素都有最小上界和最大下界的偏序集
？拓补排序
极大元/极小元
偏序关系：同时具有自反、反对称、传递性的关系
关系部分
离散数学（一）知识梳理
0 条评论
回复 删除
下一页
