离散数学(2)

大一下学期离散数学(2)的复习笔记，目前已完结。

一、图论

1. 定义

  1. 空图：$|E|=0$
  2. 平凡图：$|V|=1$
  3. 不加说明时，图指无向图
  4. 无向图
    1. 多重图：有重边、无自环
    2. 伪图：有重边、有自环
    3. 简单图
      1. $k$-正则图：每个顶点的度数都为$k$
      2. 补图
    4. 二分图
    5. 连通支：极大连通子图；连通支个数 $p(G)$
    6. 点割集、边割集、点断集、边断集
      1. 割集：删除真子集不增加连通支数目
      2. 断集：只在连通图上有定义
    7. 点连通度 $k(G)$：点断集的最小值
    8. 边连通度 $\lambda(G)$：边断集的最小值
    9. 块（点双连通分量）：极大的无割点联通子图
  5. 有向图
    1. 外邻集：直接后继
    2. 内邻集：直接前驱
    3. 度数$=$入度$+$出度（不带负号）
  6. 最大度：$\Delta(G)$；最小度：$\delta(G)$
  7. 导出子图：节点集或边集
  8. 图同构：对节点重新编号
    1. 必要条件：顶点数、边数、度数列相同；存在同构的导出子图
    2. 图同胚：插入或消去 $2$ 度顶点后同构
  9. 图的对称差：顶点取并，边取对称差
  10. 道路与回路
    1. 有重复边、有重复点：通路/道路/回路
    2. 无重复边、有重复点：简单通路/简单回路
    3. 无重复边、无重复点：初级通路/路径/初级回路/圈
  11. 有向联通
    1. 可达；互相可达
    2. 弱联通：不考虑方向时联通
    3. 单向联通：任意两点存在一个可达方向
    4. 强联通：任意两点互相可达
  12. 距离 $d(u,v)$：短程线长度
  13. 弦：回路中不属于回路的边
  14. 欧拉回路：每条边恰好经过一次
  15. 哈密顿回路：每个顶点恰好经过一次
  16. 旅行商问题：完全图中最短的哈密顿回路
  17. 中国邮路：每条边至少经过一次的最短回路
  18. 最优二叉树：带权路径长度之和最小
  19. 可平面图；平面图（一个嵌入）；非平面图
  20. $\mathrm{Jordan}$ 曲线：连续的，自身不相交的，起点和终点相重合的曲线
  21. 面/域：平面图中不含节点及边的区域；面的次数 $\deg(R)$
  22. 极大平面图：$n\ge 3$ 的简单平面图，任意不相邻节点间加边都会破坏可平面性
  23. 极小非平面图：删除任意边后变成平面图（一定为简单图，$K_5,K_{3,3}$）
  24. 自对偶图：如轮图 $W_n$
  25. 色数：最少颜色数目；点色数 $\gamma(G)$；边色数 $\gamma^\prime(G)$；面色数 $\gamma^{\prime\prime}(G)$
  26. 极大匹配；最大匹配；交互道路；可增广道路；完全匹配；完美匹配；覆盖

2. 道路与回路

  1. 握手定理
  2. 割点的性质
    1. 存在与 $v$ 不同的两个顶点 $u$ 和 $w$，使得任一条 $u$ 到 $w$ 的道路 $P_{uw}$ 都经过 $v$
    2. 图 $V-v$ 可以划分为两个顶点集 $U$ 和 $W$，使得对任意顶点 $u\in U$ 和 $w\in W$，顶点 $v$ 都在每条道路 $P_{uw}$ 上
  3. 割边（桥）的性质
    1. 边 $e$ 不属于 $G$ 的任何圈
    2. 存在 $G$ 的顶点 $u$ 和 $w$，使 $e$ 属于 $u$ 和 $w$ 的任何一条道路 $P_{uw}$
    3. 图 $G-e$ 可以划分为两个顶点集 $U$ 和 $W$，使得对任意顶点 $u\in U$ 和 $w\in W$，道路 $P_{uw}$ 都经过 $e$
  4. 去掉点割集后连通分支数 $\ge 2$，去掉边割集后连通分支数 $=2$（去掉一条边最多让连通分支数 $+1$）
  5. 连通图中，$k(G)\le \lambda(G)\le \delta(G)$
  6. 块的性质
    1. $G$ 的任何两个顶点同属某一初级回路
    2. $G$ 的任何一个顶点和任何一条边同属某个初级回路
    3. $G$ 的任何两条边同属某个初级回路
    4. 给定两个点 $u,v$ 和一条边 $e$，存在一条包含 $e$ 的初级道路 $P_{uv}$
    5. 对 $G$ 的任意三个不同的顶点，存在一条包含它们的初级道路
    6. 对 $G$ 的任意三个不同的顶点，存在一条只包含其中两点而不含第三点的道路
  7. 连通图的 $k$ 笔画
    1. 无向图：$2k$ 个奇点（均为偶点则为欧拉图）
    2. 有向图：出度入度不平衡数（均平衡则为欧拉图）
  8. 哈密顿图判定
    1. 证伪
      1. 带有 $1$ 度顶点的图没有哈密顿回路
      2. $2$ 度顶点的两条边属于任何哈密顿回路
      3. 有割点的图不是哈密顿图
      4. 二分哈密顿图中 $|V_1|=|V_2|$
    2. 充分条件
      1. $\mathrm{H}$ 回路：简单图中任意两点 $d(u)+d(v)\ge n$
      2. $\mathrm{H}$ 道路：简单图中任意两点 $d(u)+d(v)\ge n-1$
    3. 必要条件
      1. $\mathrm{H}$ 回路：$p(G-S)\le |S|$，$S$ 为任意顶点集（能排成一个圈）
      2. $\mathrm{H}$ 道路：$p(G-S)\le |S|+1$，$S$ 为任意顶点集
    4. 充要条件
      1. 简单图中 $u,v$ 不相邻且 $d(u)+d(v)\ge n$，则 $G$ 有 $\mathrm{H}$ 回路等价于 $G+(u,v)$ 有 $\mathrm{H}$ 回路
      2. 简单图有 $\mathrm{H}$ 回路等价于其闭合图有 $\mathrm{H}$ 回路
  9. 中国邮路
    1. 充要条件
      1. 每条边最多重复一次
      2. $G$ 的任意一个回路上，重复边的长度之和不超过该回路长度的一半
    2. 欧拉图：欧拉回路
    3. 半欧拉图：欧拉道路 $+$ 奇点间最短路
    4. 非欧拉图：重复某些边后的欧拉回路
      1. 奇偶点图上作业法：补全奇点 $\to $ 检查回路 $\to $ 翻转回路
      2. 最小权匹配法：奇点集全源最短路 $\to $ 最小权匹配 $\to $ 重复边
    5. 有向图
      1. 添加超发超收点 $v_s,v_t$
      2. 求 $d(v_s)$ 条过以 $v_s, v_t$ 为两端点的形如 $(v_s, v_i), (v_j, v_t)$，每边一次且仅一次的总和最小的 $P_{st}$ 道路，记下 $G$ 中各边在这些道路里的重复次

3. 树

  1. 树的性质
    1. 任意两个顶点之间存在唯一的路径
    2. 无回路，且 $m=n-1$
    3. 连通，且 $m=n-1$
    4. 连通，且任何边均为割边
    5. 没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一一个含新边的回路
  2. 基本关联矩阵的性质（有向连通图）
    1. 关联矩阵/基本关联矩阵的秩为 $n-1$
    2. 关联矩阵/基本关联矩阵中回路所对应的各列线性相关
    3. 基本关联矩阵中行列式非零的 $n-1$ 阶子阵对应支撑树
    4. 关联矩阵任意子阵的行列式为 $0$ 或 $\pm 1$
  3. 支撑树的计数
    1. 有向图：$\det(B_kB_k^T)$
    2. 无向图：任意加方向变成有向图
    3. 含边：总数 $-$ 不含（去边）或缩点
    4. 根树：$\det(\vec{B_k}B_k^T),\vec{B_k}$ 为 $B_k$ 中将 $1$ 变成 $0$
  4. 基本回路矩阵的性质（有向连通图）
    1. 基本回路：余树边所对应的回路，方向与余树边相同
    2. 基本回路矩阵调换顺序后变成 $[I,C_{f_{12}}]$，$I$ 对应余树
    3. 关联矩阵与完全回路矩阵的边对应时，$BC_e^T=0$
    4. 基本回路矩阵/完全回路矩阵的秩为 $m-n+1$
    5. 回路矩阵：由任意 $m-n+1$ 条线性无关的回路所组成的矩阵
      1. 同样满足 $BC^T=0$
      2. 可由基本回路矩阵做可逆变换得到
    6. 回路矩阵中行列式非零的 $m-n+1$ 阶子阵对应余树
    7. 若基本关联矩阵和基本回路矩阵的边次序相同，则 $C_{f_{12}}=-B_{11}^TB_{12}^{-T}$
  5. 基本割集矩阵的性质（有向连通图）
    1. 基本割集：树边所对应的割集，方向与树边相同
    2. 基本割集矩阵调换顺序后变成 $[S_{f_{11}},I]$，$I$ 对应树
    3. 完全回路矩阵与完全割集矩阵的边对应时，$S_eC_e^T=0$
    4. 基本割集矩阵/完全割集矩阵的秩为 $n-1$
    5. 割集矩阵：由任意 $n-1$ 个线性无关的割集所组成的矩阵
      1. 同样满足 $SC^T=0$
      2. 可由基本割集矩阵做可逆变换得到
    6. 割集矩阵中行列式非零的 $n-1$ 阶子阵对应树
    7. 若基本割集矩阵与基本回路矩阵的边次序相同，则 $S_{f_{11}}=-C_{f_{12}}^T=B_{12}^{-1}B_{11}$

4. 平面、对偶与染色

  1. $\mathrm{Jordan}$ 曲线定理：连接 $\mathrm{int}J$ 的点和 $\mathrm{ext}J$ 的点的任何连线必在某点和 $J$ 相交
    1. 推论：$K_5$ 是非平面图
  2. 不是割边的边必为某两个域的公共边界（割边 $\deg$ 数两次）
  3. 测地变换
    1. 可平面等价于可球面
    2. 可将任何一个内部域改换为外部域
  4. 平面图的判定定理
    1. 平面图的任何子图都是平面图
    2. $K_n(n\le 4),K_{1,n}(n\ge 1),K_{2,n}(n\ge 2)$ 是平面图
    3. $K_n(n\ge 5),K_{3,n}(n\ge 3)$ 是非平面图
    4. 重边和自环不影响可平面性
    5. $\mathrm{Kuratowski}$ 定理：图 $G$ 是平面图当且仅当：
      1. $G$ 中不含与 $K_5,K_{3,3}$ 同胚的子图
      2. $G$ 中不含可边收缩到 $K_5,K_{3,3}$ 的子图
  5. 平面图与点数、边数、面数
    1. $\sum \deg(R_i)=2m$
    2. $\mathrm{Euler}$ 定理：$n-m+r=p(G)+1$
    3. 简单连通平面图中，若每个域边界数至少为 $t$，则 $m\le (n-2)\frac{t}{t-2}$
    4. 简单连通平面图为极大平面图 $\Leftrightarrow \forall R_i,\deg(R_i)=3 \Rightarrow 3r=2m$
    5. 极大平面图 $m=3n-6,r=2n-4$
    6. 简单连通平面图 $m\le 3n-6,r\le 2n-4$
    7. 简单连通平面图中 $\delta \le 5$
  6. 平面图的判定算法
    1. 检测每个连通支，移去连通支中的割点，检测每个块
    2. 移去自环，消去 $2$ 度顶点，移去重边，直到无法继续进行
    3. 若 $m\lt 9$ 或 $n\lt 5$，则是平面图
    4. 若 $m\gt 3n-6$，则是非平面图
  7. 对偶图的性质
    1. 有且仅有平面图有对偶图，且对偶图唯一
    2. 同构的两个图，对偶图不一定同构
    3. 对偶图是连通图
    4. 对偶图是平面图
    5. 对偶图中的割集对应原图中的圈
  8. 特例图的点色数
    1. 奇圈：$3$；偶圈：$2$
    2. 奇阶轮图：$4$；偶阶轮图：$3$
    3. $\gamma(G)=2 \Leftrightarrow G$ 是二分图 $\Leftrightarrow G$ 无奇圈
    4. 树：$2$
    5. 平面连通图 $G$ 的域可 $2$ 着色当且仅当 $G$ 是欧拉图
  9. 点色数的估计与确定
    1. 对于任意不含自环的图，有 $\gamma(G)\le \Delta(G)+1$
    2. 若连通图 $G$ 不是完全图，也不是奇圈，则 $\gamma(G)\le \Delta(G)$
    3. $\mathrm{Welch-Powell}$ 近似算法：按度数从大到小排列，逐个染色
    4. 记 $\mathring{G_{ij}},\overline{G_{ij}}$ 分别为 收缩和连接 $i,j$ 后的图，则 $\gamma(G)=\min\{\gamma(\mathring{G_{ij}}),\gamma(\overline{G_{ij}})\}$
  10. 点色数多项式
    1. $f(G,t)$：最多用 $t$ 种颜色染色 $\Rightarrow t\lt \gamma(G),f(G,t)=0$
    2. 记 $m_i$ 为正好用 $t$ 种颜色染色，则 $m_i$ 只有在 $\gamma(G)\le i\le \min\{t,n\}$ 时才不为零，$\displaystyle f(G,t)=\sum_{i=1}^n m_iC(t,i)$
    3. $f(K_n,t)=t(t-1)(t-2)\cdots(t-n+1)$
    4. $f(T_n,t)=t(t-1)^{n-1}$
    5. $f(G,t)=f(\overline{G_{ij}},t)+f(\mathring{G_{ij}},t)$
  11. 边着色
    1. 转化为点着色：每个边上取一个点；两条边若关联于同一个点则连一条边
    2. $\mathrm{Vizing}$ 定理：简单图中 $\Delta(G)\le \gamma^\prime(G)\le \Delta(G)+1$
    3. 特例边色数
      1. 偶圈：$2$；奇圈：$3$
      2. 轮图 $W_n$：$n-1$
      3. 奇完全图 $K_n$：$n$；偶完全图：$n-1$
  12. 面着色
    1. 等价于对偶图的点着色
    2. 六色定理、五色定理、四色定理
    3. 若任意 $3-$ 正则平面图可面 $4$ 着色，则四色猜想成立
    4. 哈密顿平面图可面 $4$ 着色
    5. $\mathrm{Tait}$ 猜想：任意 $3-$ 正则平面图都是哈密顿图（不成立）

5. 匹配与网络流

  1. 可增广道路一定包含奇数条边，且其中不属于原匹配的边多一条
  2. $M$ 为 $G$ 的最大匹配，当且仅当 $G$ 中不含关于 $M$ 的可增广道路
  3. $\mathrm{Hall}$ 定理（相异性条件）：二分图中存在 $V_1$ 到 $V_2$ 的完全匹配当且仅当 $V_1$ 中任意 $k$ 个顶点至少与 $V_2$ 中的 $k$ 个顶点相邻
  4. $k$ 条件：若 $V_1$ 中的每个顶点度数都不少于 $k$，$V_2$ 中的每个顶点度数都不大于 $k$，则 $G$ 中存在 $V_1$ 到 $V_2$ 的完全匹配
  5. 二分图中从 $X$ 到 $Y$ 的最大匹配数是 $|X|-\delta (G)$，其中 $A$ 为 $X$ 中任意个数节点的子集，$\displaystyle \delta (G)=\max_{A\subseteq X} \delta (A),\delta (A)=|A|-|N(A)|$，$N(A)$ 为 $A$ 的邻接点集
  6. $\mathrm{König}$ 定理：二分图中最大匹配数等于最小覆盖数
  7. 网络流图中，其最大流量等于其最小割切的容量

6. 证明与建模

  1. 道路与回路
    1. 证明：非空简单图中一定存在度相同的顶点
    2. 证明：对于任意 $(n+1)^2$ 项的递增的自然数列，要么存在 $n+3$ 项的子列，使任一项能整除此子列中它后面的每一项；要么存在 $n+1$ 项的子列，使此子列中任一项不能整除此子列中它后面的任何一项
    3. 证明：无向图中若所有点度数 $\ge 2$，则存在回路
    4. 证明：若连通图的最长道路不唯一，则它们必定相交
    5. 证明：简单图中若每个顶点度数 $\ge 3$，则存在带弦的回路
    6. 证明：$6$ 个人中或者有 $3$ 个人互相认识，或者有 $3$ 个人互相不认识
    7. 证明：$9$ 个人中若非至少有 $4$ 个人互相认识，则至少有 $3$ 个人互相不认识
    8. 证明：在有 $k$ 个连通支的简单图中，$m\le \frac{1}{2}(n-k+1)(n-k)$
    9. 证明：简单图中，若 $n\ge 4,m\ge 2n-3$，则含有带弦的回路
    10. 证明：简单连通图中，$k(G)\le \lceil \frac{2m}{n} \rceil$
    11. 证明：在不含 $K_3$ 的简单图中，
      1. $\sum d^2(v_i)\le mn$（技巧：所有顶点的邻居的度数之和为 $\sum d^2(v_i)$）
      2. $(\mathrm{Mantel})$ $m\le \frac{1}{4}n^2$
    12. 设 $G$ 是有 $n$ 个顶点的简单图，其最小度 $\delta(G)\ge \frac{n+q}{2}$，证明 $G$ 中存在包含任意 $q$ 条互补相邻边的哈密顿回路
    13. 对任意 $n\ge 3$，在 $K_n$ 中有多少个无公共边的哈密顿回路？
  2. 树
    1. 定义树的中心为以其为端点的最长初级道路长度最小的顶点，证明：任意一棵树至多有两个中心，且当有两个中心时，这两个中心相邻
    2. 证明：对于一棵 $2n$ 个顶点的树 $T$，有完美匹配当且仅当对于任意顶点 $u$，从 $T$ 中删去 $u$ 得到的导出子图 $T-u$ 的若干个连通分支中，恰有一个连通分支的点数为奇数
    3. 设 $G$ 是无向图，对任意顶点 $v\in V(G)$，$G-v$ 仍是连通图，而且 $G$ 的基本割集矩阵 $S_f$ 的每一行都有偶数个 $1$ 元素，证明 $G$ 中有欧拉回路
  3. 平面、对偶与染色
    1. 证明：无法将五边形分割成有限个三角形且无奇点
    2. 证明：顶点数 $n\lt 12$ 的平面图的点和域都是 $4-$ 可着色的
    3. 设简单平面图 $G$ 的顶点数 $n\ge 4$，证明 $G$ 中至少有 $4$ 个顶点的度不大于 $5$
    4. 设 $G$ 是每个面都是三角形的平面图，现用 $3$ 种颜色对它的所有顶点任意着色，证明：顶点上恰好得到了这 $3$ 种颜色的面的数目是偶数个
    5. 证明：边数 $\lt 30$ 的简单平面图可以点 $4-$ 可着色
    6. 设 $G$ 是有 $n$ 个顶点的 $k-$ 正则图，证明：$G$ 的点色数 $\le \frac{n}{n-k}$
    7. 证明：若简单平面图中 $r\lt 12$，且每个点度数 $\ge 3$，则至少有一个域的边界数 $\lt 5$
  4. 建模题
    1. 穿行房间问题（对偶图）
    2. 计算机编码盘设计（欧拉图）
    3. 打鸟、放机器人（二分图匹配）
    4. 工作任务分配、逃生路线（网络流）

7. 图论算法

  1. 图的代数表示
    1. 邻接矩阵
    2. 权矩阵
    3. 关联矩阵
    4. 边列表
    5. 正向表：节点从 $0$ 开始编号；$[A_i,A_{i+1})$；$A$ 长度 $n+1$
    6. 邻接表
    7. 十字链表
  2. 连通性
    1. 全源：$\mathrm{Warshall}$ 算法
    2. 单源：$\mathrm{BFS,DFS}$
  3. 构造欧拉图
    1. 找回路 $\to $ 余图找新回路 $\to $ 以公共点为起末连接
  4. 旅行商问题
    1. 分支定界：按边权从小到大排序 $(O(n!))$
    2. 近似算法：插点法 $(O(n^2))$
    3. 近似解/最优解 $\lt 2$
  5. 最短路
    1. 单源正边权：$\mathrm{Dijkstra}$ 算法 $(O(n^2))$
    2. 单源负边权：$\mathrm{Bellman-Ford}$ 算法 $(O(nm))$
    3. 单源 $1$ 边权：$\mathrm{BFS}$ $(O(m))$
    4. 全源：$\mathrm{Floyd}$ 算法 $(O(n^3))$
    5. $\mathrm{Bellman-Ford}$ 负环不终止，$\mathrm{Floyd}$ 不正确
  6. 关键路径
    1. $\mathrm{PT}$ 图拓扑排序
    2. 最大允许延误时间：反向求最晚启动时间，再相减
  7. 支撑树的生成：避圈法
  8. 最小支撑树
    1. $\mathrm{Prim}$ 算法 $(O(n^2)\to O(m\log n))$
    2. $\mathrm{Kruskal}$ 算法 $(O(m+p\log m),p\in (n,m))$
    3. 判断是否形成回路：并查集
      1. 优化 1：路径压缩
      2. 优化 2：小并入大/低并入高
    4. 稠密图用 $\mathrm{Prim}$，稀疏图用 $\mathrm{Kruskal}$
  9. 最优二叉树
    1. $\mathrm{Huffman}$ 算法：按权值从小到大排序，两两合并
    2. 应用：编码
      1. 前缀码：若字符串集合中两两互不为前缀
      2. 二元前缀码：只出现 $0,1$ 的前缀码
      3. 最佳前缀码：由最优二叉树产生的二元前缀码
      4. 最佳前缀码不唯一（左右可互换）
  10. 二分图匹配
    1. 最大匹配：匈牙利算法 $(O(mn))$
    2. 最佳匹配：网络流
  11. 网络流
    1. 最大流：$\mathrm{Ford-Fulkerson}$ 算法

二、群论

1. 代数系统

  1. 基本定义
    1. 代数系统：非空集合、运算满足映射条件且封闭
    2. 同类型代数系统：都是 $k_i$ 元运算
    3. 同构映射：双射且 $f(a\circ b)=f(a)*f(b)$
    4. 同态映射：可以不是双射（单射：单一同态；满射：满同态，$X\cong Y$，$Y$ 是 $X$ 的同态像）
    5. 子代数系统：非空子集、封闭
  2. 基本定理
    1. 若左右单位元同时存在，则两者相等且为唯一单位元
    2. 有结合律时若左右逆元同时存在，则两者相等且为唯一逆元
    3. 同态映射的像构成子代数系统
    4. 满同态保交换律、结合律、单位元、逆元

2. 群的基本概念

  1. 基本定义
    1. 半群：非空集合、二元运算、封闭、结合律
    2. 幺群（含幺半群）：半群、单位元
    3. 交换幺群：幺群、交换律
    4. 循环幺群：存在生成元（一定是交换幺群）
    5. 子半群：非空子集、封闭
    6. 子幺群：非空子集、封闭、单位元在子集内
    7. 群：幺群、逆元
    8. 交换群（阿贝尔群）：群、交换律
    9. $\mathrm{Klein}$ 四元群：$\{e,a,b,c\},a^2=e,ab=c$
    10. 平凡群：只含单位元的群
    11. 元素的阶：$O\langle a\rangle$
    12. 子群：非空子集、封闭、单位元和逆元在子集内
  2. 群的判定定理
    1. 有限半群上的运算若满足消去律，则为群（无限半群不一定，如正整数乘法）
    2. 若半群有左单位元和左逆元，则为群
    3. 半群中若对任意两个元素 $a,b$，$ax=b,ya=b$ 有解，则为群
    4. 非空子集是子群等价于 $ab^{-1}\in H$
  3. 元素的阶
    1. 小于等于群的阶
    2. 与其逆元的阶相等
    3. 推论：对有限阶元素 $a,b$，$O\langle b^{-1}ab\rangle=O\langle a\rangle, O\langle ab\rangle=O\langle ba\rangle$
    4. 存在所有元素的阶都有限的无限群（如自然数幂集上的对称差）
  4. 子群的性质
    1. 两个子群的交集仍然是子群
    2. $\{a^k\}$ 是子群
    3. $HH=H$ 不能推出 $H$ 是子群：取 $G=\{\mathbb{Q}-\{0\},*\}$，$H$ 为全体奇数（没有逆元）
    4. 不存在群是其两个真子群的并
    5. 存在群是其三个真子群的并：取 $G=K_4,H_1=\{e,a\},H_2=\{e,b\},H_3=\{e,c\}$
    6. 不存在只有有限个子群的无限群：分有无无限阶元素讨论

3. 特殊的群

  1. 循环群
    1. 无限阶循环群只有生成元 $a,a^{-1}$，有限阶循环群有 $\varphi(O(a))$ 个生成元（$\varphi$：小于 $n$ 且与 $n$ 互素）
    2. 无限阶循环群的子群仍是无限阶循环群
    3. $n$ 阶循环群的子群生成元阶数是 $n$ 的因子，且每个因子都只对应一个子群
    4. 无限阶循环群与 $(\mathbb{Z},+)$ 同构，$n$ 阶循环群与 $(\mathbb{Z}_n,+)$ 同构
  2. 变换群与置换群
    1. 非空集合上的映射称为一个变换，有限集合上的一一变换称为 $n$ 元置换
    2. 非空集合 $A$ 的所有一一变换关于变换的乘法所构成的群叫做 $A$ 的一一变换群，记作 $E(A)$，$E(A)$ 的子群叫做变换群
    3. $S(n)$：$n!$ 个 $n$ 元置换的集合，$S(n)$ 关于置换乘法的群叫做 $n$ 次对称群，其子群叫做置换群
    4. 不相交的轮换满足交换律
    5. 任何 $n$ 元置换都可以唯一地表示为不相交的轮换的乘积
    6. 任何一个轮换都可表示成对换的乘积，且不唯一
    7. 置换的逆序数与其对换表示中对换个数的奇偶性相同（奇置换、偶置换）
    8. 偶置换关于置换乘法构成的群叫做交错群，记作 $A(n)$
    9. $\mathrm{Cayley}$ 定理：任意群与一个变换群同构（$n$ 阶有限群与 $S(n)$ 的一个子群同构）
    10. 轮换计算技巧：首尾相接

4. 群的分解

  1. 陪集的性质
    1. 设 $H$ 是 $G$ 的子群，则 $a\in H\Leftrightarrow aH=H$
    2. $\forall x\in aH,xH=aH$，并称 $a$ 是 $aH$ 的陪集代表
    3. $aH=bH\Leftrightarrow a\in bH$ 或 $b\in aH\Leftrightarrow b^{-1}a\in H$ 或 $a^{-1}b\in H$
    4. 若非 $aH=bH$，则 $aH\cap bH=\emptyset$
  2. 群的陪集分解
    1. 群 $G$ 关于其子群 $H$ 的左陪集的个数称为 $H$ 在 $G$ 中的指数，记作 $[G:H]$
    2. $\mathrm{Lagrange}$ 定理：$|G|=[G:H]|H|$（子群的阶是群的阶的因子）
    3. 推论：$n$ 阶群中任意元素的阶都是 $n$ 的因子（素数阶的群是循环群）
    4. 推论：设 $A,B$ 是 $G$ 的有限子群，则 $|AB||A\cap B|=|A||B|$
  3. 正规子群与商群
    1. 定义：$\forall a\in G,aH=Ha$，记作 $H\triangleleft G$
    2. 判定定理：$H\triangleleft G\Leftrightarrow \forall g\in G,h\in H,ghg^{-1}\in H$
    3. 若 $A,B$ 是正规子群，则 $AB,A\cap B$ 也是正规子群
    4. 若 $A$ 是正规子群，$B$ 是子群，则 $A\cap B$ 是 $B$ 的正规子群，$AB$ 是 $G$ 的子群
    5. 设 $H$ 是正规子群，$G/H$ 表示 $H$ 的所有陪集构成的集合，则 $G/H$ 关于陪集乘法构成群，称为 $G$ 关于 $H$ 的商群
    6. 商群性质：$aHbH=abH$

5. 例题

  1. 证明：$6$ 阶群一定存在一个 $3$ 阶子群
  2. 设 $G$ 是群，$H_1,H_2$ 是 $G$ 的子群，证明：$H_1H_2$ 是 $G$ 的子群当且仅当 $H_1H_2=H_2H_1$
  3. 证明：有限半群中一定存在 $x^2\in S$，满足 $x^2=x$，但无限半群中不一定
  4. 设 $G$ 是群，$x,y\in G$，称所有形如 $xyx^{-1}y^{-1}$ 的元素为换位子，群 $G$ 的所有换位子构成的子群称为 $G$ 的换位子群 $G^{\prime}$，证明：
    1. $G^{\prime}$ 是 $G$ 的正规子群
    2. $G/G^{\prime}$ 是交换群
  5. $(2024)$ 证明：有限 $\mathrm{Abel}$ 群 $G$ 中，$\displaystyle \prod_{g\in G} g=\prod_{a\in G,a^2=e} a$，其中 $e$ 是 $G$ 的单位元
笔记
#数学 #大一下
离散数学(2)
https://sqzr2319.github.io/DiscreteMath-2/
作者
sqzr2319
发布于
2025年6月12日
许可协议