课程笔记
3207字16分钟
《离散数学》课程中符号繁多、术语晦涩，这里整理了一些常用的符号、概念定律，做个人复习使用，仅供参考，欢迎补充。
“解释”仅作为辅助记忆的个人理解，并非严格的数学定义，具体请参考ppt和教材。
复习时请一定要回归定义。
目录
集合
基本
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 集合 | ||
| 集合的基数 | 集合中元素的个数 | |
| 幂集 | 所有子集构成的集合 | |
| 交 | ||
| 并 | ||
| 对称差 | ||
| 补集 | ||
| 广义交 | A子集的交集 | |
| 广义并 | A子集的并集 |
二元关系
基础
| 符号 | 含义 | 解释 |
|---|---|---|
| 有序对/序偶 | ||
| 关系 | ||
| 笛卡尔积 | ||
| 笛卡尔积 | ||
| 空关系 | ||
| 全域关系 | ||
| 恒等关系 | ||
| 定义域 | ||
| 值域 | ||
| 域 | ||
| 逆 | ||
| 复合 | ||
| 复合 | 和自己复合次 | |
| 在上的限制 | 中以为定义域的关系 | |
| 在下的像 | ; 定义域对应的值域 | |
| 自反性 | 包含恒等关系 | |
| 反自反性 | 不包含 | |
| 对称性 | ||
| 反对称性 | 有则无 | |
| 对称性 | ||
| 反对称性 | 有则无 (并非不对称) | |
| 传递性 |
Tip
不自反反自反
不对称反对称
偏序关系、等价关系、闭包
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 偏序关系 | ||
| 偏序关系; | 即和可以比大小 | |
| y覆盖x | 即和之间没有中间值 | |
| B是A上的链 | 且任意均可比 | |
| B是A上的反链 | 且任意均不可比 | |
| 极小元、极大元、最小元、最大元 | 字面意思 | |
| 等价关系 | ||
| 等价关系 | R是A上的等价关系，R是自反、对称、传递的 | 和三角形等价类比 |
| 关于的等价类 | 和等价的元素的集合 | |
| A关于R的商集 | 中所有等价类的并集 | |
| 划分 | 把A不重不漏地分割成若干子集，得到的集合 | |
| 闭包 | ||
| 的自反闭包 | 包含R的最小自反关系， | |
| 的对称闭包 | 包含R的最小对称关系， | |
| 的传递闭包 | 包含R的最小传递关系， | |
函数
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 函数 | 为单射的二元关系 | |
| 为在的值 | ||
| 像 在下的像 | 对应的值域 | |
| 完全原像 在下的完全原像 | 对应的定义域 | |
| 满射 | 任意都有使得 | |
| 单射 | 任意都有 唯一 使得 | |
| 双射 | 既满射又单射 一一对应 | |
| 常函数、恒等函数 （严格）单调递增（递减）函数 | ||
| 复合 | （注意顺序） | |
| 反函数 | ||
基数
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 等势 | 存在到的双射函数 和能一一对应 | |
| 优势 | 存在到的单射函数 | |
| 真优势 | 优势且不等势 | |
| 后继 | 的下一个数 | |
| 有穷 | 与某个自然数等价 | |
| | 基数 | 和等势的自然数 |
| 的基数 | ||
| 的基数 | ||
| 可数 | ||
图论
图的基本概念
基本概念
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 基本概念 | ||
| 无序积 | ||
| , | 顶点 集 | |
| , | 边 集 | |
| , | 顶点、边 | |
| , | 顶点数、边数 | |
| 图 | ||
| 有向图 | ||
| 度 | 的邻边次数和（自环算2） | |
| 出度 | 的邻接出边次数 | |
| 入度 | 的邻接入边次数 | |
| 图的最小度 | ||
| 图的最大度 | ||
| 悬挂点 | 度为1的顶点 | |
| ; | 的邻域 | |
| ; | 的闭邻域 | |
| 的关联集 | 与相连的边集合 | |
| 的后继元素 | 和自然数的后继一样用的加号 | |
| 的先驱元素 | ||
| 关联 | 自环关联次数为2，其他为1 | |
| 重数 | 到边的个数 | |
| 零图 | 无边的图 | |
| 简单图 | 无自环、无平行边的图 | |
| 多重图 | 边有重数的图 | |
| 子图 | 图的一部分 | |
| 生成子图 | 包含母图所有点的子图 | |
| 的导出子图 | 及之间边构成的的子图 | |
| 的导出子图 | 及关联顶点构成的的子图 | |
| 图化 | 给出顶点的度数，构造图 | |
| 同构 | 形状一样 | |
| 无向完全图 | 任意两顶点间都有边 | |
| 有向完全图 | 任意两顶点间有来有回 | |
| 竞赛图 | 任意两顶点间有且仅有一条边 | |
| 通路与回路 | ||
| 通路 | 连接始点和终点的路径 是顶点和边的交替序列 | |
| 回路 | 闭合通路 | |
| 简单路径、简单回路 | 路径中边不重 | |
| 初级路径、初级回路 | 路径中点、边不重 （初级比简单更低级） | |
| 复杂路径、复杂回路 | 路径中边重复 （点可重） | |
| 长度 | 通路中边的数目 | |
| 短程线 | 最短通路 | |
| 到距离 | 短程线长度 | |
| 连通 | ||
| 与连通 | 无向图中之间有通路 点和自己连通 | |
| 连通分支 | 连通关系的等价类 | |
| 连通分支数 | ||
| 点割集 | 删去后破坏连通性的点集 | |
| 边割集 | 删去后破坏连通性的边集 | |
| 极小点割集、边割集 | 刚好能破坏连通性 极小最小 | |
| 割点 | 删去后破坏连通性的点 | |
| 割边；桥 | 删去后破坏连通性的边 | |
| 点连通度 | 最小点割集大小 | |
| 边连通度 | 最小边割集大小 | |
| 可达 | 有向图中到存在通路 | |
| 相互可达 | 有向图中间存在通路 | |
| （弱）连通图 | 有向图的基图是连通图 | |
| 单向连通图 | 有向图任意两点间有通路 （双向也算单向连通） | |
| 强连通图 | 有向图任意两点相互可达 | |
| 二部图 | 的每条边两个端点分属于 | |
| 互补顶点子集 | ||
| 完全二部图 | 与所有点相邻 零图是二部图 | |
Tip
对所有概念：
- 简单：边不重
- 初级：点不重
- 复杂：边重
- ：指出
- ：指入
- 闭：包含自己
- 开：不包含自己
- 真：不和自己相等
图的矩阵表示
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 的关联矩阵 | 与关联次数 | |
| 的关联矩阵 | 始点为1，终点为-1，不关联为0 | |
| 的邻接矩阵 | 到边数 | |
| 的可达矩阵 | 可达 |
Tip
| 矩阵 | 关系 |
|---|---|
| 关联 | |
| 邻接 | |
| 可达 |
图的运算
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 的并图 | 都是先对边做集合运算，再把关联点加进去 | |
| 的差图 | ||
| 的交图 | ||
| 的环合 |
欧拉图与哈密顿图
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 欧拉通路 | 经过所有边恰一次的通路 | |
| 欧拉回路 | 经过所有边恰一次的回路 | |
| 哈密顿图 | 具有哈密顿回路的图 | |
| 半哈密顿图 | 具有哈密顿通路但无哈密顿回路的图 | |
| 哈密顿通路 | 经过所有顶点恰一次的通路 | |
| 哈密顿回路 | 经过所有顶点恰一次的回路 | |
| 带权图 | 边有权值的图 | |
Tip
平凡图是欧拉图和哈密顿图
树
树的形心和中心
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 树 | 连通无回路的无向图 | |
| 树叶 | 1度的顶点 | |
| 分支点 | 非树叶的顶点 | |
| 树的顶点的离心率 | 其他点到的最大距离 | |
| 树的半径 | 最小离心率 | |
| 树的直径 | 最大离心率 | |
| 树的中心点 | 离心率等于半径的顶点 | |
| 树的中心 | 中心点的集合 | |
| 顶点的分支 | 把这个顶点拿掉，剩下的连通分支 | |
| 顶点的度数 | 分支的数目（和图的度数一样） | |
| 顶点的权 | 分支中边的最大数目 | |
| 顶点的形心点 | 权最小的顶点，同时也是度数最大的点 | |
| 顶点的形心 | 形心点的集合 | |
生成树
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 生成树 | 是的生成子图且是树 | |
| 弦 | 不在生成树上的边 | |
| 余树 | 弦组成集合的导出子图（余树非树） | |
| 收缩 | 把的端点重合后形成的图 | |
| 生成树棵数 | ||
| 基本回路 | 生成树加入一个弦后产生的回路 | |
| 基本回路系统 | 所有弦对应基本回路的集合 | |
| 圈秩 | 基本回路的个数, | |
| 基本割集 | 由一个树枝和许多弦构成的割集 | |
| 基本割集系统 | 所有树枝对应基本割集的集合 | |
| 割集秩 | 基本割集的个数, | |
| 根树 | ||
| 根树 | 一个顶点入度为0，其余为1的有向树 和数据结构里的一样 | |
| 树根、内点、树叶 | ||
| 分支点 | 树根和内点 | |
| 层数 | 树根到的通路长度 | |
| 树高 | 树的最大层数 | |
| 叉正则树 | 每个分支点恰好有条边的树 | |
| 叉完全正则树 | 树叶层数相同的叉正则树 | |
| 最优二叉树 | 边权和最小的二叉树 | |
Tip
层数从0开始，树根的层数为0
平面图
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 平面嵌入 | ||
| 面 | ||
| 内部面 | ||
| 外部面 | ||
| 面的次数 | ||
| 面数 | ||
| 极大平面图 | 再加边就不能平面嵌入 | |
| 同胚 | 消去、增加二度点后同构 | |
| 块图 | 没有割点的连通图 | |
| 的块 | 的“极小的”子块图 | |
| 基础简单图 | 去掉自环和平行边形成的图 | |
| 对偶图 | 面点，点面 | |
| 自对偶图 | 对偶图和自己同构 | |
支配集、覆盖集、独立集和匹配
| 符号 | 含义 | 解释 |
|---|---|---|
| 支配集 | 剩下点均与支配集中的点相连 | |
| 点覆盖集 | 能覆盖所有边的点集 | |
| 点独立集 | 不相邻的点的集 | |
| 边覆盖集 | 能覆盖所有点的边集 | |
| 匹配；边独立集 | 不相邻的边的集 | |
| 支配数 | ||
| 点覆盖数 | ||
| 点独立数 | ||
| 边覆盖数 | ||
| 匹配数 | ||
| 饱和点 | 中有边与之关联 | |
| 非饱和点 | 中没有边与之关联 | |
| 完美匹配 | 与所有点关联 | |
| 交错路径 | 在与中交替取点形成的路径 | |
| 可增广交错路径 | 起、重点_都是_非饱和点的交错路径 | |
| 完备匹配 | 二部图中有一个点集都是的饱和点 | |
| 符号 | 含义 | 解释 |
|---|---|---|
| 支配集 | 剩下点均与支配集中的点相连 | |
| 点覆盖集 | 能覆盖所有边的点集 | |
| 点独立集 | 不相邻的点的集 | |
| 边覆盖集 | 能覆盖所有点的边集 | |
| 匹配；边独立集 | 不相邻的边的集 | |
| 支配数 | ||
| 点覆盖数 | ||
| 点独立数 | ||
| 边覆盖数 | ||
| 匹配数 | ||
| 饱和点 | 中有边与之关联 | |
| 非饱和点 | 中没有边与之关联 | |
| 完美匹配 | 与所有点关联 | |
| 交错路径 | 在与中交替取点形成的路径 | |
| 可增广交错路径 | 起、重点_都是_非饱和点的交错路径 | |
| 完备匹配 | 二部图中有一个点集都是的饱和点 | |
、可能有多重含义，具体看上下文，可能指支配集、独立集等。
顶点着色
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 地图 | ||
| 国家 | ||
| 两国家相邻 | 有公共边（点不算） | |
| 面着色 | ||
| 面可着色 | ||
| 面色数 | ||
| 色图 | ||
| 次大度 | 有更大度邻居的点里度数最大的（并非次大） | |
点着色面着色
边着色
| 符号/概念 | 含义 | 解释 |
|---|---|---|
| 正常边着色 | 邻边不同色 | |
| 边色数 | ||
| 因子 | 至少含一条边的生成子图 | |
| 因子分解 | 把分解边不重因子之并 | |
| 因子 | 的度正则因子 | |