目录
偏序和等价关系
关系:设 \(X\) 是一个集合,\(X\) 上的关系是 \(X\) 的元素的有序对集合 \(X\times X\) 的子集 \(R\)。我们把属于 \(R\) 的有序对 \((a,b)\) 写作 \(aRb\)。把不属于 \(R\) 的有序对 \((a,b)\) 写作 \(a\not R b\)。
集合 \(X\) 上的关系 \(R\) 可能具有的一些特性:
- 如果对于 \(X\) 中所有的 \(x\),都有 \(xRx\),则称 \(R\) 是自反的。
- 如果对于 \(X\) 中所有的 \(x\),都有 \(x\not Rx\),则称 \(R\) 是反对称的。
- 如果对于 \(X\) 中所有的 \(x\),只要 \(xRy\) 就有 \(yRx\),则称 \(R\) 是对称的。
- 如果对于 \(X\) 中所有的 \(x\),只要 \(xRy\) 就有 \(y\not Rx\),则称 \(R\) 是反对称的。
- 对于 \(X\) 中的 \(x,y,z\),只要 \(xRy,yRz\),就有 \(xRz\),则称 \(R\) 是传递的。
偏序、偏序集:集合 \(X\) 上的偏序是一个自反、反对称且传递的关系,集合 \(X\) 上的严格偏序是一个反自反、反对称且传递的关系。因此 \(\subseteq,\le,\mid\) 均是偏序,而 \(\subset,<\) 均是严格偏序。在其上定义了偏序 \(\le\) 的集合 \(X\) 也叫做偏序集,记作 \((X,\le)\)。
若 \(xRy\) 或 \(yRx\),则说 \(x\) 和 \(y\) 是可比的,否则不可比。若 \(X\) 的每一对元素都是可比的,则集合 \(X\) 上的偏序 \(R\) 是全序。比如数集上标准的 \(\le\) 是一个全序。
设 \((X,\le)\) 是全序,则存在 \(X\) 的一个排列 \(\{a_1,a_2,\dots,a_n\}\),使得若 \(i,j\) 则 \(a_i\le a_j\)。
如果 \(a<b\) 并且没有元素 \(c\) 能够夹在 \(a\) 和 \(b\) 之间,那么称 \(a\) 被 \(b\) 覆盖 。
反链是 \(X\) 的一个子集 \(A\),使得它的任意两个元素都不可比,链是 \(X\) 的一个子集 \(A\),使得它的任意两个元素都可比,因此链是 \(X\) 的一个全序子集。显然反链和链的交集大小小于等于 \(1\)。
若 \(X\) 存在大小为 \(r\) 的反链 \(C\),则\(X\) 的链划分数大于等于 \(r\)。
将 \((X,\le)\) 放在图上,得到图 \((V,E)\),显然 \((V,E)\) 是一个 DAG,称一个 偏序集的极小元为所有放在 DAG 上的入度为\(0\) 的元素集合,极大元为所有放在 DAG 上的出度为\(0\) 的元素集合。
Dilworth 定理
先说 Dilworth 定理的对偶定理。
定理 1
设 \((X,\le)\) 是有限偏序集,而 \(r\) 是链的最大大小,则 \(X\) 可以被划分成 \(r\) 个反链,但不能划分成少于 \(r\) 个反链。
证明:显然不能划分成少于 \(r\) 个反链,只需证明有划分成 \(r\) 个反链的构造即可,显然 \(X\) 的极小元是一个反链,然后将其从 \(X\) 中删去,重复操作即可,恰好划分为 \(r\) 个反链。
定理 2(Dilworth 定理)
设 \((X,\le)\) 是有限偏序集,而 \(r\) 是反链的最大大小,则 \(X\) 可以被划分成 \(r\) 个链,但不能划分成少于 \(r\) 个链。
证明:设 \(|X|=m\)。当 \(|X|=1\) 时定理成立。
当 \((X,\le)\) 存在一个大小为 \(m\) 的反链 \(A\),满足 \(A\) 既不是 \(X\) 的极小元集合,也不是 \(X\) 的极大元集合,设 \(A^{+}\) 表示所有属于 \(X\) 且满足 \(a\le x,a\in A\) 的元素集合、\(A^{-}\) 表示所有属于 \(X\) 且满足 \(x\le a,a\in A\) 的元素集合。有 \(A^{+}\cap A^{-}=A\),\(A^{+}\cup A^{-}=X\),然后将 \(A^{+},A^{-}\)递归归纳到下面一种情况中,然后将两个集合的解拼在一起即可。
当 \((X,\le)\) 不存在一个大小为 \(m\) 的反链 \(A\),满足 \(A\) 既不是 \(X\) 的极小元集合,也不是 \(X\) 的极大元集合,显然此时长度为 \(m\) 的反链为极小元或极大元。若极小元为长度为 \(m\) 的反链,则在DAG 上极小元指出的点的入度大于 \(1\),此时随便选择属于极小元的元素 \(x\) 和属于极大元的元素 \(y\),则 \(X-\{x,y\}\) 的反链长最大为 \(m-1\),继续递归归纳即可,反链为极大元同理。
标签:偏序,le,浅谈,定理,极大元,集合,反链 From: https://www.cnblogs.com/fzrcy/p/18362013