离散数学期末复习
由于离散数学期中过于拉跨，专门开贴记录相关知识点。
关系
三个定理
- 如果\(A_1\subseteq A_2\)则有\(R(A_1)\subset R(A_2)\)
- \(R(A_1\cup A_2)=R(A_1)\cup R(A_2)\)
- 重点： \(R(A_1\cap A_2)\subseteq R(A_1)\cap R(A_2)\)
整除关系 定义整除关系\(a|b\)为：\(a\)能整除\(b\)，如\(3|6\)，画哈塞图表示（哈塞图无向），则为上面为被整除的数，下面为除数。对于定义在集合\(A=\{1,3,6,9,15,45\}\)上的哈塞图如下：
在期中考试中错的很重一点是，对于偏序关系的大于、小于、上确界、下确界、极大值、极小值不清楚，那么对于偏序集合\((A,|)\)
覆盖关系(<) \(a|b \rightarrow a<b\)
上确界(最小上界) 针对一个子集，对于一个集合\(A\)的子集\(B=\{1,3,9\}\)，若在\(A\)中能找到一个元素\(a\)，使得\(\forall b\in B\rightarrow b<a\)，且\(a\)小于其他所有的上界，本条件下，最小上界\(LUB(B)=9\)
下确界（最大下界） 同理于上确界，\(GLB(B)=1\)
极大值、最大值 极大值为不小于其他任何元素的元素，可以有多个；最大值为大于其他任何元素的元素，只能有一个或者不存在。对于\(A\)，极大值为\(6,45\)，最大值不存在。
格
偏序集中任意两个元素组成的集合均存在最小上界和最大下界的偏序集合称作一个格
群
四个渐进关系
| 名称 | 运算封闭 | 结合律 | 单位元 | 逆元 |
|---|---|---|---|---|
| 广群 groupoid | √ | × | × | × |
| 半群 semigroup | √ | √ | × | × |
| 含幺半群 monoid | √ | √ | √ | × |
| 群 group | √ | √ | √ | √ |
自由半群 群元素为字母表，运算为连接两个元素
子群
子代数 对于群\(G\)，\(H\)为\(G\)的子群，当且仅当\(\forall a,b\in H\rightarrow a^{-1}b\in H\)。
乘积代数 半群\((S,*)\)和\((T,*')\)，定义新的半群\((S\times T,*'')\)，其中运算 \(*''\) 为 \[(s_1, t_1)*''(s_2, t_2)=(s_1*s_2, t_1*'t_2)\] 则\(S\times T\)中的元素为\(S\)、\(T\)中元素组合后得到的二元组合\((s,t)\)
商代数
同余关系 对于广群 \((S, *)\) 有关系 \(R\) 为同余关系，当且仅当 \(aRa'\wedge bRb'\rightarrow (a*b)R(a'*b')\) PS：同余关系必定为一个等价关系，即满足自反、对称、传递。
商广群 由于同余关系将原广群划分为了多个不同的广群，因此我们称这样的划分得到的群为商广群 \(G/R\)，群的元素为划分得到的等价类。
同态&同构
对于广群\((S,*)\)、\((T,*')\) ，有\(f(s_1*s_2)=f(s_1)*'f(s_2)\)若
- 对于\(s_1,s_2\in S\)均成立，则称\(f\)为一个同态 (homomorphism) 映射
- 满足第一点且\(f\)为一个双射（同时单射和满射），则\(f\)为一个同构 (isomorphism) 映射。
满同态定理 对于满同态映射\(f: S\rightarrow T\)，定义关系\(R: aRb \rightarrow f(a)=(b)\)，则有：
- \(R\)为一个同余关系。
- \(g:S/R\rightarrow T\) 为一个同构关系。即 \(R\) 对 \(S\) 的划分得到的等价类的集合和 \(T\) 中元素满足一对一映射关系。
图
匹配 指边的子集中，两两顶点互不相同的集合。
- 最大匹配：边数最多的匹配集合
- 完备匹配：能将二部图\((V_1,V_2), (V_1\cup V_2=V)\)中的所有顶点都匹配起来的匹配
图同构
两个图只有顶点的名字不同，其他完全相同。
- 必要不充分条件：两个图的图形不变量相同
通路与回路
连通图 仅针对无向图，如果无向图中的点两两连通，则说这个图是连通图。
强连通、弱连通 仅针对有向图，如果有向图中的点两两连通，则说这个图是强连通图；如果这个有向图不连通，但是与其对应的无向图连通，我们称这个图是弱连通的。
欧拉路径/回路
欧拉路径 包含所有边的一条通路
欧拉回路 包含所有边的一条回路
首先图必须要连通，然后
- 连通多重图有欧拉回路 \(\leftrightarrow\) 顶点度数均为偶数
- 联通多重图有欧拉路径 \(\leftrightarrow\) 仅有两个度为奇数的顶点。
使用 Fleury 算法构造欧拉路径 每次添加一条连接上一个选择的到的顶点，且不为割边（去掉后使得图不连通）的边，直到所有边都被添加。
哈密尔顿通路/回路
没有充要条件，pass
平面图以及着色
欧拉定理 对于连通的平面图，有\(r=e-v+2\)，其中，\(r\) 为由边划分得到的区域数量。
- 如果是有\(k\)个连通分量的平面图，则\(r=k+e-v+1\)
- 有\(n\)个顶点连通平面简单图\(G\)，有\(e\le 3n-6\)
- 对于连通平面简单图，且\(v\ge3\)、没有长度为 3 的回路，则有\(e\le 2v-4\)
Kuratowski 定理 一个图是平面图当且仅当它不含有任何可以通过\(K_5\)和\(K_{3,3}\)换点（将顶点换成边）得到的子图如下图。
图的着色 所有平面图都可以用五种颜色着色
有两种方法可以算出着色数，分别是朴素的算法以及着色多项式。
生成函数
一张表，慢慢背 ⑧