离散数学(下)概念

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 流量
作者

xqmmcqs

发布于

2020-12-26

更新于

2022-01-18

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×