《离散数学》术语、符号、概念速查2025年1月4日3207字16分钟

《离散数学》课程中符号繁多、术语晦涩，这里整理了一些常用的符号、概念定律，做个人复习使用，仅供参考，欢迎补充。

“解释”仅作为辅助记忆的个人理解，并非严格的数学定义，具体请参考ppt和教材。

复习时请一定要回归定义。

目录

集合

基本

二元关系

函数

基数

图论

图的基本概念

欧拉图与哈密顿图

树

支配集、覆盖集、独立集和匹配

顶点着色

边着色

集合

基本

符号/概念含义解释集合集合的基数集合中元素的个数幂集所有子集构成的集合交并对称差补集广义交A子集的交集广义并A子集的并集

二元关系

基础

符号含义解释有序对/序偶关系笛卡尔积笛卡尔积空关系全域关系恒等关系定义域值域域逆复合复合和自己复合次在上的限制中以为定义域的关系在下的像; 定义域对应的值域自反性包含恒等关系反自反性不包含对称性反对称性有则无对称性反对称性有则无 (并非不对称)传递性

Tip不自反反自反

不对称反对称

偏序关系、等价关系、闭包

符号/概念含义解释偏序关系偏序关系; 即和可以比大小y覆盖x即和之间没有中间值B是A上的链 且任意均可比(科比)B是A上的反链 且任意均不可比极小元、极大元、最小元、最大元字面意思等价关系等价关系R是A上的等价关系，R是自反、对称、传递的和三角形等价类比关于的等价类和等价的元素的集合A关于R的商集中所有等价类的并集划分把A不重不漏地分割成若干子集(细细切做臊子)，得到的集合闭包的自反闭包包含R的最小自反关系，的对称闭包包含R的最小对称关系，的传递闭包包含R的最小传递关系，

函数

符号/概念含义解释函数为单射的二元关系为在的值像在下的像对应的值域完全原像在下的完全原像对应的定义域满射 任意都有使得单射任意都有 唯一 使得双射既满射又单射一一对应常函数、恒等函数（严格）单调递增（递减）函数复合（注意顺序）反函数

基数

符号/概念含义解释等势存在到的双射函数和能一一对应优势存在到的单射函数真优势优势且不等势后继的下一个数有穷与某个自然数等价 基数和等势的自然数的基数的基数可数

图论

图的基本概念

基本概念

符号/概念含义解释基本概念无序积,顶点(Vertex) 集,边(Edge) 集,顶点、边,顶点数、边数图(Graph)有向图(Digraph)度的邻边次数和（自环算2）出度的邻接出边次数入度的邻接入边次数图的最小度图的最大度悬挂点度为1的顶点; 的邻域; 的闭邻域的关联集与相连的边集合的后继元素和自然数的后继一样用的加号的先驱元素关联自环关联次数为2，其他为1重数到边的个数零图无边的图简单图无自环、无平行边的图多重图边有重数的图子图图的一部分生成子图包含母图所有点的子图的导出子图及之间边构成的的子图的导出子图及关联顶点构成的的子图图化给出顶点的度数，构造图同构形状一样无向完全图任意两顶点间都有边有向完全图任意两顶点间有来有回竞赛图任意两顶点间有且仅有一条边通路与回路通路连接始点和终点的路径是顶点和边的交替序列回路闭合通路简单路径、简单回路路径中边不重初级路径、初级回路路径中点、边不重（初级比简单更低级）复杂路径、复杂回路路径中边重复（点可重）长度通路中边的数目短程线最短通路到距离短程线长度连通与连通无向图中之间有通路点和自己连通连通分支连通关系的等价类连通分支数点割集删去后破坏连通性的点集边割集删去后破坏连通性的边集极小点割集、边割集刚好能破坏连通性极小最小割点删去后破坏连通性的点割边；桥删去后破坏连通性的边点连通度最小点割集大小边连通度最小边割集大小可达有向图中到存在通路相互可达有向图中间存在通路（弱）连通图有向图的基图是连通图单向连通图有向图任意两点间有通路（双向也算单向连通）强连通图有向图任意两点相互可达二部图的每条边两个端点分属于互补顶点子集完全二部图与所有点相邻零图是二部图

Tip对所有概念：

简单：边不重

初级：点不重

复杂：边重

：指出

：指入

闭：包含自己

开：不包含自己

真：不和自己相等

图的矩阵表示

符号/概念含义解释的关联矩阵与关联次数的关联矩阵始点为1，终点为-1，不关联为0的邻接(Adjacent)矩阵到边数的可达矩阵可达

Tip

矩阵关系关联邻接可达

图的运算

符号/概念含义解释的并图都是先对边做集合运算，再把关联点加进去的差图的交图的环合

欧拉图与哈密顿图

符号/概念含义解释欧拉通路经过所有边恰一次的通路欧拉回路经过所有边恰一次的回路哈密顿图具有哈密顿回路的图半哈密顿图具有哈密顿通路但无哈密顿回路的图哈密顿通路经过所有顶点恰一次的通路哈密顿回路经过所有顶点恰一次的回路带权图边有权值的图

Tip平凡图是欧拉图和哈密顿图

树

树的形心和中心

符号/概念含义解释树(Tree)连通无回路的无向图树叶1度的顶点分支点非树叶的顶点树的顶点的离心率其他点到的最大距离树的半径最小离心率树的直径最大离心率树的中心点离心率等于半径的顶点树的中心中心点的集合顶点的分支把这个顶点拿掉，剩下的连通分支顶点的度数分支的数目（和图的度数一样）顶点的权分支中边的最大数目顶点的形心点权最小的顶点，同时也是度数最大的点顶点的形心形心点的集合

生成树

符号/概念含义解释生成树是的生成子图且是树弦不在生成树上的边余树弦组成集合的导出子图（余树非树）收缩把的端点重合(两头捏在一起)后形成的图生成树棵数基本回路生成树加入一个弦后产生的回路基本回路系统所有弦对应基本回路的集合圈秩基本回路的个数,基本割集由一个树枝和许多弦构成的割集基本割集系统所有树枝对应基本割集的集合割集秩基本割集的个数,根树根树一个顶点入度为0，其余为1的有向树和数据结构里的一样树根、内点、树叶分支点树根和内点层数树根到的通路长度树高树的最大层数叉正则树每个分支点恰好有条边的树叉完全正则树树叶层数相同的叉正则树最优二叉树边权和最小的二叉树

Tip层数从0开始，树根的层数为0

平面图

符号/概念含义解释平面嵌入面内部面外部面面的次数面数极大平面图再加边就不能平面嵌入同胚消去、增加二度点后同构块图没有割点的连通图的块的“极小的”子块图基础简单图去掉自环和平行边形成的图对偶图面点，点面自对偶图对偶图和自己同构

支配集、覆盖集、独立集和匹配

符号含义解释支配集剩下点均与支配集中的点相连点覆盖集能覆盖所有边的点集点独立集不相邻的点的集边覆盖集能覆盖所有点的边集匹配；边独立集不相邻的边的集支配数点覆盖数点独立数边覆盖数匹配数饱和点中有边与之关联非饱和点中没有边与之关联完美匹配与所有点关联交错路径在与中交替取点形成的路径可增广交错路径起、重点_都是_非饱和点的交错路径完备匹配二部图中有一个点集都是的饱和点

符号含义解释支配集剩下点均与支配集中的点相连点覆盖集能覆盖所有边的点集点独立集不相邻的点的集边覆盖集能覆盖所有点的边集匹配；边独立集不相邻的边的集支配数点覆盖数点独立数边覆盖数匹配数饱和点中有边与之关联非饱和点中没有边与之关联完美匹配与所有点关联交错路径在与中交替取点形成的路径可增广交错路径起、重点_都是_非饱和点的交错路径完备匹配二部图中有一个点集都是的饱和点

、可能有多重含义，具体看上下文，可能指支配集、独立集等。

顶点着色

符号/概念含义解释地图国家两国家相邻有公共边（点不算）面着色面可着色面色数色图次大度有更大度邻居的点里度数最大的（并非次大）

点着色面着色

边着色

符号/概念含义解释正常边着色邻边不同色边色数因子至少含一条边的生成子图因子分解把分解边不重因子之并因子的度正则因子