本科课程 · 离散数学 ②
代数结构与图论
把运算本身当作研究对象：群、环、域刻画"对称与解方程"的抽象结构；图用点和线装下网络、路线与关系。两条线索在密码学（RSA 用 Z_p*）、编译器（自动机用半群）与算法（图遍历）中殊途同归。
1 代数系统与二元运算
概念运算的性质就是结构的基因
二元运算 ∗: S×S → S 的四条基本性质：
① 封闭：∀a,b ∈ S, a∗b ∈ S；② 结合：(a∗b)∗c = a∗(b∗c)；
③ 幺元 e：e∗a = a∗e = a（若存在则唯一）；④ 逆元：a∗a⁻¹ = e（在含幺半群里唯一）。
交换律独立于以上四条。半群（封闭+结合）⊂ 单半群（+幺元）⊂ 群（+逆元）。
① 封闭：∀a,b ∈ S, a∗b ∈ S；② 结合：(a∗b)∗c = a∗(b∗c)；
③ 幺元 e：e∗a = a∗e = a（若存在则唯一）；④ 逆元：a∗a⁻¹ = e（在含幺半群里唯一）。
交换律独立于以上四条。半群（封闭+结合）⊂ 单半群（+幺元）⊂ 群（+逆元）。
2 群、子群与拉格朗日定理
定理对称性的数学
群 (G, ∗)：封闭、结合、有幺元、每个元素可逆。性质：消去律成立；方程 ax = b 有唯一解 x = a⁻¹b。
阿贝尔群：再满足交换律。
子群判定：非空 H ⊆ G 是子群 ⇔ ∀a,b∈H, ab⁻¹ ∈ H。
循环群：由单个元素 g 的幂生成。Zₙ = ⟨1⟩；其生成元恰为与 n 互素的元素（共 φ(n) 个）。
拉格朗日定理：子群的阶整除群的阶（|H| | |G|）——由此：元素的阶整除群阶；素数阶群必循环且无真子群。
阿贝尔群：再满足交换律。
子群判定：非空 H ⊆ G 是子群 ⇔ ∀a,b∈H, ab⁻¹ ∈ H。
循环群：由单个元素 g 的幂生成。Zₙ = ⟨1⟩；其生成元恰为与 n 互素的元素（共 φ(n) 个）。
拉格朗日定理：子群的阶整除群的阶（|H| | |G|）——由此：元素的阶整除群阶；素数阶群必循环且无真子群。
随堂检测群论
3 环与域
概念两种运算的和谐共处
环 (R, +, ×)：(R,+) 是阿贝尔群，× 结合、对 + 分配。含幺交换环再要求 × 交换、有幺元。
域：非零元对 × 也构成阿贝尔群（都能做除法）。
关键事实：Zₙ 是域 ⇔ n 是素数；Zₙ 有零因子 ⇔ n 是合数（如 Z₆：2×3=0）。Q、R、C 是域，Z 只是环。
应用：Z_p 域上的多项式运算 = CRC 校验、AES 的 GF(2⁸)。
域：非零元对 × 也构成阿贝尔群（都能做除法）。
关键事实：Zₙ 是域 ⇔ n 是素数；Zₙ 有零因子 ⇔ n 是合数（如 Z₆：2×3=0）。Q、R、C 是域，Z 只是环。
应用：Z_p 域上的多项式运算 = CRC 校验、AES 的 GF(2⁸)。
4 同态与同构
概念保持结构的映射
同态 φ(a∗b) = φ(a)∘φ(b)；双射同态 = 同构（"名字不同、结构相同"）。
核 ker φ = {a | φ(a) = e′} 是子群；同态基本定理 G/kerφ ≅ imφ。
例：log 把 (R₊, ×) 同构到 (R, +)——"乘法变加法"正是计算尺的原理；Z₆ ≅ Z₂×Z₃（中国剩余定理）。
核 ker φ = {a | φ(a) = e′} 是子群；同态基本定理 G/kerφ ≅ imφ。
例：log 把 (R₊, ×) 同构到 (R, +)——"乘法变加法"正是计算尺的原理；Z₆ ≅ Z₂×Z₃（中国剩余定理）。
5 图的基本概念
概念握手定理与特殊图
握手定理：Σ deg(v) = 2|E|——总度数必为偶数，奇度顶点个数必为偶数。
完全图 Kₙ：任意两点相邻，|E| = n(n−1)/2；二部图 ⇔ 无奇圈。
同构：存在保持相邻关系的双射；必要条件：度序列相同（反之不然）。
完全图 Kₙ：任意两点相邻，|E| = n(n−1)/2；二部图 ⇔ 无奇圈。
同构：存在保持相邻关系的双射；必要条件：度序列相同（反之不然）。
6 连通、欧拉图与哈密顿图
定理一笔画与环球旅行
欧拉回路（每条边恰一次回到起点）⇔ 连通且所有顶点度数为偶；
欧拉通路（不回到起点）⇔ 连通且恰有 0 或 2 个奇度顶点（起终点是奇度点）。——七桥问题的解答。
哈密顿回路（每个顶点恰一次）：无简单充要条件；充分条件：Dirac——n≥3 简单图若每点 deg ≥ n/2 则哈密顿。判定问题是 NP 完全的。
欧拉通路（不回到起点）⇔ 连通且恰有 0 或 2 个奇度顶点（起终点是奇度点）。——七桥问题的解答。
哈密顿回路（每个顶点恰一次）：无简单充要条件；充分条件：Dirac——n≥3 简单图若每点 deg ≥ n/2 则哈密顿。判定问题是 NP 完全的。
随堂检测图论
7 树与生成树
概念最瘦的连通图
树：连通无回路。六条等价刻画：连通无圈 ⇔ 连通且 e = n−1 ⇔ 无圈且 e = n−1 ⇔ 任意两点恰一条路径 ⇔ 无圈但加任一新边得唯一圈 ⇔ 连通但删任一边不连通。
生成树：连通图的极小连通生成子图（Kruskal 求最小生成树）；根树：表达式树、哈夫曼编码、并查集。
n 个顶点的无标号树计数无简单公式；标号树有 Cayley 公式 nⁿ⁻²。
生成树：连通图的极小连通生成子图（Kruskal 求最小生成树）；根树：表达式树、哈夫曼编码、并查集。
n 个顶点的无标号树计数无简单公式；标号树有 Cayley 公式 nⁿ⁻²。