离散数学复习 (III)

期末考试时间: 2026.01.07

为了打字方便, 用 代替 .

第六章 (I) 群、环、域

1. 半群, 幺半群.

2. 幺半群的常见例子: .

3. 群.
4. 群的常见例子: .
5. Klein 四元群.
6. 有限群与无限群. 群的阶.
7. 平凡群.
8. 交换群/Abel 群.
9. 群中元素的幂. 幂的性质.
10. 群中元素 的阶 . 若 存在, 则: (i) ; (ii) 当且仅当 .
11. 设 是群 的元素, 则方程 在 中有唯一解 , 方程 在 中有唯一解 .
12. 群的运算满足消去律.
13. 群中的唯一幂等元是 .
14. 设 为群. 若 是 的非空子集, 且 关于 的运算与单位元构成群, 则称 是 的子群, 记作 .
15. 设 为群. 若 为 的非空子集, 且 关于 的运算构成群, 则 .
    证 只需证明 , 也就是证明 . 事实上, 由 知 .
16. 子群判定定理: 设 为群, 为 的非空子集, 则 的充分必要条件是 .
17. 设 为群 的元素, 令 , 则由子群判定定理可知 . 称 为 的由 生成的子群.
18. 设 为群, 令 , 可以通过子群判定定理证明 . 称 为 的中心.
19. 设 为群 的子群, 则: (i) ; (ii) .
20. 循环群与生成元.
21. 循环群的常见例子: .
22. 若 是循环群, 则:
    (a) 若 为无限群, 则对任意两个不同的整数 , 有 .
    (b) 若 为 阶有限群, 则 且 互不相同.
23. 若 是循环群, 则:
    (a) 若 为无限群, 则只有 和 是 的生成元.
    (b) 若 为 阶有限群, 则 有 个生成元. (使用 Bezout 定理证明.)
24. 若 是循环群, 则 的子群都是循环群. ( 是无限群时显然; 否则设子群有两个元素 , 使用 Bezout 定理.)
25. 置换及其符号. 置换的乘法 (积).
26. 轮换及其符号.
27. 任何置换都可分解为若干个不交的轮换的积. (用图论证明.)
28. 全体 元置换关于置换的乘法构成群, 称为 元对称群, 记作 . 的子群称为 元置换群.
29. 陪集.
30. 设 为群 的子群, 则 的所有不同的左陪集形成 的一个划分.
31. Lagrange 定理: 若 阶有限群 是 阶有限群 的子群, 则 且 在 中的不同的左陪集的个数为 .
32. 环. 零元 , 幺元 , 负元 , 逆元 .
33. 环的常见例子: .
34. 交换环, 幺环, 无零因子环, 整环.
35. 幺环的幺元不等于零元, 除非此幺环只有一个元素.
36. 若 为环 的元素, 则 .
37. 若环 的元素个数大于 , 则 不是群.
38. 整环的常见例子: .
39. 域.
40. 若 是域, 则 和 是 Abel 群.
41. 域的常见例子: .
42. 为合数时, 不是整环; 但 为素数时, 不仅是整环, 还是域.

第六章 (II) 格与布尔代数

1. 格. 最小上界 与最大下界 .

2. 格的常见例子:

   • 设 , 是 的正因子的集合, 为整除关系, 则 是格, 其中 , .
   • 设 为一个集合, 则 是格, 其中 .
   • 是格, 其中 .
3. 格的最小上界运算 与最大下界运算 满足交换律、结合律、幂等律、吸收律.
4. 若代数系统 $(S,\,,\,\circ)\circS\preceq(S,\,\preceq)x,\,y\in Sx\land y=x*y,\,x\lor y=x\circ y$.
5. 子格.
6. 格的同构.
7. 分配格.
8. 分配格判定定理:
   (a) 格 是分配格的一个充分必要条件是 不含有与钻石格和五角格同构的子格.
   (b) 格 是分配格的一个充分必要条件是, 对任意 , 若 且 , 则 .
9. 全下界 , 全上界 . 有界格.
10. 有限格都是有界格.
11. 设 为一个集合, 则 是有界格.
12. 设 为有界格 的元素, 若 满足 , 则称 为 的补元.
13. 有补格.
14. 在分配格中, 若一个元素存在补元, 则它的补元是唯一的.
15. 布尔代数/布尔格 .
16. 布尔代数的等价定义: 代数系统 $(B,\,,\,\circ)\circ0,\,1\in Ba\in Ba1=a\circ0=aa\in Ba’\in Baa’=0,\,a\circ a’=101$ 的定义见上一项.
17. 若 为布尔代数, 则任意 满足 .

第七章 图的基本概念

1. 图的各种基本定义. 本书只讨论有限图.

2. 空图, 平凡图.

3. 关联次数.
4. 度 , 入度 , 出度 .
5. 孤立点, 悬挂点, 悬挂边.
6. 最大度 , 最小度 , 最大出度, 最小出度, 最大入读, 最小入度.
7. 度数之和与边数的关系.
8. 度数为奇数的顶点的个数是偶数.
9. 简单图与多重图.
10. 无向完全图 与有向完全图.
11. - 正则图. 阶 - 正则图的边数 .
12. 生成子图. 导出子图 ( 和 ).
13. 补图.
14. 图的同构.
15. 通路及其长度. 回路. 简单通路, 简单回路, 路径, 圈, 复杂通路, 复杂回路.
16. 若 到 存在通路, 则 到 存在路径.
17. 连通. 连通图.
18. 连通关系将顶点集划分为若干等价类, 由它们导出的子图称为连通分支. 连通分支的个数记为 .
19. 最短路径与距离.
20. 使得 的极小的 称为点割集. 点割集中的点称为割点.
21. 使得 的极小的 称为 (边) 割集. 割集中的边称为割边/桥. 若 为割集, 则 .
22. 点连通度 , 边连通度 .
23. .
24. 可达, 相互可达.
25. 弱连通图, 单向连通图, 连通图.
26. 关联矩阵, 邻接矩阵.
27. 通过邻接矩阵求两点之间特定长度的通路的数量.
28. 可达矩阵.

第八章 树

1. 树, 平凡树, 森林, 树叶, 分支点.

2. 对于 条边的 阶图 , 以下命题等价:
   (a) 为树;
   (b) 的每对顶点之间有唯一的路径;
   (c) 连通, 且 ;
   (d) 无圈, 且 ;
   (f) 连通, 且 的边均为桥;
   (e) 无圈, 且在 中任何两个不相邻的顶点之间增加一条边, 就得到圈.

3. 非平凡树至少有两片树叶.
4. 生成树, 树枝, 弦, 余树. 余树一般不是树.
5. 无向连通图都有生成树.
6. 无向连通图都满足 .
7. 基本回路, 基本回路系统.
8. 基本割集, 基本割集系统.
9. 带权图. 边的权 , 图的权 .
10. 最小生成树.
11. 有向树.
12. 若一棵非平凡的有向树, 除一个顶点入度为 外, 其余顶点入度均为 , 则称之为根树, 称入度为 的点为树根, 称出度为 的点为树叶, 称其余点为内点. 内点和树根统称分支点.
13. 层数 , 树高 .
14. 子点, 父点, 祖先, 后代.
15. 根子树.
16. 元树, 元正则树, 元完全正则树.

第九章 二部图、欧拉图、哈密顿图

1. 二部图, 互补顶点子集.

2. 完全二部图.

3. 二部图判定定理: 一个无向图是二部图的充分必要条件是它没有长度为奇数的圈.
4. 匹配. 极大匹配, 最大匹配.
5. 饱和点与非饱和点. 完美匹配.
6. 完备匹配.
7. Hall 定理: 二部图 有完备匹配的充分必要条件是对于 , 中的任意 个顶点至少与 中的 个顶点相邻.
8. 欧拉通路, 欧拉回路, 欧拉图.
9. 无向图 有欧拉通路的充分必要条件是 连通且度数为奇数的顶点不超过 个.
10. 无向图 有欧拉回路的充分必要条件是 连通且所有顶点度数均为偶数.
11. 有向图 有欧拉回路的充分必要条件是 弱连通且所有顶点都满足入度等于出度.
12. 阶有向图 有欧拉通路但无欧拉回路的充分必要条件是 弱连通且各个顶点的入度与出度之差包括一个 、一个 与 个 .
13. 哈密顿通路, 哈密顿圈, 哈密顿图.
14. 若无向图 为哈密顿图, 为 的非空真子集, 则 .
15. 若无向图 有哈密顿通路, 为 的非空真子集, 则 .
16. 设 为 阶无向简单图. 若对 中每一对不相邻的顶点 , 都有 , 则 有哈密顿通路.
17. 设 为 阶无向简单图. 若对 中每一对不相邻的顶点 , 都有 , 则 是哈密顿图.
18. 设 为 阶无向简单图. 若 , 则 为哈密顿图.

第十章 平面图及其着色

1. 平面图, 非平面图, 平面嵌入/表示.

2. 面, 无限面/外部面, 有限面/内部面. 边界, 次数 .

3. 面的次数之和等于边数的 倍.
4. 欧拉公式: 若连通平面图 有 个顶点, 条边, 个面, 则 .
5. 有 个连通分支的平面图满足 .
6. 若连通平面图 的每个面的次数都不小于 , 则 .
7. 同构, 同胚, 收缩.
8. Kuratowski 定理: 对于图 , 下列命题等价:
   (a) 是平面图;
   (b) 没有与 $K5K{3,3}GK5K{3,3}$ 的子图.
9. 平面图的对偶图.
10. (点) 着色. - 可着色, 色数 .
11. (a) 为奇数时, ; 为偶数时, .
    (b) 非空图 的色数为 的充分必要条件是 为二部图.