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