偏序关系
对于二元关系\(R\subseteq S \times S\),若\(R\)是自反的,反对称的,传递的,那么\(R\)称为偏序关系。
自反性
\(a \preceq a,\forall a\in S\)
反对称性
\(\forall a,b\in S\),若\(a\preceq b\)且\(b \preceq a\),则\(a=b\)
传递性
\(\forall a,b,c\in P\),若\(a\preceq b\)且\(b\preceq c\),则\(a\preceq c\)
按照定义,\(\le\)是个典型的偏序关系。在集合\(S\)中,若\(a\),\(b\)存在偏序关系,则称他们为可比的,反之不可比。
偏序集是由集合\(S\)与集合\(S\)上的偏序关系\(R\)构成的,记为\((S,R)\)
哈斯图(Hasse图)
对于元素\(x\),如果\(x\preceq y\)且不存在\(z\)使得\(x\preceq z\preceq y\),那么\(y\)就是\(x\)的覆盖元素,在哈斯图中连出一条\(x\rightarrow y\)的有向边。通过覆盖关系生成的图就是哈斯图。
例如,集合\(\{1,2,3,4,6,8,12\}\)上的关系\(\{(a,b)|a整除b\}\)画出的哈斯图如下:
在哈斯图中,通常将较小元放在下方,边的方向由点的相对位置隐士给出。
Dilworth定理
对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目。
设\(C\)是偏序集的一个子集,如果\(C\)中元素相互可比,那么可称\(C\)为链,如果\(C\)中元素相互不可比,则称\(C\)是反链。
上图中,红色部分就是一条链,蓝色部分是反链。
反链元素最多是2,整个图至少需要2条链\((\{1,2,4,8\}和\{3,6,12\})\)来覆盖。
通过上面的小栗子可以观察到Dilworth定理成立。
数学证明
设有限偏序集\((S,\preceq)\),\(|S|=n\),采用数学归纳法。
当\(n=1\)时,显然成立。
假设该命题对于\(n\le k\)均成立,下面证明\(n=k+1\)时也成立。
设\(A\)是一条最长反链,记为\(A=\{a_1,a_2,...,a_w\}\),定义
\(D(A)=\{x|\exists a\in A(x<a)\}\)
\(U(A)=\{x|\exists a\in A(x>a)\}\)
\(D(A)\),\(U(A)\)的含义为,对于集合中的每一个元素,能在\(A\)中找到小于或大于它的元素即可。
那么有\(S=A\cup D(A)\cup U(A)\)
对\(A\)进行分类讨论:
- 存在最长反链\(A\)使\(D(A)\)和\(U(A)\)均不为空。因为\(A\)是\(S\)的最长反链,所以\(A\)也是\(A\cup D(A)\)的最长反链,由于\(A\cup D(A)\)的元素个数小于\(k\),由归纳假设,\(A\cup D(A)\)可以划分为\(c_1,c_2,...,c_w\)共\(w\)条链,其中\(c_i\)的极大元是\(a_i\)。同理,\(A\cup U(A)\)也可以划分为\(d_1,d_2,...,d_w\)共\(w\)条链,其中\(d_i\)的极小元是\(a_i\),那么\(S\)可以划分为\(c_1\cup d_1\),\(c_2\cup d_2\),...,\(c_w\cup d_w\)共\(w\)条链。
- 对于每一个最长反链\(A\)都有\(D(A)\)或\(U(A)\)为空。那么反链\(A\)要么构成全上界,要么构成全下界。在\(S\)中选择一个极大元\(y\),在选择一个满足\(x\le y\)的极小元\(x\),则\(\{x,y\}\)可以构成一条链,且\(y\)在全上界中,\(x\)在全下界中。那么\(S-C\)中最长反链的元素个数为\(k-1\),根据归纳假设,其可以划分成\(k-1\)条链,再加上\(C\)得到\(w\)条链。
归纳证明完毕。
例题P1020 [NOIP1999 普及组] 导弹拦截
先构造出偏序集\(P=\{p_1,p_2,...,p_n\}\),记集合\(S=\{(i,p_i)|i\in N且1\le i \le n\}\),偏序关系\(R=\{((i,p_i),(j,p_j)|i\le j且p_i\ge p_j\}\)。\((S,R)\)构成一个偏序集。
第一问就是求最长链长度。
第二问的最少拦截系统对应着最少划分数等于最长反链中元素个数。反链意味着在当前的关系下不可比(集合中的点没有直接或间接相连的边),我们只要改变偏序关系,将\(p_i\ge p_j\)改为\(p_i<p_j\)(原先可比的点现在不可比,原先不可比的点现在可比),这样在新的哈斯图中最长链长的就对应着旧图中最长反链的长度。