离散数学期末复习（自用）
VLSMB9 代数系统
代数系统的平凡子代数：
同态与同构：
同构必要条件：
同构的性质：保持结合律、交换律、幺员存在性、零元存在性、逆元存在性。如果代数系统含有两个运算则保持分配律、吸收律。
同态性的保持是单一方向的。
10 群与环
半群、交换半群、子半群、独异点、交换独异点、子独异点、群
群的性质：可消去性、群方程唯一解、群中无零元、群中除了幺元以外无其他幂等元
群的阶：
特殊群：交换群、循环群
循环群只与两种群同构：
循环群都是交换群
证明子群的方法：
子群的陪集：
拉格朗日定理：n阶群的子群的阶数必定是n的因子，且每个元素的阶必定是n的因子。
G的阶数n如果为素数的话，则无非平凡子群且必定为循环群。
环的定义：二元运算，+为交换群，为半群。
+的幺员为的零元。也是环的零元。
可交换环：*为交换半群。
含幺环：*为独异点。
含零因子、无零因子。若为可交换含幺无零因子环，则为整环。
域的定义：
11 格与布尔代数
偏序集：
格的定义：任意两个元素都有上下确界
平凡格：所有全序都是格，称之为平凡格。
格的对偶原理：
格的性质：
- a&b和a、b的关系
- 偏序可以传递、反对称
- 格具有保序性
- 交换律
- 幂等律
- 结合律
- 吸收律
- 分配不等式
- a小于等于b，等价于a与b的下界为a，上界为b
格的同态与同构：
格同构，它们的哈斯图的形状一定相同。
分配格：满足分配律
有界格：
有界格定义：如果一个格存在全上界1与全下界0，则称此格为有界格。
所有有限个元素的格都是有界格
而无限个元素的格可能是无界格。
有补格的定义：一个有界格中,如果每个元素都有补元,则称之为有补格。
如果一个格既是分配格又是有补格，则称之为布尔格。
布尔代数的性质：
Stone原理：
任何有限布尔代数的元素个数为2的n次方。
两个有限布尔代数同构的充分且必要条件是元素个数相同。对于任何自然数n, 仅存在一个布尔代数。
14 图论
握手定理：
正则图的定义：最大度和最小度都为k
点割集与边割集（割集使连通分量变多）：
完全图中，点连通度、边连通度均为n-1；非连通图，均为0。
点连通度、边连通度、最小度的大小关系。
邻接矩阵：
可达矩阵：
关联矩阵：
15 欧拉图 哈密顿图
欧拉图定义：
无向图G是欧拉图当且仅当G连通且无奇度数顶点。
无向图G是半欧拉图当且仅当G 连通且恰有
两个奇度顶点。
有向的：
构造欧拉回路：圈之并。
哈密顿图的定义：
哈密顿图具有的性质：
判断哈密顿图：
$n \ge 2$竞赛图具有哈密顿通路。
16 树
无向树：
设T是n阶非平凡的无向树，则T 中至少有两片树叶。
生成树：
G为n阶m条边的无向连通图，则$m \ge n-1$
基本回路系统：
基本割集系统：
根数的分类：
17 平面图
平面图：将无向图G除了顶点外无边相交画出来
平面图各面次数之和等于边数的两倍。
极大平面图，则G的每个面的次数均为3，充要条件。
若在非平面图G中任意删除一条边，所得图为平面图，则称G为极小非平面图。
欧拉公式以及推论：
每一个面的度数都大于等于l的时候，有边m小于等于的关系。
设G为$n（n \le 3）$阶m条边的简单平面图，则$m \le 3n-6$。若为极大平面图，则取等。
设G为简单平面图，则G的最小度数$\le 5$。
平面图的判断：
G中不含与$K_5$或$K_{3,3}$同胚或无可收缩成$K_5$或$K_{3,3}$的子图。
平面图的对偶图：
对偶图的性质：
自对偶图：
18 匹配与着色
二部图的定义：
二部图判定定理：当且仅当G中无奇数长度的圈。
二部图的匹配：
判断完备匹配的定理：
二部图的匹配算法：每次选择度最小的节点。
四色定理：平面图的色数不超过4。
点着色：
色数：
- 零图：1
- n完全图：n
- 奇数轮图：3
- 偶数轮图：4
- 二部图（非空边）：2
着色方法：先找度数最大的节点，给他和他不相邻的涂上一个颜色。
色数的上界：
地图着色：
边着色：
边着色的色数：
- G为简单平面图，只能为最大度数或者加一
- n奇数完全图为n，偶数完全图为n-1
- 二部图为最大度数
- 轮图为n-1（n大于等于4时）
