这幅思维导图基于我上课复习的重点而作,并不全面,如有纰漏请指出。
二元关系
序偶
笛卡尔积
域
- 前域
- 后域
- 定义域
- 值域
二元关系
- 定义
重要关系
- 空关系
- 全关系
- 恒等关系
二元关系的数量
关系的表示
- 集合表示法
- 关系图表示法
关系矩阵表示法
- 布尔矩阵的并交运算
- 布尔矩阵的积运算
关系的运算
基本运算
- 交
- 并
- 补
- 差
- 复合运算
- 逆运算
- 幂运算
关系的性质
- 自反性
- 反自反性
- 对称性
- 反对称性
- 传递性
关系的闭包运算
- 自反闭包(r(R))
- 对称闭包(s(R))
- 传递闭包(t(R))
集合论
特殊的集合
- 空集(∅)
- 全集(U)
- 有限集、无限集
- 幂集
- 自然数集合(N)
- 整数集(Z)
- 有理数集合(Q)
- 复数集(C)
集合的表示方法
- 枚举法
- 隐式法
- 归纳法
- 递归指定
- 文氏图法
集合与元素的关系
- 明确
- 互异
- 无序
集合间的关系
- 相等
包含
- 真包含
集合的运算
- 交
- 并
- 差
- 补
- 对称差
集合的运算定律
- 幂等率
- .......
- 德摩根率
可数集合与不可数集合
- 等势
特殊关系
等价关系
性质
- 自反
- 对称
- 传递
等价类
特点
- 不空
- 不重
- 不丢
- 商集
- 划分
次序关系
拟序关系
性质
- 反自反
- 传递
偏序关系
性质
- 自反
- 反对称
- 传递
哈斯图
- 画法
最大元、最小元
(在一个集合中)大于等于(小于等于)所有
极大元、极小元
(在一个集合中)没有比其大(小)的元素
上界、下界
(在全集中)大于等于(小于等于)全部集合中的元素
上确界、下确界
最小上界,最大下界
函数
函数的定义
函数的类型
- 单射
- 满射
- 双射
- 变换
函数的运算
- 复合运算
特殊图
欧拉图
- 欧拉通路(回路)
判定定理
- 有向欧拉图
- 无向欧拉图
- Fleury算法
哈密顿图
- 哈密顿通路(回路)
判定方法
- 必要条件
- 充分条件
- 其它方法
偶图
判定方法
- 必要条件
- 充分条件
匹配
判定条件
- 相异性条件
- t条件
- 必要条件
平面图
面
- 无限面
- 有限面
- 边
- 次数
- 欧拉公式
- 同胚
- 收缩
- 库拉托夫斯基定理
树
无向树
定义
- 叶
- 分支点
- 森林
- 平凡树
性质
- 无回路
- 连通
- 平凡树至少有2片叶
生成树
算法
- 破圈法
- 避圈法
- 广度优先法
最小生成树
算法
- Kruskal
- Prim
有向树
定义
- 根树
- 外向树
- 内点
- 叶
- 根
- 分支点
- 层数
- 根树的高
关系
- 祖先
- 后代
- 父亲
- 儿子
- 兄弟
- 有序树、k元树
遍历
- 先根
- 后根
- 中根
最优树
定义
- 前缀
- 前缀码
- 二元前缀码
赋权二元树
- 权
算法
- 哈夫曼算法
图
定义
序偶
- 有序<u,v>
- 无序(u,v)
表示
- 集合
- 图形
- 矩阵
分类
按边的方向
- 有向图
- 无向图
- 混合图
按重边
- 多重图
- 线图
- 简单图
按权值
- 有权
- 无权
特殊图
- 零图
- 平凡图
子图
- 真子图
- 导出子图
- 生成子图
完全图
补图
点
度
握手定理
- 推论
分类(有向图)
- 入度
- 出度
- 悬挂点
- 邻接点
- 割点
边
- 邻接边
- 割边(桥)
同构
- 定义
- 必要条件
通路、回路
- 简单(复杂)通路、简单(复杂)回路
- 基本通路、基本回路
可达性与最短路
- 可达性判定
- 可达性矩阵
连通性
无向图
- 连通分支
- 点割集
- 边割集
有向图
分类
- 弱连通图
- 单向连通图
- 强连通图
- 非连通图
连通分支
- 若连通分支
- 单连通分支
- 强连通分支
谓词逻辑
个体词
- 个体常量
- 个体变量
- 个体域
量词
- 全称量词
- 特称量词
- 量词辖域
谓词
- 逻辑符号化
谓词合成公式
- 原子公式
- 合成公式
自由变元与约束变元
- 改名规则
- 带入规则
- 闭式
- 公式的解释
分类
- 有效公式
- 矛盾公式
- 可满足公式
- 基本等价关系
范式
- 前束范式
- Skolem标准型
谓词综合推理
- 推理规律
推理规则
- US
- UG
- ES
- EG
命题逻辑
命题
命题连接词
- 否定
- 合取
- 析取
- 蕴含
- 等价
命题公式
分类
- 永真公式(重言式)
- 永假公式(矛盾式)
- 可满足式
公式的等价
- 基本等价公式
范式
- 文字
简单析取式(子句)
- 合取范式
简单合取式(短语)
- 析取范式
- 互补对
主范式
- 极小项、极大项
求解
- 公式法
- 真值表技术
命题蕴含公式
基本蕴含关系
- 简化规则
- ......
- 二难推论
演绎法推理
推理规则
- P
- T
- CP