离散数学（下）概念

BUPT 离散数学（下）课程（计算机学院）涉及的公式，自制

第十一章学太快了没时间总结了

第九章

英文	中文
binary relation	二元关系
R-relative set of x	\(R(x)=\{y\in B| x\ R\ y\}\)
R-relative set of \(A_1\)	\(R(A_1)=\{y\in B|x\ R\ y,x\in A_1\}\)
reflexive	自反的，\(\forall x[x\in A\rightarrow(x,x)\in R]\)
irreflexive	反自反的，\(\forall x[x\in A\rightarrow(x,x)\notin R]\)
symmetric	对称的，\(\forall x\forall y[(x,y)\in R\rightarrow(y,x)\in R]\)
asymmetric	非对称的，\(\forall x\forall y[(x,y)\in R\rightarrow(y,x)\notin R]\)
antisymmetric	反对称的，\(\forall x\forall y[(x,y)\in R\wedge(y,x)\in R\rightarrow x=y]\)
transitive	传递的，\(\forall x\forall y\forall z[(x,y)\in R\wedge (y,z)\in R\rightarrow (x,z)\in R]\)
n-ary relation	n 元关系
relational data model	关系数据模型
primary key	主键
composite key	复合主键
selection operator	选择运算符：\(s_C\)，\(R\)中满足条件\(C\)的所有\(n\)元组
projection operator	投影运算符：将\(n\)元组映射到\(m\)元组
join operator	连接运算符：将两个表合成一个表
the restriction of \(R\) to \(B\)	\(R\cap(B\times B)\)
closure	闭包/封闭性
diagonal relation	对角关系：\(\Delta=\{(a,a)|a\in A\}\)
equivalence relation	等价关系：自反、对称、传递
equivalence class	等价类
representative	代表元
partition	划分
partial order	偏序关系：自反、反对称、传递
partially ordered set	偏序集
poset	偏序集
comparable	可比的：\(a\preccurlyeq b\)或\(b\preccurlyeq a\)
incomparable	不可比的：既不\(a\preccurlyeq b\)也不\(b\preccurlyeq a\)
totally ordered set	全序集：每对元素都可比
linear ordered set	线序集：每对元素都可比
total order	全序
linear order	线序
chain	链：全序集
well-ordered set	良序集：每个非空子集都有一个最小元素
quasiorder	拟序关系：传递、反自反
lexicographic order	字典顺序：\(a_1\prec_1 b_1\)或者\(a_1=b_1\)且\(a_2\prec b_2\)时\((a_1,a_2)\prec(b_1,b_2)\)
hasse diagram	哈塞图
covering relation	覆盖关系：\(x\prec y\)且不存在\(z\in S\)使得\(x\prec z\prec y\)的关系\((x,y)\)
isomorphism	同构/同构映射：有处处定义的双射函数，满足像的积等于积的像
maximal	极大元：不小于这个偏序集的任何其他元素
minimal	极小元：不大于这个偏序集的任何其他元素
greatest element	最大元：大于这个偏序集的所有其他元素
least element	最小元：小于这个偏序集的所有其他元素
unit element	最大元：大于这个偏序集的所有其他元素
zero element	最小元：小于这个偏序集的所有其他元素
upper bound	上界：大于偏序集的某个子集的所有元素
lower bound	下界：小于偏序集的某个子集的所有元素
least upper bound	最小上界
greatest lower bound	最大上界
lattice	格：每对元素都有最小上界和最大下界
topological sorting	拓扑排序

离散数学结构

英文	中文
commutative	可交换的：\(x\square y=y\square x\)
associative	可结合的：\((x\square y)\square z=x\square(y\square z)\)
distributive	可分配的：\(x\square(y\nabla z)=(x\square y)\nabla(x\square z)\)
identity	单位元：\(e\square x=x\)
inverse	逆元：\(x\square y=y\square x=e\)
binary operation	二元运算：处处定义的函数\(f:A\times A\rightarrow A\)
idempotent	幂等的：\(a\square a=a\)
semigroup	半群：一个非空集合和一个可结合的二元运算
monoid	独异点：含有单位元的半群
subsemigroup	子半群：闭合的一个半群的子集
submonoid	子独异点：含有单位元的子半群
isomorphic	同构的
homomorphism	同态：有处处定义的函数，满足像的积等于积的像
homomorphic image	同态像
congruence relation	同余关系： \(R\)是等价关系，\(a,a'\)等价，\(b,b'\)等价，则\((a*b),(a'*b')\)等价
quotient semigroup	商半群：\((S/R,\circledast)\)，其中\(\circledast([a],[b])=[a]\circledast[b]=[a*b]\)
factor semigroup	商半群
natural homomorphism	自然同态：\(f_R:S\rightarrow S/R\quad f_R(a)=[a]\)
group	群：一个集合和一个可结合的、有单位元、有逆元的二元运算
Abelian	阿贝尔群：满足可交换的群
subgroup	子群：子群\(H\)包含群\(G\)的单位元、封闭、同时包含\(a\)和\(a^{-1}\)
trivial subgroup	平凡子群：群本身和只包含单位元的子群
Klein 4 group	克莱因四元素群
cyclic group	循环群：\(G=\{a_0,a_1,a_2,a_3\}\)
left coset	左陪集：\(aH=\{ah|h\in H\}\)
right coset	右陪集：\(Ha=\{ha|h\in H\}\)
normal subgroup	正规子群：\(aH=Ha\)对于所有的\(a\in G\)
kernel	核：\(\ker(f)=\{a\in G|f(a)=e'\}\)
word	码字：长度为\(m\)的 01 序列
noise	噪声：传输时可能使 01 码字发生变化
parity check code	奇偶校验码
Hamming distance	海明距离：\(\delta(x,y)=|x\oplus y|\)
group code	群码：\(e(B^m)=\{e(b)|e(b)\in B^n\}\)是\(B^n\)的子群
parity check matrix	一致性检验矩阵：\(H=\left[\begin{matrix}H_{m\times r} \\ I_r\end{matrix}\right]\)
maximum likelihood technique	极大似然技术：假设\(B^m\)有序排列，找到第一个和\(x\)距离最小的码字
coest leader	陪集头
syndrome	特征值

第八章

英文	中文
linear homogeneous recurrence relation of degree k with constant coefficients	常系数线性齐次递推关系
characteristic equation	特征方程
characteristic root	特征根
linear nonhomogeneous recurrence relation with constant coefficients	常系数线性非齐次递推关系
associated homogeneous recurrence relation	相伴的齐次递推关系
divide and conquer algorithm	分治算法
the master theorem	主定理：\[n=b^k\quad k\in\mathbf Z \\ f(n)=af(n/b)+cn^d\in\left\{\begin{align*}& O(n^d) & a<b^d \\& O(n^d\log n) & a=b^d \\& O(n^{\log_b a}) & a>b^d\end{align*}\right.\]
backtracking	回溯法
generating functions	生成函数

第十章

英文	中文
graph	图：\(G=(V,E)\)
vertex/vertices	顶点
node	节点
edge	边
endpoint	端点
simple graph	简单图：无向边，无重边，无自环
multigraph	多重图：无向边，有重边，无自环
pseudograph	伪图：无向边，有重边，有自环
directed graph	有向图
digraph	有向图
directed edge	有向边
simple directed graph	简单有向图：有向边，无重边，无自环
directed multigraphs	多重有向图：有向边，有重边，有自环
multiplicity	多重度
mixed graph	混合图：无向和有向边，有重边，有自环
adjacent	邻接
neighbor	相邻
incident with	关联：\(e\)连接\(u\)和\(v\)
connect	连接：\(e\)连接\(u\)和\(v\)
neighborhood	邻居：所有和邻接的节点的集合
degree	度：\(\mathrm{deg}(v)\)
isolated	孤立的：度为 0
pendant	悬挂的：度为 1
initial vertex	起点
terminal vertex	终点
in-degree	入度：\(\mathrm{deg}^-(v)\)
out-degree	出度：\(\mathrm{deg}^+(v)\)
underlying undirected graph	基本无向图：把有向图的方向忽略得到的无向图
complete graph	完全图：\(K_n\)
cycle	圈图：\(C_n\)
wheel	轮图：\(W_n\)
n-cube	\(n\)立方体图：\(Q_n\)
bipartite graph	二分图
complete bipartite graph	完全二分图：\(K_{m,n}\)
matching	匹配
complete match	完全匹配
subgraph	子图
proper subgraph	真子图
adjacency list	邻接表
adjacency matrix	邻接矩阵
incidence matrix	关联矩阵：行是点，列是边
isomorphic graph	同构图：存在双射函数\(f:V_1\to V_2\)，\(\forall a,b\in V_1\)，\(a,b\)在图\(G_1\)中邻接当且仅当\(f(a),f(b)\)在图\(G_2\)中邻接
path	通路
traverse	遍历：路径遍历了某些边
circut	回路
simple path/circut	简单路径/回路：每条边至多出现一次
walk	路径：顶点和边相互交替的序列
closed walk	闭合路径
trail	路线：没有重复边的路径
connected	连通的
connected component	连通分支：无向图的极大连通子图
cut vertex	割点
cut edge	割边
bridge	桥：割边
nonseparable graph	不可分割图：不含割点的连通图
vertex cut	点割集
separating cut	分割集
vertex connectivity	点连通度：点割集中最小的顶点数，\(\kappa(G)\)
edge cut	边割集
edge connectivity	边连通度：边割集中最小的边数，\(\lambda(G)\)
strongly connected	强连通的
weakly connected	弱连通的：有向图的基本无向图连通
strongly connected component	强连通分支：有向图的极大强连通子图
Euler circuit	欧拉回路：包含 G 的每一条边的简单回路
Euler path	欧拉通路：包含 G 的每一条边的简单通路
Hamilton path	哈密顿通路：经过 G 中每一个顶点恰好一次的简单通路
Hamilton circuit	哈密顿回路：经过 G 中每一个顶点恰好一次的简单回路
planar	平面图
planar representation	平面表示
region	面
elementary subdivision	初步细分：删去一条边，增加一个点和两条边
homeomorphic	同胚的：可以从相同的图通过一系列初步细分得到的两张图
coloring	着色
chromatic number	着色数：\(\chi(G)\)
chromatic polynomial	着色多项式：\(P_G(n)\)用\(n\)或更少的颜色给图\(G\)染色的方案数
source	源端
sink	汇端
capacity	容量
flow	流量