等价关系与划分原理

可视化演示

等价关系满足自反性、对称性与传递性，可将集合划分为互不相交的等价类。本文详解等价关系的判定方法、等价类划分定理... 切换模式查看不同维度。

等价关系三性质

周末洗衣服，面对一整筐混着红、蓝、白各色衣物的筐子，你立下规矩：按颜色分类。这个“颜色相同”的标准之所以可靠，是因为它天生守三条规矩。第一，任何一件衣服都和自己颜色相同，这叫自反；第二，红衬衫和红袜子同色，红袜子也必然和红衬衫同色，这叫对称；第三，红衬衫与红袜子同色、红袜子与红 T 恤同色，那么红衬衫与红 T 恤也必然同色，这叫传递。三条规矩缺一不可，少了一条，分堆就难免出乱子。

把“颜色相同”翻译成数学语言：设 A 是一筐衣服的集合，R 是 A 上的二元关系——也就是由 A 中元素组成的有序对集合。当两个元素 x、y 满足关系时记作 (x,y) ∈ R，也可写作 x ~ y，读作“x 与 y 等价”。若关系 R 同时满足自反性、对称性、传递性，就称 R 是 A 上的等价关系。需要特别留意：判定时必须对 A 中所有元素逐一验证，任何一条不满足都可以举出反例否定，不能靠抽查几对元素就想当然。

三条性质的形式化写法如下。自反性要求每个元素都和自己配对；对称性要求关系双向成立；传递性要求关系能跳过中间元素直达结论。举个例子：平面上直线的“垂直”关系满足对称性（a⊥b 则 b⊥a），但直线不垂直于自身，且 a⊥b、b⊥c 时 a 与 c 平行而非垂直，两条性质同时被破坏，所以“垂直”不是等价关系。

$$\displaystyle \begin{aligned} & \text{自反性: } \forall x \in A,\ (x,x) \in R \\ & \text{对称性: } \forall x,y \in A,\ (x,y) \in R \Rightarrow (y,x) \in R \\ & \text{传递性: } \forall x,y,z \in A,\ (x,y) \in R \wedge (y,z) \in R \Rightarrow (x,z) \in R \end{aligned}$$

1. 自反性：集合中每个元素都必须与自身构成有序对，这是“人人有类”的底线。

$$\forall x \in A,\ (x,x) \in R$$

2. 对称性：只要 x 与 y 有关系，y 与 x 也必须有关系，关系不允许“单向箭头”。

$$\forall x, y \in A,\ (x,y) \in R \Rightarrow (y,x) \in R$$

3. 传递性：x 连 y、y 连 z，则 x 必须直接连 z，中间人可以省略。

$$\forall x, y, z \in A,\ (x,y) \in R \wedge (y,z) \in R \Rightarrow (x,z) \in R$$

回到洗衣房，三条规矩保证了“同色”能稳定分堆。再看生活里的关系：“住在同一栋楼”不传递——隔着两栋楼的人未必互相认识；“互相点赞”连自反都不满足——很少有人给自己点赞。唯有同时守住三性质的关系，才能担当“分类大任”，这正是等价关系在数学中被赋予的名字。

等价类与代表元

分好堆之后，你随手拿起一件红衬衫，把它举起来说：“所有和它同色的衣服，都归我管。”这一摞红衣服，数学上就叫红衬衫所在的等价类。等价类的精髓是：只要抓住一个代表元素，就能圈出整个类，无需逐一清点每一件衣服。

形式化定义：设 R 是 A 上的等价关系，对于任意 a ∈ A，a 的等价类记为 [a]_R，定义为 A 中所有与 a 满足关系 R 的元素组成的集合。换言之，[a]_R 就是“和 a 同色的那一整摞”。每个等价类中的任意一个元素，都可以担任这个类的代表元；代表元的选择是自由的，一个类里谁站出来说话都不影响结论。

等价类有两个核心性质。其一，类内任意两个元素都互相等价——红衬衫和红袜子直接满足关系 R；其二，任意两个不同等价类互不相交，且所有等价类拼起来恰好是全集 A。为什么不会交叉？若 [a] 与 [b] 有一个公共元素 c，则 a ~ c 且 b ~ c，由对称性得 c ~ b，再由传递性得 a ~ b，于是 a 与 b 同类，[a] = [b]。这个“公共元素必致同类”的三段式证明，是各类考试最爱考查的点。

$$[a]_R = \{\, x \in A \mid (a,x) \in R \,\}$$

1. 方括号记号：[a]_R 表示“以 a 为代表的等价类”，下标 R 标明了所依赖的关系。

$$[a]_R$$

2. 遍历全集：x 取遍集合 A 中的所有元素，一个不漏，保证类不丢元素。

$$x \in A$$

3. 筛选条件：只保留与 a 满足关系 R 的元素，也就是与 a“同色”的全部衣服。

$$(a,x) \in R$$

4. 集合构造完成：所有满足条件的 x 聚合成一个子集，即为 a 所在的类。

$$[a]_R = \{ x \in A \mid (a,x) \in R \}$$

从洗衣房视角看，红堆里任何一件衣服都可以当“发言人”，红袜子、红 T 恤、红衬衫全都等价，谁站出来说话都不影响“这堆是红的”这个结论。代表元素是自由的，但分类的边界是唯一的——这正是等价类既灵活又确定的奇妙之处。

划分原理定理

分堆完成后，你把每一摞小心地放进不同的抽屉：红堆抽屉、蓝堆抽屉、白堆抽屉。现在整套衣柜呈现出一种漂亮的结构——每个抽屉互不混装，所有抽屉合起来又不多不少覆盖了全部衣物。这种结构在数学上就叫集合的划分。

划分的定义：集合 A 的一组子集族 $\{A_1, A_2, \ldots, A_k\}$ 称为 A 的一个划分，如果这些子集两两互不相交且它们的并集等于 A。子集族里的每个成员叫一个块。注意划分与“覆盖”不同：覆盖只要求并集为全集，允许重叠；划分额外要求互斥，两者是严格的包含关系。

划分定理是本课最核心的定理：集合 A 上的任意等价关系 R，其全部等价类构成 A 的一个划分；反过来，A 的任意一个划分，也必然能定义一个等价关系——两个元素等价当且仅当它们落在同一个块中。这两种结构一一对应：给出分堆的规矩（等价关系），必然得到一种布局（划分）；给出任何一种合理布局，也必然能反推出它的分堆规矩。

$$\displaystyle A = \bigcup_{[a]_R \in A/R} [a]_R, \qquad [a]_R \cap [b]_R = \varnothing \ \text{或} \ [a]_R = [b]_R$$

1. 并集覆盖：所有等价类取并集后恰好等于全集 A，衣服一件不落。

$$A = \bigcup_{[a]_R \in A/R} [a]_R$$

2. 两两互斥：任意两个等价类要么完全相同，要么一个公共元素都没有。

$$[a]_R \cap [b]_R = \varnothing \ \text{或} \ [a]_R = [b]_R$$

3. 一一对应：等价关系与划分互为充要条件，可互相转化。

$$\text{等价关系} \longleftrightarrow \text{划分}$$

因为一一对应，数“划分的种数”就等于数“等价关系的个数”。含 n 个元素的集合上的划分总数由贝尔数 Bₙ 给出，例如 3 元素集合有 B₃ = 5 种划分。衣柜的世界里，等价关系是“分堆的规矩”，划分是“分好之后的布局”：一个规矩必然产生一种布局，而任何一种布局也必然对应唯一的规矩。

商集的构造

现在你不需要关心具体哪件红衬衫了，洗衣房只需一份“堆的清单”：红堆、蓝堆、白堆。这份清单——把整筐衣服压缩成三个名称——就是商集。商集是“类型的集合”，它站在更高一层看问题，不再纠结于个体细节。

严格定义：设 R 是 A 上的等价关系，商集 A/R 是 A 的所有等价类组成的集合，即 A/R = { [a]_R | a ∈ A }。A 中每个元素都映射到它所在的那个类，这个映射 f: A → A/R，f(a) = [a]_R，称为自然映射（也叫自然同态），它把“个体”投影为“类型”——就像把一万件具体衣服投影成三个堆名。

商集的基数满足基数守恒：原集合的大小等于各等价类基数之和。因为每个等价类互不相交、合起来覆盖全集，总数自然守恒。把 A 想象成一整筐衣服，商集就是抽屉清单，每件衣服恰好属于一个抽屉。整数按模 3 同余得到的商集只有三个元素：余 0 类、余 1 类、余 2 类——无穷多个整数被压缩成了三堆，这就是商集的“降维”威力。

$$A/R = \{\, [a]_R \mid a \in A \,\}, \qquad |A| = \sum_{C \in A/R} |C|$$

1. 商集记号：A/R 读作“A 商 R”，是由等价类构成的集合。

$$A/R$$

2. 逐元素生成：对 A 中每个元素 a，生成它的等价类 [a]_R。

$$a \mapsto [a]_R$$

3. 去重取类：重复的等价类只保留一个，于是商集只包含互不相同的类。

$$A/R = \{ [a]_R \mid a \in A \}$$

4. 基数守恒：各等价类大小之和等于原集合大小。

$$|A| = \sum_{C \in A/R} |C|$$

洗衣房老板不需要记住一万件衣服，只需要记住三堆的名字；客服问“这件衣服归哪堆”，自然映射两秒作答。商集就是我们给繁杂世界做的“降维总结”——从个体到类型，从细节到结构，这种思维方式贯穿数学、算法与工程。

典型例题实战

理论学完，该上手做题了。最经典的等价关系莫过于“模 n 同余”。想象一块 12 小时的钟表：3 点和 15 点指向同一个刻度，我们说 3 与 15 模 12 同余。时针的世界里，12 个刻度把无数个时刻分成了 12 个等价类——这正是洗衣房按颜色分堆在数字世界里的投影。

定义：整数 a 与 b 模 n 同余，记作 a ≡ b (mod n)，当且仅当 n 整除 a − b。验证三性质：a − a = 0 被 n 整除，自反成立；若 n | (a−b)，则 n | (b−a)，对称成立；若 n | (a−b) 且 n | (b−c)，两式相加得 n | (a−c)，传递成立。因此模 n 同余是整数集上的等价关系，它的等价类一共 n 个，分别由余数 0, 1, ……, n−1 代表，记作 [0], [1], ……, [n−1]。

另一个常见例题是三角形相似关系：三角形与自身相似（自反）；A∽B 则 B∽A（对称）；A∽B 且 B∽C 则 A∽C（传递）。所以所有三角形按形状被分成等价类——两个三角形同属一类当且仅当三个角对应相等。解题时，先想清楚“什么让我们把两个对象看作一类”，再套三性质验证，最后数清类的个数，三步即可拿下。

$$a \equiv b \pmod{n} \Longleftrightarrow n \mid (a-b)$$

1. 同余记号：a 与 b 模 n 同余，读作“a 同余于 b 模 n”。

$$a \equiv b \pmod{n}$$

2. 差被整除：两者之差是 n 的整数倍，这是判定同余的唯一标准。

$$n \mid (a-b)$$

3. 等价类形状：同一类中的数相差 n 的整数倍，类由余数唯一标记。

$$[r] = \{ r + kn \mid k \in \mathbb{Z} \}$$

回到洗衣房：洗衣房按“色系”分堆，数学按“余数”分堆，钟表按“刻度”分堆——所有的分堆逻辑殊途同归，都是同一个等价关系的框架。做题时先问“什么让我们把两个对象看作一类”，再验证三性质，问题就迎刃而解。

并查集原理

洗衣房规模变大了，一天要处理十万件衣服，老板需要一个智能分拣助手。助手的工作只有两件：回答“这两件衣服同不同色？”（查询），以及“把这两小堆并成一大堆”（合并）。并查集（Union-Find）就是干这个的专用数据结构——它用一组“组长指针”实时维护等价类。

并查集用一个数组 parent 记录每个元素的“组长”：parent[x] 指向 x 所在等价类的父节点。若 parent[x] = x，说明 x 就是这棵树的根，也就是该等价类的代表元。查找操作 find(x) 沿着 parent 链往上爬，直到抵达根，返回根——即返回 x 所在等价类的代表。合并操作 union(x, y) 则先找到两个代表元，若相同说明已同类，否则把一棵树的根挂到另一棵树的根下。

朴素 find 最坏要爬 O(n) 层（树退化成链）。于是引入路径压缩：在 find 的过程中，把沿途所有节点的 parent 直接改成根。下次再查其中任何一个元素，只需一步就到达根。配合按秩合并（union 时把矮树挂到高树下），整体摊还复杂度逼近常数 O(α(n))，α(n) 是增长极慢的反阿克曼函数，在实际问题中完全可以当作常数。

$$\displaystyle \mathrm{find}(x) = \begin{cases} x, & \mathrm{parent}[x] = x \\ \mathrm{find}(\mathrm{parent}[x]), & \mathrm{parent}[x] \neq x \end{cases}$$

1. 父指针数组：parent 数组记录每个元素当前指向的“上级”，数组下标就是元素本身。

$$\mathrm{parent}[x]$$

2. 递归出口：当 parent[x] = x 时，x 就是这棵树的根，也就是该等价类的代表元。

$$\mathrm{find}(x) = x \iff \mathrm{parent}[x] = x$$

3. 沿链上溯：否则问题转化为 find(parent[x])，把链不断上移，直至抵达根。

$$\mathrm{find}(x) = \mathrm{find}(\mathrm{parent}[x])$$

助手的工作方式像极了你教它认色：每件衣服的标签上写着组长是谁，组长上面还有总组长。路径压缩就像助手把“红衬衫 → 红袜子 → 红组长”这条长链直接改写成“红衬衫 → 红组长”，下一次秒答。这就是为什么十万件衣服的查询，助手几乎不假思索。

并查集应用

分拣助手不只服务洗衣房。凡是“动态维护互不相交的分组，并回答元素是否同组”的问题，都是并查集的舞台。把它从洗衣房搬到计算机世界，它就成了图算法中最常见的高效工具。

三大经典应用。第一，无向图的连通分量：把每个顶点看作一件衣服，每条边看作“同色”证据，扫描所有边执行 union，最后 find 同根的点属于同一连通分量。第二，最小生成树（克鲁斯卡尔算法）：按边权从小到大加入边，用并查集判断两端点是否已在同一连通块——若已连通则跳过（加入会成环），否则 union 并累计权值。第三，动态连通性问题：在线地处理“加边 + 询问两点是否连通”的操作序列，每一次查询都是 O(α(n)) 级别的瞬时响应。

复杂度上，m 次操作（混合 find/union）的摊还时间为 O(m·α(n))，在一切实际输入中 α(n) ≤ 5，可以当作常数看待。这让并查集成为千万级节点图规模下的首选方案。实现时注意两个细节：find 必须写路径压缩（递归或迭代皆可），union 必须按秩或按 size 合并；这两个优化缺一个，最坏情况就会退化到 O(n)，从“秒答”变成“死等”。

$$\displaystyle \mathrm{union}(x,y):\ r_x = \mathrm{find}(x),\ r_y = \mathrm{find}(y); \qquad r_x \neq r_y \Rightarrow \mathrm{parent}[r_x] = r_y$$

1. 定位代表：先分别找出 x、y 所在等价类的代表元，这是判断与合并的前提。

$$r_x = \mathrm{find}(x), \quad r_y = \mathrm{find}(y)$$

2. 同组判断：两代表相同则已同类，合并可直接跳过，避免白费功夫。

$$r_x = r_y \Rightarrow \text{无需合并}$$

3. 挂接根节点：不同则把某棵树的根接到另一棵树的根下，完成两组融合。

$$\mathrm{parent}[r_x] = r_y$$

从洗衣房到数据中心，等价关系的框架始终如一：先定义“什么算同类”，再用并查集高效维护“谁和谁同类”。社交网络里的朋友团体、图像里的连通域、分布式系统的数据分片——它们都是同一座“等价类分拣机”的不同版本。

AI 应用场景

Python 演示

class UnionFind:    """并查集: 用树结构维护集合中元素的等价类分组"""     def __init__(self, n):        self.parent = list(range(n))  # parent[i] 指向组长        self.rank = [0] * n           # 树深度估计, 用于按秩合并        self.count = n                # 当前等价类的个数     def find(self, x):        if self.parent[x] != x:            self.parent[x] = self.find(self.parent[x])  # 路径压缩        return self.parent[x]     def union(self, x, y):        rx, ry = self.find(x), self.find(y)        if rx == ry:            return False              # 已属同一等价类, 无需合并        if self.rank[rx] < self.rank[ry]:            rx, ry = ry, rx        self.parent[ry] = rx        if self.rank[rx] == self.rank[ry]:            self.rank[rx] += 1        self.count -= 1        return True     def connected(self, x, y):        return self.find(x) == self.find(y)  def main():    uf = UnionFind(8)  # 8 个元素, 初始各自成类    edges = [(0, 1), (1, 3), (2, 5), (4, 6), (5, 7), (0, 4)]    for a, b in edges:        uf.union(a, b)    print("0 和 3 同属一个等价类:", uf.connected(0, 3))   # True    print("0 和 2 同属一个等价类:", uf.connected(0, 2))   # False    print("等价类个数:", uf.count)                          # 2    print("parent 数组:", uf.parent)  if __name__ == "__main__":    main()

1. self.parent = list(range(n))初始化时每个元素自成一组，parent[i]=i 表示 i 是自己这组的代表元。
2. self.parent[x] = self.find(self.parent[x])递归查找并顺手做路径压缩，把 x 直接挂到总代表下面，下次查询一步到位。
3. rx, ry = self.find(x), self.find(y)先找到两个元素各自的代表元，比较代表元即可判断是否同类。
4. if rx == ry: return False代表相同说明本就在同一等价类中，合并失败返回 False。
5. if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx保证 rx 始终是较深的树根，为按秩合并做准备。
6. self.parent[ry] = rx把较浅树的根挂到较深树的根下，树高得到控制。
7. self.count -= 1每次成功合并，等价类总数减少 1，count 直接给出当前类的数量。

常见误区

面试题