离散数学
发布于 2025-12-14
·
离散数学复习全书 (完整版)
教材版本 ：离散数学 (第3版) - 西安交通大学出版社 (陈建明 曾明 刘国荣 编)适用范围 ：期末复习 / 考研备考内容涵盖 ：集合论、关系、函数、代数系统、图论
目录
第3章 集合
复习重点 ：集合的定义与表示、幂集、基本运算定律、宏运算（对称差与环积） 、集合恒等式的证明方法（特别是成员表法）。
3.1 集合的基本概念
1. 集合的定义与特性
概念 ：集合是由总括某些个体成一个整体而产生的，其中的个体称为元素 （成员）。关系 ：
属于 ($a \in A$) ：个体 $a$ 是集合 $A$ 的成员。不属于 ($a \notin A$) ：个体 $a$ 不是集合 $A$ 的成员。特性 ：集合中的元素必须是可辨认的 （互异性），且属于关系是无二义性的。
2. 集合的表示法
文字表示法 ：用自然语言描述，如 {教室里在座的同学}。列举法 ：列出所有元素，如 {1, 2, 3}。谓词表示法 ：${x \mid P(x)}$，其中 $P(x)$ 是元素 $x$ 具有的属性，如 ${x \mid x^2 - 4x + 3 = 0}$。
3. 特殊集合
空集 ($\emptyset$) ：不含任何元素的集合。全集 ($X$ 或 $E$) ：研究范围内全部个体组成的集合。
4. 集合间的关系
子集 ($\subseteq$) ：若 $\forall x (x \in A \rightarrow x \in B)$，则 $A \subseteq B$。
性质：$\emptyset \subseteq A$，$A \subseteq A$。
相等 ($=$) ：$A = B$ 当且仅当 $A \subseteq B$ 且 $B \subseteq A$。
5. 幂集 (Power Set)
定义 ：集合 $A$ 的所有子集组成的集合，记为 $2^A$。
公式：$2^A = {x \mid x \subseteq A}$。
性质 ：
若 $\vert A\vert = n$，则 $\vert2^A\vert = 2^n$。
$2^\emptyset = {\emptyset}$。
$A = B \iff 2^A = 2^B$。
3.2 集合的基本运算
1. 补运算 (Complement)
定义 ：$A’ = {x \mid x \in X \land x \notin A}$ （相对于全集 $X$）。性质 ：
$(A’)’ = A$ （双重否定）。
$X’ = \emptyset, \emptyset’ = X$。
2. 并运算与交运算
并集 ($\cup$) ：$A \cup B = {x \mid x \in A \lor x \in B}$。交集 ($\cap$) ：$A \cap B = {x \mid x \in A \land x \in B}$。
3. 运算定律 (重要)
常用的集合恒等式包括：
幂等律 ：$A \cup A = A, A \cap A = A$。交换律 ：$A \cup B = B \cup A, A \cap B = B \cap A$。结合律 ：$(A \cup B) \cup C = A \cup (B \cup C)$。分配律 ：
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$。
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$。
De Morgan 律 (德摩根律) ：
$(A \cup B)’ = A’ \cap B’$。
$(A \cap B)’ = A’ \cup B’$。
4. 包含关系的等价形式 (定理 3.7)
以下三个命题等价：
$A \subseteq B$
$A \cup B = B$
$A \cap B = A$
3.3 集合的宏运算
这些运算是由基本运算（并、交、补）组合而成的。
1. 差运算 (Difference)
定义 ：$A \setminus B = {x \mid x \in A \land x \notin B}$。等价形式 ：$A \setminus B = A \cap B’$。性质 ：$A \setminus B \subseteq A$；$A \setminus A = \emptyset$；$A \setminus \emptyset = A$。
2. 环和运算 / 对称差 (Symmetric Difference)
定义 ：$A \oplus B = {x \mid (x \in A \land x \notin B) \lor (x \in B \land x \notin A)}$。等价形式 ：
$A \oplus B = (A \setminus B) \cup (B \setminus A)$
$A \oplus B = (A \cup B) \setminus (A \cap B)$
性质 ：满足交换律和结合律；$A \oplus A = \emptyset$；$A \oplus \emptyset = A$。
3. 环积运算 (Ring Product)
定义 ：$A \otimes B = {x \mid (x \in A \lor x \notin B) \land (x \in B \lor x \notin A)}$。等价形式 ：$A \otimes B = (A \cup B’) \cap (B \cup A’)$。关系 ：$A \otimes B = (A \oplus B)’$，即环积是环和的补集。
4. 大并与大交
用于处理集族（集合的集合）的运算。
大并 ($\bigcup$) ：$\bigcup_{y \in \Gamma} A_y = {x \mid \exists \gamma \in \Gamma (x \in A_\gamma)}$。大交 ($\bigcap$) ：$\bigcap_{y \in \Gamma} A_y = {x \mid \forall \gamma \in \Gamma (x \in A_\gamma)}$。广义 De Morgan 律 ：$(\bigcup A_y)’ = \bigcap (A_y’)$；$(\bigcap A_y)’ = \bigcup (A_y’)$。
3.4 集合运算的其他表示法
1. 文氏图 (Venn Diagram)
用平面上的封闭曲线（如圆）表示集合，用矩形表示全集。适合直观展示集合关系，但不适合作为严格证明工具。
2. 成员表法 (Membership Table)
原理 ：将全集中的个体分为两类（属于集合记为1，不属于记为0）。列出所有可能的所属状态组合，类似于真值表。用途 ：证明集合恒等式 。如果两个集合表达式的成员表结果列完全相同，则这两个集合相等。示例 ：证明 $(A \cup B)’ = A’ \cap B’$
A
B
A $\cup$ B
(A $\cup$ B)’
A’
B’
A’ $\cap$ B’
0
0
0
1 1
1
1
0
1
1
0 1
0
0
1
0
1
0 0
1
0
1
1
1
0 0
0
0
(注：两列粗体部分相同，故等式成立)
3.5 习题与考点提示
区分 $\in$ 和 $\subseteq$ ：$\emptyset \in {\emptyset}$ 是真的，但 $\emptyset \subseteq {\emptyset}$ 也是真的。要特别注意空集和幂集的元素关系。幂集元素个数 ：若 $A={1, 2}$，则 $2^A = {\emptyset, {1}, {2}, {1, 2}}$，共 $2^2=4$ 个元素。证明题技巧 ：
证明 $A = B$：分别证明 $A \subseteq B$ 和 $B \subseteq A$。
证明 $A \subseteq B$：任取 $x \in A$，推导出 $x \in B$。
使用成员表法或集合演算法（利用已知定律变换）来证明复杂的集合恒等式。
第4章 关系
复习重点 ：关系的本质（集合）、五大基本性质的判定（矩阵/图法）、闭包运算、等价关系与划分的对应、偏序集中的特殊元素判定。
4.1 集合的叉积 (Cartesian Product)
1. 基本定义
有序对 ：由两个元素 $a, b$ 按特定顺序组成的序列 $(a, b)$。特点是当 $a \neq b$ 时，$(a, b) \neq (b, a)$。叉积 (笛卡儿积) ：
\(A \times B = \{(a, b) \mid a \in A \land b \in B\}\)
基数 ：$\vert A \times B\vert = \vert A\vert \times \vert B\vert$。推广 ：$A_1 \times A_2 \times \dots \times A_n$ 是 $n$ 元组的集合。
2. 运算性质 (常考点)
不满足交换律 ：$A \times B \neq B \times A$ (除非 $A=B$ 或其中之一为空)。不满足结合律 ：$(A \times B) \times C \neq A \times (B \times C)$。对集合运算的分配律 [习题 4-1]：
$A \times (B \cup C) = (A \times B) \cup (A \times C)$
$A \times (B \cap C) = (A \times B) \cap (A \times C)$
$A \times (B \setminus C) = (A \times B) \setminus (A \times C)$
(注意) ：$(A \cup B) \times (C \cup D) \neq (A \times C) \cup (B \times D)$，通常前者包含后者。
4.2 关系的基本概念
1. 定义与术语
二元关系 ：$A$ 到 $B$ 的二元关系 $R$ 是 $A \times B$ 的子集。A上的关系 ：$R \subseteq A \times A$。三大域 ：
定义域 (Domain) ：$\mathcal{D}(R) = {x \mid \exists y, xRy}$ (出发点集合)值域 (Range) ：$\mathcal{R}(R) = {y \mid \exists x, xRy}$ (终点集合)域 (Field) ：$\mathcal{F}(R) = \mathcal{D}(R) \cup \mathcal{R}(R)$
2. 关系的表示
关系矩阵 $M_R$：
元素 $m_{ij}=1 \iff (a_i, a_j) \in R$。
关系图 $G_R$：
4.3 关系的运算
1. 逆运算 ($R^{-1}$)
定义 ：$R^{-1} = {(y, x) \mid (x, y) \in R}$。性质 ：
$(R^{-1})^{-1} = R$
$\mathcal{D}(R^{-1}) = \mathcal{R}(R), \mathcal{R}(R^{-1}) = \mathcal{D}(R)$
$(R \cup S)^{-1} = R^{-1} \cup S^{-1}$ [习题 4-13]
$(R \cap S)^{-1} = R^{-1} \cap S^{-1}$
2. 复合运算 ($R \circ S$)
定义 ：设 $R \subseteq A \times B, S \subseteq B \times C$。
\(R \circ S = \{(x, z) \mid \exists y \in B, (x, y) \in R \land (y, z) \in S\}\)
(注意：本教材符号顺序为先R后S，有些教材写作 S $\circ$ R，需区分) 性质 ：
结合律 ：$(R \circ S) \circ T = R \circ (S \circ T)$逆序律 ：$(R \circ S)^{-1} = S^{-1} \circ R^{-1}$ [习题 4-13]对并运算分配 ：$R \circ (S \cup T) = (R \circ S) \cup (R \circ T)$
矩阵运算 ：$M_{R \circ S} = M_R \cdot M_S$ (布尔乘法)。
3. 幂运算 ($R^n$)
$R^0 = I_A$ (恒等关系)
$R^{n+1} = R^n \circ R$
定理 ：若 $A$ 为有限集，则存在 $k, s$ 使得 $R^k = R^{k+s}$ (幂序列最终会出现循环)。
4.4 关系的性质 (核心考点)
设 $R$ 是集合 $A$ 上的关系：
性质
定义 ($\forall x, y, z \in A$)
矩阵特征 $M_R$
图特征 $G_R$
集合特征
自反性 $xRx$
主对角线全1
每个点有自环
$I_A \subseteq R$
反自反性 $\neg(xRx)$
主对角线全0
无自环
$R \cap I_A = \emptyset$
对称性 $xRy \to yRx$
对称矩阵 ($M=M^T$)
边成对出现或无向
$R = R^{-1}$
反对称性 $xRy \land yRx \to x=y$
$m_{ij}=1 \land i \neq j \Rightarrow m_{ji}=0$
无双向边
$R \cap R^{-1} \subseteq I_A$
传递性 $xRy \land yRz \to xRz$
$M^2 \le M$ (布尔)
若有路必有直达边
$R \circ R \subseteq R$
★ 习题中的重要推论 (性质的保持)
运算后的性质保持 [习题 4-17]：
若 $R_1, R_2$ 自反 ，则 $R_1 \cup R_2, R_1 \cap R_2, R_1 \circ R_2, R_1^{-1}$ 均自反。
若 $R_1, R_2$ 对称 ，则 $R_1 \cup R_2, R_1 \cap R_2, R_1^{-1}$ 对称；但 $R_1 \circ R_2$ 不一定 对称 (除非 $R_1 \circ R_2 = R_2 \circ R_1$)。
若 $R_1, R_2$ 传递 ，则 $R_1 \cap R_2, R_1^{-1}$ 传递；但 $R_1 \cup R_2$ 不一定 传递。
特殊判定 ：
若 $R$ 对称且反对称，则 $R$ 只能包含对角线元素 (即 $R \subseteq I_A$)。
全关系 $E_A$ 是自反、对称、传递的。
空关系 $\emptyset$ 是反自反、对称、反对称、传递的。
4.5 闭包运算 (Closure)
定义 ：包含 $R$ 且具有性质 $P$ 的最小关系。计算公式 ：
自反闭包 $r(R) = R \cup I_A$对称闭包 $s(R) = R \cup R^{-1}$传递闭包 $t(R)$ (或 $R^+$) $= \bigcup_{i=1}^{\vert A\vert} R^i$
性质 [习题 4-18]：
若 $R$ 自反，则 $s(R)$ 和 $t(R)$ 也自反。
若 $R$ 对称，则 $r(R)$ 和 $t(R)$ 也对称。
$(R^+)^+ = R^+$ (闭包的闭包等于自身)。
4.6 等价关系与划分
1. 核心概念
等价关系 ：自反 + 对称 + 传递。 (记为 $\sim$)等价类 ：$[x]_R = {y \mid y \in A \land xRy}$。商集 ：$A/R = {[x]_R \mid x \in A}$。
2. 划分定理
定理 ：集合 $A$ 上的等价关系 与 $A$ 的划分 一一对应。
由关系求划分 ：商集即为划分。由划分求关系 ：$R = {(x, y) \mid x, y \text{ 在划分的同一个块中}}$。关系图特征 ：等价关系的关系图由若干个互不相连的完全图 （团）组成（每个团对应一个等价类）。
4.7 半序关系 (Partial Order)
1. 核心概念
偏序关系 ：自反 + 反对称 + 传递。 (记为 $\preceq$)
例：$\le$ (小于等于)，$\subseteq$ (包含)，$\vert$ (整除)
覆盖 (Covering) ：若 $x \prec y$ 且中间没有其他元素，称 $y$ 覆盖 $x$。哈斯图 (Hasse Diagram) ：简化图，仅画覆盖关系，方向向上。
2. 特殊元素 (极值与界)
设 $B$ 是偏序集 $A$ 的子集：
极大元 ：$B$ 中没有比它大的。 (可以有多个，可以没有)最大元 ：$B$ 中所有元素都 $\preceq$ 它。 (唯一，若存在必是极大元)上界 ：$A$ 中比 $B$ 所有元素都大的元素。上确界 (LUB) ：最小的上界。 (唯一)(极小元、最小元、下界、下确界同理)
3. 格 (Lattice)
定义 ：偏序集中任意两个元素 $x, y$ 都有上确界 ($x \lor y$) 和下确界 ($x \land y$)。全序集 (线序) ：任意两元素都可比的偏序集。全序集一定是格。
★ 习题中的重要结论
有限偏序集 必有极大元和极小元 [习题 4-36]。整除关系 ：在正整数集上的整除关系 $D_n$ 构成格。
$x \land y = \text{gcd}(x, y)$ (最大公约数)
$x \lor y = \text{lcm}(x, y)$ (最小公倍数)
第5章 函数
复习重点 ：函数的定义与分类（单/满/双射）、复合函数与逆函数的性质、集合基数的比较与计算、可数集与不可数集的判定。
5.1 函数的基本概念
1. 函数的定义
定义 ：设 $X, Y$ 是非空集合，$f$ 是从 $X$ 到 $Y$ 的二元关系。若 $\forall x \in X$，存在唯一 的 $y \in Y$ 使得 $(x, y) \in f$，则称 $f$ 为从 $X$ 到 $Y$ 的函数 (或映射)，记为 $f: X \to Y$。
定义域 (Domain) ：$\mathcal{D}(f) = X$ (必须全域定义)。值域 (Range) ：$\mathcal{R}(f) = {y \mid \exists x \in X, f(x) = y} \subseteq Y$。
函数相等 ：$f = g \iff \mathcal{D}(f) = \mathcal{D}(g) \land \forall x \in \mathcal{D}(f), f(x) = g(x)$ (即作为关系集合相等)。
2. 函数集合 $Y^X$
定义 ：$Y^X = {f \mid f: X \to Y}$，即所有从 $X$ 到 $Y$ 的函数组成的集合。基数 ：若 $\vert X\vert = m, \vert Y\vert = n$，则 $\vert Y^X\vert = n^m$。
3. 特殊函数
特征函数 $\chi_A$：设 $A \subseteq X$，$\chi_A: X \to {0, 1}$，
\(\chi_A(x) = \begin{cases} 1, & x \in A \\ 0, & x \notin A \end{cases}\)
性质 ：$\chi_{A \cap B} = \chi_A \cdot \chi_B$；$\chi_{A \cup B} = \chi_A + \chi_B - \chi_A \cdot \chi_B$；$\chi_{A’} = 1 - \chi_A$。
5.2 函数的性质 (核心考点)
1. 三类重要函数
设 $f: X \to Y$：
满射 (Surjection) ：$\mathcal{R}(f) = Y$。
即 $\forall y \in Y, \exists x \in X, f(x) = y$。
单射 (Injection) ：$\forall x_1, x_2 \in X, x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$。
等价命题：$f(x_1) = f(x_2) \Rightarrow x_1 = x_2$。
双射 (Bijection) ：既是单射又是满射。
2. 复合函数
定义 ：设 $f: X \to Y, g: Y \to Z$，则 $g \circ f: X \to Z$ 定义为 $(g \circ f)(x) = g(f(x))$。
(注意：本书记号 $g \circ f$ 表示先 $f$ 后 $g$，有些教材顺序相反，需留意) 。
性质 ：
结合律 ：$(h \circ g) \circ f = h \circ (g \circ f)$。不满足交换律 。
复合后的性质保持 [定理 5.4]：
两个满射的复合是满射。
两个单射的复合是单射。
两个双射的复合是双射。
3. 逆函数
定义 ：若 $f: X \to Y$ 是双射，则 $f^{-1}: Y \to X$ 存在且也是双射，满足 $f^{-1}(y) = x \iff f(x) = y$。性质 ：
$(f^{-1})^{-1} = f$。
$(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ (穿脱原理)。
5.3 集合的基数 (Cardinality)
1. 等势与基数
等势 ($A \approx B$) ：若存在双射 $f: A \to B$，则称 $A$ 与 $B$ 等势（基数相等），记为 $\vert A\vert = \vert B\vert$。康托尔定理 [定理 5.13]：$\vert A\vert < \vert2^A\vert$。即集合的幂集的基数总是严格大于原集合的基数。
2. 可数集 (Countable Set)
定义 ：凡是与自然数集 $\mathbb{N}$ 等势的集合称为可数集 (或可列集)，基数记为 $\aleph_0$ (阿列夫零)。性质 ：
任何无限集必包含一个可数子集。
可数集的子集是有限集或可数集。
可数集的并 ：两个 (或有限个、可数个) 可数集的并集仍是可数集。可数集的积 ：有限个可数集的笛卡儿积仍是可数集 (如 $\mathbb{Q}$ 是可数的)。例子 ：$\mathbb{Z}, \mathbb{Q}, \mathbb{N} \times \mathbb{N}$ 都是可数集。
3. 不可数集
实数集 $\mathbb{R}$ ：基数记为 $\aleph$ (或 $\mathfrak{c}$，连续统势)。
证明方法：康托尔对角线法。
常见的不可数集：$(0, 1)$ 区间、$\mathbb{R}$、复数集 $\mathbb{C}$、无理数集、$\mathbb{N}$ 的幂集 $2^\mathbb{N}$。
关系 ：$\aleph_0 < \aleph = 2^{\aleph_0}$。
4. 基数的比较
$\vert A\vert \le \vert B\vert$ ：存在单射 $f: A \to B$。C-S-B 定理 (康托尔-施罗德-伯恩斯坦定理) ：若 $\vert A\vert \le \vert B\vert$ 且 $\vert B\vert \le \vert A\vert$，则 $\vert A\vert = \vert B\vert$。
这是一个证明两个集合等势的强大工具，无需直接构造双射，只需构造两个方向的单射。
5.4 & 5.5 原始递归函数与可计算函数 (了解)
原始递归函数 ：由初始函数（零函数、后继函数、投影函数）经过有限次复合和递归运算得到的函数。Ackermann 函数 ：一个著名的非原始递归 但可计算 的函数（增长速度极快）。
6. 🎯 习题中的重要结论 (解题技巧)
以下结论来自课后习题 (P157-159)，在证明题和判断题中经常使用：
1. 象的集合运算性质 [习题 5-7]
设 $f: X \to Y$ 是函数，$A, B \subseteq X$：
并集保持 ：$f(A \cup B) = f(A) \cup f(B)$。交集包含 ：$f(A \cap B) \subseteq f(A) \cap f(B)$。
差集包含 ：$f(A) \setminus f(B) \subseteq f(A \setminus B)$。
2. 复合函数的性质推导 [习题 5-9]
设 $f: A \to B, g: B \to C$，对于复合函数 $g \circ f$：
若 $g \circ f$ 是满射 $\Rightarrow$ $g$ 必须是满射 (外层满)。
若 $g \circ f$ 是单射 $\Rightarrow$ $f$ 必须是单射 (内层单)。
若 $g \circ f$ 是双射 $\Rightarrow$ $f$ 单且 $g$ 满。
3. 单射/满射的充要条件 (右逆与左逆) [习题 5-4, 5-6]
$f: A \to B$ 是单射 $\iff$ 存在 $g: B \to A$ 使得 $g \circ f = I_A$ (存在左逆)。
$f: A \to B$ 是满射 $\iff$ 存在 $g: B \to A$ 使得 $f \circ g = I_B$ (存在右逆)。
4. 鸽巢原理 (Pigeonhole Principle)
虽然本章习题未大量展开，但它是函数部分常考点：
若 $\vert X\vert > \vert Y\vert$，则不存在从 $X$ 到 $Y$ 的单射 (必有冲突)。
若 $\vert X\vert < \vert Y\vert$，则不存在从 $X$ 到 $Y$ 的满射。
5. 关于基数的判断 [习题 5-15, 17]
代数数 是可数的。超越数 是不可数的。所有从 $\mathbb{N}$ 到 $\mathbb{N}$ 的函数构成的集合 ($\mathbb{N}^\mathbb{N}$) 是不可数的 (基数为 $2^{\aleph_0}$)。
所有从 $\mathbb{N}$ 到 ${0, 1}$ 的函数构成的集合 (${0, 1}^\mathbb{N}$) 与 $2^\mathbb{N}$ 等势，是不可数的。
第6章 代数系统
复习重点 ：二元运算及其性质（结合/交换/分配）、特殊元素（幺元/零元/逆元）、半群与独异点、群的定义与性质 、子群判定 、拉格朗日定理 、正规子群与商群、环与域的包含关系。
6.1 代数系统的基本概念
1. 运算 (Operation)
$n$ 元运算 ：设 $A$ 是非空集合，从 $A^n$ 到 $A$ 的函数 $f: A^n \to A$ 称为 $A$ 上的 $n$ 元运算。
封闭性 ：运算的结果必须仍在集合 $A$ 中。二元运算 ：$f: A \times A \to A$，通常记为 $a * b$。
2. 运算的性质
设 $*$ 是集合 $A$ 上的二元运算：
交换律 ：$\forall x, y \in A, x * y = y * x$。结合律 ：$\forall x, y, z \in A, (x * y) * z = x * (y * z)$。分配律 ：设 $\circ$ 是另一个运算，
$*$ 对 $\circ$ 满足左分配律：$x * (y \circ z) = (x * y) \circ (x * z)$。
$*$ 对 $\circ$ 满足右分配律：$(y \circ z) * x = (y * x) \circ (z * x)$。
幂等律 ：$\forall x \in A, x * x = x$。消去律 ：
左消去：若 $x * y = x * z$，则 $y = z$。
右消去：若 $y * x = z * x$，则 $y = z$。
3. 特殊元素 (重要)
幺元 (单位元) $e$ ：$\forall x \in A, e * x = x * e = x$。
零元 $ \theta $ ：$\forall x \in A, \theta * x = x * \theta = \theta$。
逆元 $x^{-1}$ ：对于 $x \in A$，若存在 $y \in A$ 使得 $x * y = y * x = e$，则称 $y$ 为 $x$ 的逆元。
性质 ：若运算满足结合律 ，则元素的逆元若存在，必唯一 。$(x^{-1})^{-1} = x$；$(x * y)^{-1} = y^{-1} * x^{-1}$ (注意顺序颠倒)。
6.2 代数系统的同构与同态
1. 定义
设 $V_1 = \langle A, * \rangle, V_2 = \langle B, \circ \rangle$ 是同类型的代数系统。$f: A \to B$ 是函数。
同态 (Homomorphism) ：若 $\forall x, y \in A$，有 $f(x * y) = f(x) \circ f(y)$，则称 $f$ 是同态映射。
单同态 ：$f$ 是单射。满同态 ：$f$ 是满射。
同构 (Isomorphism) ：若 $f$ 是双射 且是同态 ，则称 $V_1$ 与 $V_2$ 同构，记为 $V_1 \cong V_2$。
2. 性质
同态映射保持运算性质（如结合律、交换律、幺元、逆元等）不变。
若 $e_A$ 是 $A$ 的幺元，则 $f(e_A)$ 是 $f(A)$ 的幺元。
$f(x^{-1}) = (f(x))^{-1}$。
6.3 半群 (Semigroup)与独异点 (Monoid)
1. 半群
定义 ：代数系统 $\langle S, * \rangle$，若 $*$ 满足结合律 ，则称 $S$ 为半群。性质 ：半群中做运算不需要加括号（$a_1 * a_2 * \dots * a_n$ 唯一确定）。子半群 ：$T \subseteq S$，且 $T$ 对 $*$ 封闭。
2. 独异点 (幺半群)
定义 ：含有幺元 的半群 $\langle M, *, e \rangle$。子独异点 ：$T \subseteq M$，T封闭，且 $e \in T$ (幺元必须在子集中)。
6.4 群 (Group) —— 核心章节
1. 群的定义
代数系统 $\langle G, * \rangle$ 是群，需满足三个条件：
结合律 ：运算满足结合律。有幺元 ：存在 $e \in G$。有逆元 ：$\forall a \in G$，存在 $a^{-1} \in G$。
(注：群 = 独异点 + 每个元素可逆)
阿贝尔群 (交换群) ：满足交换律的群。有限群与阶 ：集合 $G$ 的元素个数 $\vert G\vert$ 称为群的阶。
2. 群的性质
群中无零元（除非 $\vert G\vert=1$）。
群满足消去律 （左消去和右消去均成立）。
方程 $a * x = b$ 和 $y * a = b$ 在群中有唯一解。
元素的阶 ：使 $a^k = e$ 的最小正整数 $k$，记为 $\vert a\vert$。若不存在，则阶为无限。
3. 子群 (Subgroup)
设 $H$ 是群 $G$ 的非空子集，若 $H$ 关于 $G$ 的运算也构成群，则称 $H$ 为 $G$ 的子群，记为 $H \le G$。
平凡子群 ：${e}$ 和 $G$ 本身。判定定理 (重要) ：
两步判定法 ：$H \le G \iff (a, b \in H \Rightarrow ab \in H) \land (a \in H \Rightarrow a^{-1} \in H)$。一步判定法 ：$H \le G \iff \forall a, b \in H, a * b^{-1} \in H$。有限子群判定 ：若 $G$ 是群，$H \subseteq G$ 且 $H$ 有限 非空，只要 $H$ 对运算封闭 ，则 $H \le G$。
4. 循环群 (Cyclic Group)
定义 ：若群 $G$ 中存在元素 $g$，使得 $G$ 中任一元素都可表示为 $g$ 的幂 ($G = {g^n \mid n \in \mathbb{Z}}$)，则称 $G$ 为循环群，$g$ 为生成元，记为 $G = \langle g \rangle$。性质 ：
循环群一定是阿贝尔群。
子群也是循环群。
若 $\vert G\vert=n$，则 $G \cong \langle \mathbb{Z}_n, +_n \rangle$ (模 $n$ 剩余类加法群)。
若 $G$ 无限，则 $G \cong \langle \mathbb{Z}, + \rangle$ (整数加法群)。
5. 陪集与拉格朗日定理 (Lagrange’s Theorem)
陪集 ：设 $H \le G$，对于 $a \in G$：
左陪集 $aH = {ah \mid h \in H}$。
右陪集 $Ha = {ha \mid h \in H}$。
性质 ：陪集构成了 $G$ 的一个划分；任意两个陪集要么相等，要么不相交；$\vert aH\vert = \vert H\vert$。
拉格朗日定理 (必考) ：设 $G$ 是有限群，$H$ 是 $G$ 的子群，则：
\(\vert G\vert = \vert H\vert \cdot [G:H]\)
结论 ：子群的阶 $\vert H\vert$ 整除群的阶 $\vert G\vert$ 。推论 ：
群中任意元素的阶整除群的阶。
素数阶的群一定是循环群。
6. 正规子群与商群
正规子群 ：若 $\forall g \in G, gH = Hg$ (左陪集等于右陪集)，则称 $H$ 为正规子群，记为 $H \trianglelefteq G$。
商群 ：所有陪集构成的集合 $G/H = {aH \mid a \in G}$，在定义运算 $(aH)*(bH) = (ab)H$ 下构成的群。商群的阶 $\vert G/H\vert = \vert G\vert / \vert H\vert$。
6.5 & 6.6 环 (Ring) 与 域 (Field)
1. 环的定义
代数系统 $\langle R, +, \cdot \rangle$ 满足：
$\langle R, + \rangle$ 是阿贝尔群 。
$\langle R, \cdot \rangle$ 是半群 。
$\cdot$ 对 $+$ 满足分配律 。
2. 特殊的环
交换环 ：乘法满足交换律。含幺环 ：乘法有单位元。无零因子环 ：若 $a \cdot b = 0 \Rightarrow a=0 \lor b=0$。整环 (Integral Domain) ：交换、含幺、无零因子的环。(例如：整数环 $\mathbb{Z}$)
3. 域
定义 ：$\langle F, +, \cdot \rangle$ 是域，若：
$\langle F, +, \cdot \rangle$ 是含幺交换环。
$\langle F^, \cdot \rangle$ 是阿贝尔群 ($F^ = F \setminus {0}$，即非零元素对乘法构成群)。
关系链 ：
\(域 \subset 除环 \subset 整环 \subset 交换环 \subset 环\)
(注：有限整环一定是域)
🎯 习题中的重要结论 (补充考点)
以下结论整理自第6章课后习题 (P212-219)，常用于证明题或填空题：
1. 半群与群的判定
有限半群判定群 [习题 6-12]：若有限半群 $\langle S, * \rangle$ 满足消去律 ，则它是一个群。方程解判定 [习题 6-13]：若半群 $S$ 中，方程 $ax=b$ 和 $ya=b$ 对任意 $a,b$ 都有解，则 $S$ 是群。
2. 元素的阶与运算
逆元的阶 [习题 6-17]：$\vert a\vert = \vert a^{-1}\vert$。共轭元的阶 [习题 6-17]：$\vert a\vert = \vert b^{-1}ab\vert$。交换群中的阶 ：若 $G$ 是阿贝尔群，则 $\vert ab\vert$ 整除 $\text{lcm}(\vert a\vert, \vert b\vert)$。偶数阶群 [习题 6-25]：偶数阶群中必存在阶为 2 的元素 (即 $x \neq e$ 且 $x = x^{-1}$)。
3. 子群的相关性质
子群的交 [习题 6-22]：任意两个子群的交 $H \cap K$ 仍是子群。子群的并 ：$H \cup K$ 一般不是子群，除非 $H \subseteq K$ 或 $K \subseteq H$。子群的积 ：设 $HK = {hk \mid h \in H, k \in K}$。若 $G$ 是阿贝尔群，则 $HK$ 是子群。
4. 正规子群与中心
中心 (Center) [习题 6-27]：$C = {x \in G \mid \forall g \in G, xg=gx}$ (与所有元素交换的元素集合)。
指数为2的子群 [习题 6-30]：若子群 $H$ 的指数 $[G:H] = 2$ (即只有两个左陪集)，则 $H$ 必为正规子群。
5. 环的性质
布尔环 [习题 6-40]：若环 $R$ 满足 $\forall x \in R, x^2 = x$ (幂等律)，则 $R$ 是交换环，且 $\forall x, x+x=0$ (特征为2)。
第8章 图论
复习重点 ：图的基本概念（度、握手定理）、图的连通性、矩阵表示、欧拉图与哈密顿图的判定、平面图的欧拉公式、树的性质与生成树。
8.1 & 8.2 图的基本概念
1. 图的定义
图 (Graph) ：$G = \langle V, E \rangle$，其中 $V$ 是非空顶点集，$E$ 是边集。
有向图 ：边是有序对 $\langle u, v \rangle$（弧）。无向图 ：边是无序对 $(u, v)$。
相关术语 ：
阶 ：顶点数 $\vert V\vert$。零图 ：$E = \emptyset$ 的图。平凡图 ：1阶零图。多重图 ：含有平行边（多重边）的图。伪图 ：含有自环的图。简单图 ：既无自环也无平行边的图。
2. 顶点的度 (Degree)
无向图 ：
度 $d(v)$ ：与顶点 $v$ 关联的边的数目（自环算2度）。奇/偶点 ：度数为奇数/偶数的顶点。最大/最小度 ：$\Delta(G)$ 和 $\delta(G)$。
有向图 ：
入度 $d^-(v)$ ：以 $v$ 为终点的边数。出度 $d^+(v)$ ：以 $v$ 为起点的边数。度 ：$d(v) = d^+(v) + d^-(v)$。
3. 握手定理 (核心考点)
定理 ：在任何图中，所有顶点的度数之和等于边数的2倍。
\(\sum_{v \in V} d(v) = 2\vert E\vert\)推论 ：任何图中，奇度顶点的个数必为偶数 。有向图握手定理 ：
\(\sum d^+(v) = \sum d^-(v) = \vert E\vert\)
4. 特殊图类
完全图 $K_n$ ：任意两个不同顶点间都有边的简单无向图。
边数 $\vert E\vert = n(n-1)/2$，度数均为 $n-1$。
圈图 $C_n$ ：$n$ 个顶点的环，$d(v)=2$。轮图 $W_n$ ：$C_n$ 中心加一个点与周围相连 ($n \ge 3$)。正则图 ：所有顶点度数相同的图（$k$-正则图）。
5. 子图与同构
子图 ：$V’ \subseteq V, E’ \subseteq E$。生成子图 ：$V’ = V$（顶点全保留，边可选）。导出子图 ：选定顶点集 $V’$，保留 $V’$ 内部所有的边。同构 (Isomorphism) ：两个图结构完全相同（仅顶点标记不同）。
必要条件 ：顶点数、边数、度数列相同。如果不满足，则不同构。
8.3 路与圈 (连通性)
1. 通路与回路
通路 (Walk) ：顶点与边的交替序列。迹 (Trail) ：边互不相同的通路。路径 (Path) ：顶点互不相同的通路（简单通路）。回路 (Cycle/Circuit) ：起点=终点的路径（简单回路）。
2. 连通性
无向图 ：
连通 ：任意两点间均有路。连通分量 ：极大连通子图。
有向图 ：
弱连通 ：略去方向后是连通的。单向连通 ：任意两点 $u, v$，或者 $u \to \dots \to v$，或者 $v \to \dots \to u$。强连通 ：任意两点间均双向可达。
3. 图的距离与直径
距离 $d(u, v)$ ：$u, v$ 间最短路径的长度。直径 ：图中任意两点距离的最大值。
4. 割点与桥
点连通度 $\kappa(G)$ ：最少删除多少个顶点使图不连通。边连通度 $\lambda(G)$ ：最少删除多少条边使图不连通。不等式关系 ：$\kappa(G) \le \lambda(G) \le \delta(G)$ (最小度)。
8.4 图的矩阵表示
1. 邻接矩阵 $A(G)$
定义 ：$n \times n$ 矩阵，$a_{ij} = 1$ 若 $v_i, v_j$ 相邻，否则为0。性质 ：无向图的邻接矩阵是对称的。定理 (重要) ：$A^k$ 中第 $i$ 行第 $j$ 列的元素 $a_{ij}^{(k)}$ 表示从 $v_i$ 到 $v_j$ 长度为 $k$ 的通路的条数。
2. 关联矩阵 $M(G)$
顶点与边的关系矩阵。无向图每列有两个1；有向图每列有一个1，一个-1（出/入）。
3. 可达性矩阵 $P$
$p_{ij}=1$ 表示 $v_i$ 可达 $v_j$。可用 Warshall 算法 计算。
8.5 带权图的最短路径
Dijkstra 算法 ：解决单源最短路径问题（边权非负）。
8.6 & 8.7 欧拉图与哈密顿图
1. 欧拉图 (Euler Graph) —— 边的问题
定义 ：
欧拉通路 ：经过图中每条边一次且仅一次的迹。欧拉回路 ：经过图中每条边一次且仅一次的闭迹。欧拉图 ：具有欧拉回路的图。
判定定理 (充要条件) ：
无向图 ：
欧拉图 $\iff$ 连通且所有顶点的度数为偶数 。
半欧拉图 (有通路无回路) $\iff$ 连通且恰有 2 个奇度顶点 。
有向图 ：
欧拉图 $\iff$ 基图连通且每个顶点 $d^+(v) = d^-(v)$。
2. 哈密顿图 (Hamilton Graph) —— 点的问题
定义 ：
哈密顿通路 ：经过图中每个顶点一次且仅一次的路。哈密顿回路 ：经过图中每个顶点一次且仅一次的回路。
判定 (充分条件) ：
Ore 定理 ：$n \ge 3$ 的简单无向图，若对于任意不相邻顶点 $u, v$，有 $d(u) + d(v) \ge n$，则 $G$ 是哈密顿图。Dirac 定理 ：$n \ge 3$ 的简单无向图，若 $\delta(G) \ge n/2$，则 $G$ 是哈密顿图。必要条件 (用于证明不是H图)：若 $G$ 是H图，则对于 $V$ 的任意非空真子集 $S$，有 $p(G-S) \le \vert S\vert$ （$p$ 为连通分量数）。
8.8 二分图 (Bipartite Graph)
1. 定义与判定
定义 ：顶点集可划分为两个互不相交的子集 $V_1, V_2$，使得每条边都连接 $V_1$ 和 $V_2$ 中的顶点。判别定理 ：一个图是二分图 $\iff$ 图中不含奇数长度的回路 (所有圈长均为偶数)。
2. 匹配
Hall 定理 (完备匹配条件) ：设二分图 $G=\langle V_1, V_2, E \rangle$，存在从 $V_1$ 到 $V_2$ 的完备匹配 $\iff$ 对 $V_1$ 的任意子集 $A$，都有 $\vert N(A)\vert \ge \vert A\vert$ (邻接点数 $\ge$ 自身点数)。
8.9 平面图 (Planar Graph)
1. 定义
2. 欧拉公式 (核心)
对于连通平面图：$n - m + r = 2$
$n$：顶点数，$m$：边数，$r$：面数 (包含外部无限面)。
推论 ：
$m \le 3n - 6$ (当 $n \ge 3$ 时)。
平面图中至少有一个度数 $\le 5$ 的顶点。
$K_5$ (5个顶点的完全图) 和 $K_{3,3}$ (3,3完全二分图) 不是 平面图。
3. 库拉图斯基定理 (充要条件)
图 $G$ 是平面图 $\iff$ $G$ 不含同胚于 $K_5$ 或 $K_{3,3}$ 的子图（即不能通过收缩边得到 $K_5$ 或 $K_{3,3}$）。
8.10 树 (Tree)
1. 定义与性质
定义 ：连通且无回路的无向图。等价定义 (设图有 $n$ 点 $m$ 边)：
无回路且 $m = n - 1$。
连通且 $m = n - 1$。
无回路，但增加任一条边即形成唯一的一个圈。
连通，但删除任一条边即不连通。
任意两点间有且仅有一条路径。
2. 生成树
定义 ：包含图中所有顶点的树（是子图）。基本回路系统 ：对应一棵生成树，加入一条弦（非树边）形成的唯一回路。最小生成树 (MST) ：
Kruskal 算法 (避圈法)：按边权从小到大选边。Prim 算法 ：从一个顶点出发，不断扩展最小边。
🎯 习题中的重要结论 (补充考点)
以下结论整理自课后习题，常用于证明或选择填空：
补图的连通性 ：
若 $G$ 是不连通图，则其补图 $\overline{G}$ 必是连通图 (且直径 $\le 2$)。
树叶的数量 ：
任何 $n \ge 2$ 的树中，至少有 2 片树叶 (度为1的顶点)。
握手定理应用 ：
设树中有 $n_k$ 个度为 $k$ 的节点，则叶子数 $n_1 = 2 + \sum_{k=3}^{\Delta} (k-2)n_k$。
简单图边数限制 ：
$n$ 个顶点的简单图，若 $m > (n-1)(n-2)/2$，则 $G$ 必连通。
二分图的边数 ：
$n$ 个顶点的简单二分图，边数最多为 $\lfloor n^2/4 \rfloor$。
正则图性质 ：
若 $G$ 是 $k$-正则二分图 ($k>0$)，则 $G$ 必存在完备匹配。
提示：鼠标移动会产生拖尾并影响周围粒子；按住 Alt 可切换吸引（Alt）/排斥（默认）效果。