handsomezhuzhu.github.io/discrete-math-notes.md at main

zzh/handsomezhuzhu.github.io

Fork 0

mirror of https://github.com/handsomezhuzhu/handsomezhuzhu.github.io.git synced 2026-02-20 20:00:14 +00:00

Files

handsomezhuzhu ce2419a33e 离散

2026-01-07 00:27:21 +08:00

31 KiB

Raw Permalink Blame History

title, date, descriptionHTML, tags, sidebar, readingTime, hidden, recommend

title

date

descriptionHTML

第一章：数理逻辑

1.1 命题逻辑

1.1.1 核心概念深度解析

命题：必须是陈述句且具有唯一真值。
- 易错点：悖论（如"我正在说谎"）不是命题；含有未定变量的句子（如"$x+1=2$"）是谓词而非命题。
原子命题与复合命题：
- 原子命题：不能再分解的命题。
- 复合命题：通过联结词组合而成。

1.1.2 联结词与真值表 (详细版)

联结词	符号	英文	优先级	逻辑详解	常见语言表达
否定	`\neg`	NOT	1	真变假，假变真	"并不是..."
合取	`\land`	AND	2	仅当两者全真时为真	"且", "虽然...但是...", "既...又..."
析取	`\lor`	OR	3	仅当两者全假时为假	"或" (包含性或)
蕴涵	`\to`	IMPLIES	4	前真后假时为假，其余全真	"若...则...", "只要...就...", "只有...才..."
双蕴涵	`\leftrightarrow`	IFF	5	同真同假时为真	"当且仅当", "充分必要条件"

重点难点：蕴涵关系 (`P \to Q`) 的翻译

充分条件："只要 P 就 $Q$" \Rightarrow P \to Q
必要条件："只有 Q 才 $P$" \Rightarrow P \to Q (注意：P 是 Q 的充分条件，或者理解为 \neg Q \to \neg P)
除非："除非 P 否则 $Q$" \Rightarrow \neg P \to Q (即 P \lor Q)

1.1.3 命题公式的分类 (Classifications)

常考题型：判断给定公式属于哪一类。

永真式 (重言式, Tautology)：
- 在所有真值赋值下，结果均为真 (1)。
- 例：P \lor \neg P
矛盾式 (永假式, Contradiction)：
- 在所有真值赋值下，结果均为假 (0)。
- 例：P \land \neg P
可满足式 (Contingency)：
- 不是矛盾式的公式（即至少有一种赋值为真）。
- 注意：永真式也是可满足式的一种，但通常指"既非永真也非永假"的公式。

1.1.4 逻辑等值式 (Laws of Logic)

核心：用于化简命题公式。

双重否定律：\neg\neg P \Leftrightarrow P
幂等律：P \lor P \Leftrightarrow P, P \land P \Leftrightarrow P
交换律：P \lor Q \Leftrightarrow Q \lor P, P \land Q \Leftrightarrow Q \land P
结合律：(P \lor Q) \lor R \Leftrightarrow P \lor (Q \lor R)
分配律 (非常重要)：
- P \lor (Q \land R) \Leftrightarrow (P \lor Q) \land (P \lor R) (析取对合取的分配)
- P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R) (合取对析取的分配)
德·摩根律 (De Morgan's Laws) (变号变词)：
- \neg(P \lor Q) \Leftrightarrow \neg P \land \neg Q
- \neg(P \land Q) \Leftrightarrow \neg P \lor \neg Q
吸收律 (合并同类项)：
- P \lor (P \land Q) \Leftrightarrow P
- P \land (P \lor Q) \Leftrightarrow P
蕴含等值式：P \to Q \Leftrightarrow \neg P \lor Q (去箭头核心公式)
等价等值式：P \leftrightarrow Q \Leftrightarrow (P \to Q) \land (Q \to P)
假言易位 (逆否命题)：P \to Q \Leftrightarrow \neg Q \to \neg P
归谬律：(P \to Q) \land (P \to \neg Q) \Leftrightarrow \neg P

1.1.4 范式 (Normal Forms)

析取范式 (DNF) 与合取范式 (CNF)

定义：
- DNF：简单合取式的析取 (\sum)。例如：(P \land Q) \lor (\neg P \land R)
- CNF：简单析取式的合取 (\prod)。例如：(P \lor Q) \land (\neg P \lor R)
主范式 (Principal NF)：
- 极小项 (m_i)：包含所有变量的合取项，编码对应真值表中的行号。
- 极大项 (M_i)：包含所有变量的析取项。
- 转换方法：
  1. 真值表法：
    - 主析取范式：取真值表中结果为 T 的行对应的极小项之和。
    - 主合取范式：取真值表中结果为 F 的行对应的极大项之积。
  2. 等值演算法：利用双重否定、德摩根、分配律展开。

1.2 谓词逻辑 (Predicate Logic)

1.2.1 基本要素

个体词：常量 (a, b) 和变量 (x, y)。
谓词：$P(x_1, \dots, x_n)$，表示个体之间的性质或关系。
量词：
- 全称量词 \forall (For all)
- 存在量词 \exists (Exists)
论域 (Universe)：个体变元的取值范围。若未指定，通常指全总个体域。

1.2.2 翻译技巧 (易错)

"所有的 S 都是 P"：
- 正确：\forall x (S(x) \to P(x))
- 错误：\forall x (S(x) \land P(x)) (这意味着宇宙中万物既是S也是P)
"有的 S 是 P"：
- 正确：\exists x (S(x) \land P(x))
- 错误：\exists x (S(x) \to P(x)) (这通常是恒真的，没有意义)

1.2.3 谓词逻辑等值式

量词否定律：
- \neg \forall x P(x) \Leftrightarrow \exists x \neg P(x) (改变量词，否定谓词)
- \neg \exists x P(x) \Leftrightarrow \forall x \neg P(x)
量词辖域扩展 (设 Q 不含 x)：
- \forall x (P(x) \lor Q) \Leftrightarrow (\forall x P(x)) \lor Q
- \exists x (P(x) \land Q) \Leftrightarrow (\exists x P(x)) \land Q
量词分配律：
- \forall x (P(x) \land Q(x)) \Leftrightarrow \forall x P(x) \land \forall x Q(x) (全称对合取可分配)
- \exists x (P(x) \lor Q(x)) \Leftrightarrow \exists x P(x) \lor \exists x Q(x) (存在对析取可分配)
- 注意：\forall 对 \lor 不可分配，\exists 对 \land 不可分配！

1.2.4 前束范式 (Prenex Normal Form)

形式：Q_1 x_1 Q_2 x_2 \dots Q_k x_k M

所有量词都在最左边。
M 是不含量词的基式。

化简步骤：

消去蕴涵：利用 $A \to B \Leftrightarrow \neg A \lor B$。
否定内移：利用德摩根律和量词否定律，将 \neg 移到原子公式前。
变元改名：确保不同量词使用不同的变量名 (如 \forall x P(x) \lor \exists x Q(x) 改为 \forall x P(x) \lor \exists y Q(y))。
量词左提：利用量词辖域扩展规则将量词提到最前面。

1.3 推理理论 (Inference Theory)

1.3.1 常用推理规则

假言推理 (Modus Ponens): P, P \to Q \Rightarrow Q
拒取式 (Modus Tollens): \neg Q, P \to Q \Rightarrow \neg P
析取三段论: P \lor Q, \neg P \Rightarrow Q
假言三段论: P \to Q, Q \to R \Rightarrow P \to R
化简律: P \land Q \Rightarrow P
附加律: P \Rightarrow P \lor Q

1.3.2 谓词推理规则

全称特指 (US): \forall x P(x) \Rightarrow P(c) (任意 \to 个体)
全称推广 (UG): P(x) \Rightarrow \forall x P(x) (任意个体 \to 任意) 注意限制条件
存在特指 (ES): \exists x P(x) \Rightarrow P(c) (存在 \to 特指常量 c) 注意 c 必须是新引入的
存在推广 (EG): P(c) \Rightarrow \exists x P(x) (个体 \to 存在)

1.3.3 证明方法

直接证明法：从前提及其逻辑推论出发，推导出结论。
附加前提证明法 (CP规则)：
- 若要证 $A \to B$，可将 A 作为附加前提加入前提集，只需证出 B 即可。
反证法 (归谬法)：
- 将结论的否定 \neg C 加入前提集，推导出矛盾 (F)。

第二章：集合论与二元关系

2.1 集合论

2.1.1 基础运算

并 (\displaystyle A \cup B)、交 (\displaystyle A \cap B)、补 (\displaystyle \bar{A})、差 (\displaystyle A - B)。
对称差 (\displaystyle A \oplus B)：$\displaystyle A \oplus B = (A - B) \cup (B - A)$。
- 属于 A 或属于 B，但不同时属于两者。
- 特性：\displaystyle A \oplus A = \emptyset, \displaystyle A \oplus \emptyset = A, $\displaystyle A \oplus B = B \oplus A$。

2.1.2 集合恒等式证明技巧

子集互证法：证明 \displaystyle A=B 即证 \displaystyle A \subseteq B 且 $\displaystyle B \subseteq A$。
- 任取 $\displaystyle x \in A$，逻辑推导 $\displaystyle x \in B$。
集合演算法：利用集合恒等式（类似逻辑等值式）进行变形。
- \displaystyle A - B = A \cap \bar{B} (最常用的变形)
- 德摩根律：\displaystyle \overline{A \cup B} = \bar{A} \cap \bar{B}
成员表法/特征函数法：
- 列出元素属于各集合的所有 \displaystyle 0/1 组合，验证结果是否一致。

2.1.3 幂集与笛卡尔积

幂集 $\displaystyle P(A)$：\displaystyle A 的所有子集构成的集合。
- 若 $\displaystyle |A|=n$，则 $\displaystyle |P(A)| = 2^n$。
- 易错：\displaystyle \emptyset \in P(A), $\displaystyle A \in P(A)$。
笛卡尔积 $\displaystyle A \times B$：有序对的集合。
- $\displaystyle |A \times B| = |A| \cdot |B|$。
- 不满足交换律：\displaystyle A \times B \neq B \times A (除非 \displaystyle A=B 或为空)。

2.2 二元关系

2.2.1 关系的表示与基本性质

关系 \displaystyle R 是 \displaystyle A \times A 的子集。

表示法：集合表达式、关系矩阵 $\displaystyle M_R$、关系图 $\displaystyle G_R$。

五大基本性质 (必须熟练判断)

性质	定义	矩阵特征	图特征
自反性	`\displaystyle \forall x, (x,x) \in R`	主对角线全 1	每个节点都有自环
反自反性	`\displaystyle \forall x, (x,x) \notin R`	主对角线全 0	无自环
对称性	`\displaystyle (x,y) \in R \to (y,x) \in R`	对称矩阵 (`\displaystyle M=M^T`)	所有边双向
反对称性	`\displaystyle (x,y) \in R \land (y,x) \in R \to x=y`	`\displaystyle m_{ij}=1 \land i \ne j \Rightarrow m_{ji}=0`	无双向边
传递性	`\displaystyle (x,y) \in R \land (y,z) \in R \to (x,z) \in R`	`\displaystyle M^2 \le M` (布尔乘)	有路必达（形成捷径）

2.2.2 关系矩阵详解

定义：设 $\displaystyle A = {a_1, a_2, \dots, a_n}$，关系矩阵 \displaystyle M_R 是一个 \displaystyle n \times n 的 0-1 矩阵。

若 $\displaystyle (a_i, a_j) \in R$，则 $\displaystyle m_{ij} = 1$；否则 $\displaystyle m_{ij} = 0$。

关系运算的矩阵表示

逆关系：\displaystyle M_{R^{-1}} = (M_R)^T (转置矩阵)。
并集/交集：\displaystyle M_{R \cup S} = M_R \lor M_S, \displaystyle M_{R \cap S} = M_R \land M_S (对应位置逻辑运算)。
复合关系：\displaystyle M_{S \circ R} = M_R \cdot M_S (布尔矩阵乘法)。
- 注意顺序：\displaystyle S \circ R 表示先 \displaystyle R 后 $\displaystyle S$，矩阵乘法也是 \displaystyle M_R 在前。
- 布尔乘法规则：$\displaystyle c_{ij} = \bigvee_{k=1}^n (a_{ik} \land b_{kj})$。
幂运算：\displaystyle M_{R^n} = (M_R)^n (布尔乘幂)。

2.2.3 关系性质的运算封闭性 (表 6.2)

运算	自反性	反自反性	对称性	反对称性	传递性
逆关系 `\displaystyle R^{-1}`	是	是	是	是	是
交 `\displaystyle R \cap S`	是	是	是	是	是
并 `\displaystyle R \cup S`	是	是	是	否	否
差 `\displaystyle R - S`	否	是	是	是	否
复合 `\displaystyle R \circ S`	是	否	否	否	否

注：表中“是”表示该性质在运算下一定保持，“否”表示不一定保持。

2.2.4 关系的闭包

自反闭包 \displaystyle r(R) = R \cup I_A (矩阵：主对角线置1)
对称闭包 \displaystyle s(R) = R \cup R^{-1} (矩阵：\displaystyle M \lor M^T)
传递闭包 \displaystyle t(R) = R \cup R^2 \cup \dots \cup R^n (连通性)

Warshall 算法 (计算传递闭包的核心)

用于在计算机中高效计算 $\displaystyle t(R)$。

输入：\displaystyle n \times n 关系矩阵 $\displaystyle M$。
逻辑：
```
for k from 1 to n:
    for i from 1 to n:
        for j from 1 to n:
            M[i,j] = M[i,j] or (M[i,k] and M[k,j])
```
直观理解：第 \displaystyle k 轮循环尝试以节点 \displaystyle k 为中转站，如果 \displaystyle i \to k 且 $\displaystyle k \to j$，则建立 \displaystyle i \to j 的直达路径。

2.2.5 等价关系与划分

定义：满足 自反、对称、传递 的关系。
等价类 $\displaystyle [x]_R$：所有与 \displaystyle x 有关系 \displaystyle R 的元素集合。
划分：
- 集合 \displaystyle A 被划分为若干个不相交的子集，其并集为 $\displaystyle A$。
- 定理：等价关系与划分一一对应。等价类就是划分出的子集。
- 例：整数集上的模 3 同余关系，划分为 \displaystyle \{3k\}, \{3k+1\}, \{3k+2\} 三类。

2.2.6 偏序关系详解

定义：满足 自反、反对称、传递 的关系。符号 $\displaystyle \preceq$。
相关符号：
- $\displaystyle x \preceq y$：\displaystyle x 小于等于 \displaystyle y (或 \displaystyle x 排在 \displaystyle y 前)。
- $\displaystyle x \prec y$：$\displaystyle x \preceq y \land x \ne y$。
- 可比：若 \displaystyle x \preceq y 或 $\displaystyle y \preceq x$，则称 \displaystyle x, y 可比。
- 不可比：若既不 \displaystyle x \preceq y 也不 $\displaystyle y \preceq x$，则称 \displaystyle x, y 不可比。
覆盖关系：
- 若 \displaystyle x \prec y 且不存在 \displaystyle z 使得 $\displaystyle x \prec z \prec y$，则称 \displaystyle y 覆盖 $\displaystyle x$。
- 哈斯图即是基于覆盖关系绘制的简化图。

哈斯图画法步骤

画出覆盖关系（即去掉所有自环和传递边）。
若 \displaystyle y 覆盖 $\displaystyle x$，则将 \displaystyle y 画在 \displaystyle x 上方并连线。
方向默认向上，省略箭头。

特殊元素 (重要考点)

设 \displaystyle (A, \preceq) 为偏序集，$\displaystyle B \subseteq A$。

极小元：\displaystyle B 中没有比它更小的元素。$\displaystyle \neg \exists x \in B, x \prec a$。
极大元：\displaystyle B 中没有比它更大的元素。$\displaystyle \neg \exists x \in B, a \prec x$。
最小元：\displaystyle B 中所有元素都比它大。\displaystyle \forall x \in B, a \preceq x (若存在则唯一)。
最大元：\displaystyle B 中所有元素都比它小。\displaystyle \forall x \in B, x \preceq a (若存在则唯一)。
下界：\displaystyle A 中小于等于 \displaystyle B 中所有元素的元素。$\displaystyle \forall x \in B, l \preceq x$。
上界：\displaystyle A 中大于等于 \displaystyle B 中所有元素的元素。$\displaystyle \forall x \in B, x \preceq u$。
下确界 (GLB/Infimum)：最大下界。符号 \displaystyle \inf B 或 $\displaystyle \wedge B$。
上确界 (LUB/Supremum)：最小上界。符号 \displaystyle \sup B 或 $\displaystyle \lor B$。

示例：整除关系

设 $\displaystyle A = {1, 2, 3, 4, 6, 12}$，关系为整除 (\displaystyle |)。

哈斯图层级：\displaystyle 12 在顶；\displaystyle 4, 6 在中；\displaystyle 2, 3 在下；\displaystyle 1 在底。
\displaystyle 2 和 \displaystyle 3 不可比。
子集 \displaystyle \{2, 3\} 的上界是 $\displaystyle 6, 12$，上确界是 $\displaystyle 6$。
子集 \displaystyle \{2, 3\} 的下界是 $\displaystyle 1$，下确界是 $\displaystyle 1$。

格

定义：偏序集 \displaystyle (L, \preceq) 中任意两个元素 \displaystyle x, y 都有确定的上确界 (\displaystyle x \lor y) 和下确界 (\displaystyle x \land y)。
性质：格可以看作代数系统，满足交换律、结合律、吸收律。

2.3 函数

2.3.1 函数的性质

单射：
- 定义：$\displaystyle f(a) = f(b) \Rightarrow a = b$。
- 判别：陪域中每个元素最多被 1 个箭头指到。
满射：
- 定义：$\displaystyle \forall y \in B, \exists x \in A, f(x)=y$。
- 判别：陪域中每个元素至少被 1 个箭头指到 (值域=陪域)。
双射：既单且满。
- 只有双射存在逆函数 $\displaystyle f^{-1}$。

2.3.2 复合函数

$\displaystyle (g \circ f)(x) = g(f(x))$。
性质：
- 若 \displaystyle f, g 都是单射，则 \displaystyle g \circ f 是单射。
- 若 \displaystyle f, g 都是满射，则 \displaystyle g \circ f 是满射。
- 若 \displaystyle g \circ f 是单射 \Rightarrow f 必为单射。
- 若 \displaystyle g \circ f 是满射 \Rightarrow g 必为满射。

2.3.3 特殊函数与算法复杂度

取整函数：
- 向下取整 (Floor) $\lfloor x \rfloor$：小于等于 x 的最大整数。
- 向上取整 (Ceiling) $\lceil x \rceil$：大于等于 x 的最小整数。
算法复杂度 (Big-O Notation)：
- 定义：设 f, g 是从整数集或实数集到实数集的函数。若存在常数 C 和 $k$，使得当 x > k 时，$\lvert f(x) \rvert \le C \lvert g(x) \rvert$，则称 f(x) 是 $O(g(x))$。
- 常见阶：$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$。
- 判定技巧：
  - 忽略系数：7n^3 是 $O(n^3)$。
  - 只看最高次项：n^2 + n + 1 是 $O(n^2)$。

2.3.4 典型考题：等价关系的证明

题目：设 R 是集合 A 上的等价关系，证明 R \circ R 也是 A 上的等价关系。 证明思路：

自反性：
- \because R 自反 $\therefore \forall a \in A, (a,a) \in R$。
- 故 $(a,a) \in R \circ R$（通过中间点 $a$），即 R \circ R 自反。
对称性：
- 任取 $(x,y) \in R \circ R$，则 \exists t \in A 使得 $(x,t) \in R \land (t,y) \in R$。
- \because R 对称 $\therefore (t,x) \in R \land (y,t) \in R$。
- 交换顺序得 $(y,t) \in R \land (t,x) \in R \Rightarrow (y,x) \in R \circ R$。
传递性：
- \because R 传递，且 R 是等价关系 $\therefore R \circ R = R$（等价关系的幂运算封闭性）。
- R 自身具备传递性，故 R \circ R 传递。
- (注：若题目要求严格分布证明，需设 (x,y) \in R^2, (y,z) \in R^2 推导 (x,z) \in R^2)。

第三章：组合数学

3.0 基础数论概念 (补充)

完全数 (Perfect Number)：
- 一个正整数等于其所有真因子（即除了自身以外的约数）之和。
- 例：$6 = 1 + 2 + 3$；$28 = 1 + 2 + 4 + 7 + 14$。
- 考点：判断给定数字是否为完全数，或计算其真因子之和。

3.1 基础计数原理

3.1.1 加法与乘法原理

加法原理 (分类)：S = S_1 ∪ S_2 … (互不相交)，则 |S| = |S_1| + |S_2| …
乘法原理 (分步)：步骤 1 有 n_1 种，步骤 2 有 n_2 种... 则总数为 n_1 \times n_2 …

3.1.2 排列与组合 (Notation: `C_n^r, P_n^r`)

模型	公式	典型场景
排列 (有序)	`P_n^r = \frac{n!}{(n-r)!}`	`n` 人选 `r` 人排队拍照
组合 (无序)	`C_n^r = \frac{n!}{r!(n-r)!}`	`n` 人选 `r` 人组队
可重排列	`n^r`	`r` 位密码，每位 `n` 种选择
可重组合	`C_{n+r-1}^r`	`n` 种口味冰淇淋选 `r` 球 (隔板法)

3.1.3 组合恒等式

对称性：C_n^r = C_n^{n-r}
帕斯卡公式：C_n^k = C_{n-1}^k + C_{n-1}^{k-1}
- 组合意义：选 k 人，要么包含特定人 A (C_{n-1}^{k-1})，要么不包含 A (C_{n-1}^k)。
二项式定理：(x+y)^n = \sum_{k=0}^n C_n^k x^{n-k} y^k
- 推论：\sum_{k=0}^n C_n^k = 2^n (所有子集个数)
- 推论：\sum_{k=0}^n (-1)^k C_n^k = 0 (奇数个元素的子集数 = 偶数个元素的子集数)
范德蒙恒等式：C_{m+n}^r = \sum_{k=0}^r C_m^{k} C_n^{r-k}

3.2 高级计数方法

3.2.1 鸽巢原理 (Pigeonhole Principle)

原理：N 个物体放入 k 个盒子，必有一个盒子至少有 \lceil N/k \rceil 个物体。
应用技巧：准确定义“鸽子”（物体）和“巢”（分类标准）。
- 例：任意 13 人中必有 2 人生肖相同 (13/12 \to 2)。

3.2.2 容斥原理 (Inclusion-Exclusion)

求 $|A_1 ∪ A_2 ∪ … ∪ A_n|$：

公式：\sum |A_i| - \sum |A_i ∩ A_j| + \sum |A_i ∩ A_j ∩ A_k| - …
错排问题 (D_n)：n 封信全部装错信封的方法数。
- D_n = n!(1 - \frac{1}{1!} + \frac{1}{2!} - … + (-1)^n \frac{1}{n!})
- 递推式：D_n = (n-1)(D_{n-1} + D_{n-2})

3.2.3 球盒模型 (Twelvefold Way 概览)

将 n 个球放入 k 个盒子：

球 (Label)	盒子 (Label)	限制	方案数
不同	不同	无	`k^n`
不同	不同	`\le 1`	`P_k^n`
相同	不同	无	`C_{n+k-1}^n` (隔板法)
相同	不同	`\ge 1`	`C_{n-1}^{k-1}` (先各放1个)
不同	相同	无	`S_2(n,k)` (第二类斯特林数)

3.3 递推关系 (Recurrence Relations)

3.3.1 线性常系数齐次递推关系

形式：a_n + c_1 a_{n-1} + … + c_k a_{n-k} = 0 求解步骤：

写出特征方程：$r^k + c_1 r^{k-1} + … + c_k = 0$。
求特征根 $r_1, r_2, …$。
写出通解结构：
- 无重根：a_n = A_1 r_1^n + A_2 r_2^n + …
- 有重根 (如 r_1 为 m 重根)：a_n = (A_1 + A_2 n + … + A_m n^{m-1}) r_1^n + …
代入初值求解常数 $A_i$。

3.3.2 生成函数 (Generating Functions)

定义：$G(x) = \sum_{n=0}^\infty a_n x^n$。
应用场景：
- 求解组合数：如 (1+x)^n 的系数。
- 求解不定方程 x_1 + x_2 + x_3 = k 的非负整数解个数。
  - 构造多项式 $(1+x+x^2+…)^3$，求 x^k 系数。

3.4 典型考题：不定方程解计数

题目：求 x_1 + x_2 + x_3 = 15 的整数解个数，满足 $x_1 ≥ 1, 0 ≤ x_2 ≤ 5, x_3 ≥ 0$。 解题思路：

换元消下界：令 $y_1 = x_1 - 1 ≥ 0$。
- 原方程变为 $(y_1+1) + x_2 + x_3 = 15 ⇒ y_1 + x_2 + x_3 = 14$。
全集计算：无上限限制时的非负整数解。
- $\displaystyle N = C_{14+3-1}^{3-1} = C_{16}^2 = 120$。
容斥处理上界：
- 坏条件 $P_1$：x_2 ≥ 6 (即原题 x_2 > 5)。
- 在坏条件 P_1 下，令 $z_2 = x_2 - 6 ≥ 0$。
- 方程变为 $y_1 + (z_2+6) + x_3 = 14 ⇒ y_1 + z_2 + x_3 = 8$。
- $|P_1| = C_{8+3-1}^2 = C_{10}^2 = 45$。
最终结果：$Ans = N - |P_1| = 120 - 45 = 75$。

3.5 典型考题：常系数齐次线性递推关系求解

题目：求解递推关系 $a_n = 7a_{n-1} - 16a_{n-2} + 12a_{n-3}$，初始条件为 $a_0 = 0, a_1 = 4, a_2 = 18$。 解题步骤：

构造特征方程 将递推式移项得 $a_n - 7a_{n-1} + 16a_{n-2} - 12a_{n-3} = 0$。对应的特征方程为： r^3 - 7r^2 + 16r - 12 = 0
求解特征根 观察系数，尝试代入 $r=2$：$8 - 28 + 32 - 12 = 0$，故 (r-2) 是因子。多项式除法分解得： (r-2)(r^2 - 5r + 6) = 0 (r-2)(r-2)(r-3) = 0 解得特征根：r_1 = 2 (二重根)，r_2 = 3 (单根)。
写出通解结构 对于二重根 2 和单根 $3$，通解形式为： a_n = (C_1 + C_2 n) \cdot 2^n + C_3 \cdot 3^n
代入初始条件求解常数
- 当 n=0 时：C_1 + C_3 = 0 \implies C_3 = -C_1
- 当 n=1 时：(C_1 + C_2) \cdot 2 + 3C_3 = 4
- 当 n=2 时：(C_1 + 2C_2) \cdot 4 + 9C_3 = 18
将 C_3 = -C_1 代入后两式：
- 2C_1 + 2C_2 - 3C_1 = 4 \implies -C_1 + 2C_2 = 4
- 4C_1 + 8C_2 - 9C_1 = 18 \implies -5C_1 + 8C_2 = 18
联立求解：由第一式得 $C_1 = 2C_2 - 4$，代入第二式： -5(2C_2 - 4) + 8C_2 = 18 -10C_2 + 20 + 8C_2 = 18 -2C_2 = -2 \implies C_2 = 1 回代得 C_1 = 2(1) - 4 = -2 C_3 = -(-2) = 2
最终解 a_n = (-2 + n) \cdot 2^n + 2 \cdot 3^n 或整理为： a_n = (n-2)2^n + 2 \cdot 3^n

第四章：图论

4.1 图的基本概念

4.1.1 定义与术语

图 $G=(V, E)$：V 为顶点集，E 为边集。
度 (Degree)：\deg(v) 为关联的边数 (自环算 2 度)。
- 握手定理：$\sum_{v \in V} \deg(v) = 2|E|$。
- 推论：奇度顶点的个数必为偶数。
子图：$V' \subseteq V, E' \subseteq E$。
补图：$\bar{G}$，顶点相同，边互补 (完全图 K_n 减去原图的边)。

4.1.2 图的连通性

路径 (Path)：$v_0, e_1, v_1, \dots, v_k$。
简单路径：不经过重复边。
基本路径 (Elementary Path)：不经过重复顶点。
连通图：任意两点间均有路径。
割点 (Cut Vertex)：删去该点及关联边，图分量增加。
割边 (Bridge)：删去该边，图分量增加。
连通度：
- 点连通度 $\kappa(G)$：使图不连通所需删除的最少顶点数。
- 边连通度 $\lambda(G)$：使图不连通所需删除的最少边数。
- 不等式关系：\kappa(G) \le \lambda(G) \le \delta(G) (最小度)。

4.1.3 图的矩阵表示

邻接矩阵 $A(G)$：n \times n 矩阵，a_{ij} 表示 v_i, v_j 间的边数。
- 性质：A^k 的元素 a_{ij}^{(k)} 表示从 v_i 到 v_j 长度为 k 的路径条数。
关联矩阵 $M(G)$：顶点与边的关系。

4.1.4 图的同构 (Isomorphism)

判断 G_1 \cong G_2 的必要条件 (若不满足则必不同构)：

顶点数、边数相同。
度数列相同 (将所有点度数排序后一致)。
连通分量数相同。
对应长度的回路数相同 (如都有或都没有三角形)。 充分性证明通常需要构造双射函数。

4.2 特殊图类

4.2.1 欧拉图 (Euler) 与哈密顿图 (Hamilton)

特性	欧拉图 (Euler)	哈密顿图 (Hamilton)
定义	经过每条边恰好一次的回路	经过每个顶点恰好一次的回路
判定(充要)	连通 + 所有点度为偶数	无简单充要条件
判定(充分)	-	(Dirac) `n \ge 3, \forall v, \deg(v) \ge n/2`
半图(路径)	连通 + 恰有 0 或 2 个奇度点	-
哈密顿图常用判定方式 (充分/必要)：

必要条件：$\delta(G) \ge 2$；且无割点 (2-连通)。
Dirac 定理 (充分)：$n \ge 3, \delta(G) \ge n/2$。
Ore 定理 (充分)：n \ge 3 且任意非邻接顶点 u,v 满足 $\deg(u)+\deg(v) \ge n$。

4.2.2 树 (Trees)

定义：连通且无回路的无向图。
等价性质：
1. 无回路且 $E = V - 1$。
2. 连通且 $E = V - 1$。
3. 任意两点间存在唯一路径。
度数和：$\sum_{v \in V} \deg(v) = 2E = 2(V-1)$。
叶子与内部点关系：设 L 为叶子数，则 $L = 2 + \sum_{\deg(v)\ge 2}(\deg(v) - 2)$。
树中心 (Center)：
- 反复删除所有叶子，最终剩下 1 个或 2 个顶点，这些顶点即中心。
- 等价表述：中心是到其他顶点最大距离最小的顶点(们)。
二叉树常用关系：
- 满二叉树：若内部结点数为 $I$，叶子数为 $L$，则 $L = I + 1$。
- 完全二叉树：n 个结点时高度 $h = \lfloor \log_2 n \rfloor + 1$。
最小生成树 (MST) 算法：
- Kruskal (加边法)：按权值排序，从小到大选边，不构成回路就加入。
- Prim (加点法)：从任意点开始，每次选离当前生成树集合最近的点加入。

4.2.3 平面图 (Planar Graphs)

欧拉公式：V - E + R = 2 (R 为面数，包含无限面)。
定理：连通简单平面图 (V \ge 3) 满足 $E \le 3V - 6$。
- 证明要点：每个面至少 3 条边，故 $3R \le 2E$，与欧拉公式联立得 $E \le 3V - 6$。
- 性质：简单平面图 (V \ge 3) 满足 $E \le 3V - 6$。
- 重要证明：存在度数 \le 5 的顶点
  - 假设所有顶点度数 $\deg(v) \ge 6$。
  - 由握手定理：$2E = \sum \deg(v) \ge 6V \Rightarrow E \ge 3V$。
  - 这与平面图性质 E \le 3V - 6 矛盾。
  - 故必然存在 \deg(v) \le 5 的顶点。
- 推论：K_5 (E=10, 3V-6=9) 不是平面图。
- 推论：K_{3,3} (E=9, 3V-6=12, 但它是二分图无三角形，需用 E \le 2V-4, 9 \not\le 8) 不是平面图。
常用等价与应用：
- 连通简单平面图：$E \le 3V - 6 \iff V \ge (E+6)/3$。
- 平均度：$\overline{d} = 2E/V < 6$，因此必存在度 \le 5 的顶点。
- 判否：若某简单图满足 $E > 3V - 6$，则必非平面图。
- 若无三角形 (如二分图)，改用 $E \le 2V - 4$。
库拉图斯基定理 (Kuratowski)：图是平面图 \iff 不含同胚于 K_5 或 K_{3,3} 的子图。

4.2.4 二分图 (Bipartite Graphs)

定义：顶点集可划分为 $X, Y$，且所有边都在 X 与 Y 之间。
判定：图是二分图 \iff 图中没有奇数长度的回路。
完全二分图：$K_{m,n}$，$|X|=m, |Y|=n$，边数 $E = mn$。
度数与边数：$\sum_{x \in X}\deg(x)=\sum_{y \in Y}\deg(y)=|E|$。
平面图推论：连通简单二分平面图 (V \ge 3) 满足 $E \le 2V - 4$。
二染色判定 (BFS/DFS)：
1. 对每个连通分量，任选起点染色为 0。
2. 进行 BFS/DFS，对每条边 (u,v) 要求 $color[u] \ne color[v]$。
3. 若遇到冲突 (已染且相同) 则非二分图；无冲突则是二分图。
匹配：Hall 定理 (相异代表系)。

4.3 核心算法逻辑

4.3.1 最短路径 (Dijkstra)

适用于非负权图。

初始化：S=\{start\}, dist[start]=0, 其他无穷大。
循环：
- 在 V-S 中找 dist 最小的点 $u$。
- 加入 $S$。
- 松弛 (Relax) u 的所有邻居 $v$：若 $dist[u] + w(u,v) < dist[v]$，则更新。

4.3.2 图着色 (Graph Coloring)

点色数 $\chi(G)$：相邻顶点不同色所需的最少颜色数。
布鲁克定理 (Brooks)：若 G 不是奇环也不是完全图，则 \chi(G) \le \Delta(G) (最大度)。
平面图四色定理：平面图 $\chi(G) \le 4$。
色多项式 $P_k(G)$：用 k 种颜色染色的方案数。
- 递推公式：P_k(G) = P_k(G-e) - P_k(G \cdot e)
  - $G-e$：删边。
  - $G \cdot e$：收缩边 (合并端点)。

4.3.3 最优二叉树 (Huffman Coding)

常考题型：给定一组权值，构造哈夫曼树并计算带权路径长度 (WPL)。

算法步骤：
- 初始化：将所有权值看作独立的单节点树森林 $F = {T_1, T_2, \dots}$。
- 循环：
  1. 在 F 中选出根节点权值最小的两棵树 $T_1, T_2$。
  2. 构造新树：根权值为 $W(T_1) + W(T_2)$，左右子树分别为 $T_1, T_2$。
  3. 从 F 中删除 $T_1, T_2$，加入新树。
  4. 重复直到 F 中只剩一棵树。
带权路径长度 (WPL)：
- WPL = \sum_{i=1}^n w_i \times l_i
- $w_i$：第 i 个叶子的权值。
- $l_i$：第 i 个叶子到根的路径长度（边数）。
- 简便算法：WPL = 所有非叶子节点的权值之和。

31 KiB Raw Permalink Blame History Unescape Escape