速成 · 集合论与图论

这门课的两半不是硬拼在一起的。集合论提供“对象、二元关系和映射”的语言，图论把一种二元关系画成顶点和边，再研究局部连接怎样决定整体结构。

从集合走到图

可以按下面的顺序重建课程：

1. 集合回答有哪些对象，集合运算怎样对应逻辑运算；
2. 关系是笛卡尔积的子集，用来表达“谁与谁有关”；
3. 函数是满足全定义、单值条件的特殊关系；
4. 自然数和基数用双射比较集合大小；
5. 图把对象放在顶点，把二元关系放在边；
6. 连通、最短路、树、欧拉路、哈密顿路、匹配和平面性分别回答不同的结构问题；
7. 社交网络把这些概念重新放回真实数据。

集合论最该掌握的四组判断

元素与子集不能混

$x\in A$ 说的是对象和集合；$A\subseteq B$ 说的是两个集合。空集满足 $\varnothing\subseteq A$，但通常不能因此写 $\varnothing\in A$。

集合运算可以直接翻译成命题逻辑：

$$x\in A\cap B\iff (x\in A)\land(x\in B),$$ $$x\in A\cup B\iff (x\in A)\lor(x\in B).$$

证明集合恒等式时，任选一个元素，把两边都翻译成逻辑式，通常比画图可靠。

关系的五种性质要逐个量化

设 $R\subseteq X\times X$：

• 自反：每个 $x$ 都有 $xRx$；
• 反自反：每个 $x$ 都没有 $xRx$；
• 对称：$xRy\Rightarrow yRx$；
• 反对称：$xRy$ 且 $yRx\Rightarrow x=y$；
• 传递：$xRy$ 且 $yRz\Rightarrow xRz$。

反对称不是“不对称”。$\leq$ 是反对称关系，却允许 $x\leq x$。

等价关系是“自反 + 对称 + 传递”，产生集合的划分；偏序是“自反 + 反对称 + 传递”，产生可以比较但未必处处可比的层次。

函数先检查存在，再检查唯一

$f:X\to Y$ 要求每个 $x\in X$ 都对应某个 $y\in Y$，而且只能对应一个。单射检查不同输入是否会撞到同一输出；满射检查陪域中是否有漏掉的元素；双射同时满足二者，才有从整个 $Y$ 回到 $X$ 的逆函数。

无穷集合用双射比较大小

可数不是“有限”，而是能与自然数排成一个序列。有理数可数，实数不可数；对任何集合 $X$，幂集都严格更大：

$$|X|<|\mathcal P(X)|.$$

这条结论来自对角构造，而不是因为“子集看起来很多”。

图论做题先认清问题在问边还是顶点

问题	要覆盖什么	典型判据或算法
连通性	顶点之间能否到达	BFS/DFS、强连通分支
最短路	路径总权最小	BFS、DAG 动态规划、Dijkstra
生成树	连通全部顶点且无圈	树的等价性质、最小生成树
欧拉路	每条边恰好一次	度数与连通性
哈密顿路	每个顶点恰好一次	必要/充分条件，通常更难
匹配	选互不共享端点的边	增广路、Hall 定理
平面性	能否无交叉嵌入平面	欧拉公式、边数界、Kuratowski

欧拉和哈密顿最容易混：前者管边，后者管顶点。欧拉图有漂亮的充要条件；哈密顿图没有同样简单的通用判定，不能拿度数奇偶直接套。

五条公式先会解释，再背

握手定理：

$$\sum_{v\in V}\deg(v)=2|E|.$$

邻接矩阵计数：$(A^k)_{ij}$ 等于从 $i$ 到 $j$、长度为 $k$ 的通路数。

树：若有 $n$ 个顶点，则边数是 $n-1$；反过来还必须配合连通或无圈条件使用。

连通平面图的欧拉公式：

$$|V|-|E|+|F|=2.$$

至少有三个顶点的简单连通平面图满足：

$$|E|\leq 3|V|-6.$$

最后一条只是平面性的必要条件。通过边数界不能证明某图一定平面，只能在违反上界时证明它不平面。

算法题按“不变量”理解

• BFS 每次按层扩展，因此第一次到达某点时边数最少；
• Dijkstra 每次固定暂定距离最小的未确定点；非负边保证以后绕路不会把它变小；
• 二分图匹配沿增广路把“未匹配—已匹配”边交替翻转，匹配数恰好增加一；
• 强连通分支压缩后一定是 DAG，否则环上的分支本应合并；
• 关键路径中，活动最早开始时间等于最晚开始时间时没有机动余量。

背流程前先说出这句“不变量为什么保持”，算法就不容易写成无意义的步骤表。

源材料边界

源目录保留了 13 个教学主题、第三/第四/第八次作业和一次社交网络大作业，没有真实考试卷。因此真题目录保持空，不把课件思考题或练习题冒充真题。