动机
偏序刻画了哪些对象可以排在哪些对象之后,同时允许某些元素对互不可比。如果要把全部元素安排到若干有序的“轨道”中,至少需要多少条轨道?每个反链都给出一个障碍:它的元素不能位于同一条轨道上。狄尔沃思(Dilworth)定理指出,在有限偏序集中,这个显而易见的障碍就是唯一的障碍。
证明将把相容的相邻选择转化为匹配的边。匹配为每个元素至多选定一个前驱和一个后继。随后,最小顶点覆盖会揭示一个最大反链。这一构造既给出一种安排,又给出少于该数目的轨道不可能的证书,因此其结论比两个数相等这一无解释的等式更有用。
定义
定义 6.2.1
(链、反链、高度与宽度)
设 为有限偏序集。链是其元素两两可比的子集。反链是其相异元素两两不可比的子集。高度 是最大链的大小,宽度 是最大反链的大小。链划分把 表示为若干非空链的不交并;反链划分则使用非空反链。对于空偏序集,高度、宽度以及两种最小划分的大小均为零。
划分不同于单独一条长链或单独一个大反链:它必须恰好一次地容纳每个元素。任何反链与每条链至多相交于一个元素。因此反链的大小为每个链划分的部分数给出下界。同样,每条链也为反链划分的大小给出下界。
定义 6.2.2
(二分严格比较图)
取 的两个独立副本 。当且仅当原偏序集中 时,把 与 相连。同一元素的两个副本是不同的顶点,并且不存在边 。该图使用全部严格比较,包括由传递性推出的比较。
匹配是端点互不相交的边的集合,其最大大小记作 。顶点覆盖是与图中每条边都相交的顶点集合。这些图论定义针对的是双副本图,而链与反链由原偏序集的元素构成。明确保持这一区分可避免把两个副本重复计数。
定理/命题
引理 6.2.3
(二分图中的匹配与顶点覆盖)
在每个有限二分图中,匹配的最大大小等于顶点覆盖的最小大小。
定理 6.2.4
(狄尔沃思有限链划分定理)
对每个有限偏序集 ,划分 所需链的最少数目等于 。更确切地说,设 , 为严格比较图中最大匹配的大小,则这两个量都等于 。由一个最大匹配和一个大小相同的顶点覆盖,可以构造出最优链划分和最大反链。
定理 6.2.5
(高度版本:反链划分)
对每个有限偏序集 ,划分所需反链的最少数目等于 。对于非空的 ,令 为以 为终点的最大链的大小。 的非空水平集构成一个最优反链划分。
这两个命题在划分问题中交换了链与反链的角色。高度定理有简短的直接证明;宽度定理则需要更实质的论证。仅仅反转序关系并不能交换链与反链,因为这样不会改变可比性。
证明思路或证明
证明
(二分图中的匹配与覆盖)
我们首先论证证明中用到的二分图匹配—覆盖事实。取任意有限二分图的一个最大匹配,其两部分为 。从未匹配的左顶点集 出发,从左到右沿未匹配边行进,从右到左沿匹配边行进,并设 分别为两部分中可达的顶点集。没有未匹配的右顶点是可达的,因为由此得到的交错路径会使匹配变大。
每个可达的右顶点都与一个可达的左顶点匹配,并且 之外的每个可达左顶点都是经由其匹配边到达的。因此该匹配把 与 配对。此外,可达左顶点的每个邻点也是可达的:未匹配边可以被沿用,而它的匹配邻点(如果有)就是搜索中它的前驱。于是
覆盖每一条边,且 ,即匹配的大小。每个覆盖的大小至少等于每个匹配的大小,因为互不相交的匹配边需要互不相同的覆盖顶点。这就证明了所需的匹配—覆盖等式,包括空图的情形。
证明
(由匹配得链,由覆盖得反链)
现在对严格比较图使用一个最大匹配。把每条匹配边 替换为原元素上的有向连接 。每个元素至多有一条出边和一条入边。不存在有向圈,因为严格序关系构成的圈会与传递性及非自反性矛盾。因此这些连接构成互不相交的有向路径,允许孤立顶点。每条路径都是一条链,路径的数目为 。
反过来,一个分成 部分的链划分,在每条链内部相邻元素之间给出匹配边。大小为 的链给出 条边,故总共有 条边。左、右副本恰好施加了所需的前驱与后继限制。因此 ,这证明 是最小链划分的大小。
在双副本图中选取大小为 的顶点覆盖 ,并令
如果 中有两个元素可比,则它们对应的比较边没有被覆盖。因此 是反链。至多 个不同的原标号有副本在 中,所以 。所构造的链划分对每个反链给出相反方向的界。于是 ,这就证明了狄尔沃思定理。我们没有假设覆盖对每个标号至多包含一个副本;计数不等式和相反方向的界已经足够。
证明透视
划分与障碍在同一个数相遇
两个互相独立的构造在同一个数相遇。匹配给出有 个部分的链划分;使连接构成路径的,是匹配对每个左副本和每个右副本都至多使用一次,所以双副本的设计恰好就是“至多一个后继、至多一个前驱”的规则,而非自反性与传递性排除了有向圈。覆盖给出大小至少为 的反链;关键一步是只要某标号有一个副本被覆盖就把它排除,于是 内任何比较 都会留下未被覆盖的边 。单独任何一个构造都不能证明最优性。二分图引理只经由 进入,正是它使两个计数重合:反链至少有 个元素,而它的元素分属划分中不同的链,故至多有 个。传递性用了两次:一次排除有向圈,一次把所有比较都放进图中;若缺少后者,划分中一条链的相邻元素之间未必有边。
证明
(秩水平集构成最优反链划分)
对于高度定理,若 ,则把 接在以 为终点的一条最长链之后,得到 。因此秩相同的元素互不可比。这些水平集把偏序集划分为至多 个反链。大小为 的链至少需要这么多个反链部分,所以该划分是最优的。空集情形由约定得出。
例题详解
例题 6.2.6
(一个前驱与两个互不可比的后继)
设 且 ,其中 互不可比。比较图有边 ,所以 。使用 的匹配给出链 。覆盖 使 的两个副本都落在覆盖之外,从而给出最大反链 。因此宽度为二。秩水平集为 与 ,这是大小为二的最优反链划分,其大小也等于高度。
例题 6.2.7
(十二的因数同时提供两种证书)
按整除关系对 排序。链 与 给出两部分的划分; 是反链,证明宽度为二。对应的匹配有边 。覆盖 与每条严格整除边都相交,且大小同样为四。其未被覆盖的原标号恰为四与六。最长链的大小为四,所以高度定理改而需要四个反链部分。
例题 6.2.8
(仅用覆盖边会得到错误的最优化问题)
取五个元素,满足 、、、 以及所有由传递性得到的比较。宽度为二: 与 是链,而 是反链。只使用哈塞(Hasse)图的覆盖边时,最大匹配的大小为二,因为至多一条连接可以进入 ,至多一条可以离开 。错误的公式于是会给出三条链。加入比较 后,得到大小为三的匹配和正确答案二。链不必使用位于其两个成员之间的每一个元素。
提取实际的划分
证明描述了一种具体的重构方法。对每个原元素,记录其匹配的后继和匹配的前驱(如果存在)。从每个没有匹配前驱的元素开始建立一条链,并反复沿其后继前进直到没有后继为止。每个元素恰好出现在一条这样的路径中。无圈性保证每个连通分支中存在起点,而度数限制则防止出现分叉或合并。
两个副本使得链内部的元素可以同时有前驱和后继,却不允许有两个前驱:那样会在两条匹配边中使用同一个右副本顶点。两个后继同样会重复使用某个左副本顶点。因此匹配施加的是路径约束,而不是要求原元素总共只出现在一条连接中。
反链的重构采用相反的视角。仅当一个原标号的两个副本都不在覆盖中时,才选取该标号。若仅因左副本未被覆盖就选取,则不够:某条比较边可能恰在另一个被选标号的右副本处被覆盖。两个副本都不在覆盖中,才是使可比性不可能出现的精确性质。
宽度与高度约束总大小
最优链划分有宽度个部分,每个部分的大小至多为高度。因此
这个界并不能确定各条链,但常常立即给出障碍。如果偏序集多于九个元素,则其高度和宽度不可能都至多为三。等号是可能成立的,例如三条长度为三且互不可比的链。
一个应用涉及由互不相同的实数组成的序列。对其下标定义序:当 ,或 且下标 处的值较小时,称 。链即递增子序列。由于各值互异,反链按下标顺序读出即为递减子序列。若序列有 项,则不可能同时满足所有递增子序列长度至多为 且所有递减子序列长度至多为 。否则大小界将给出至多 项。因此必定出现相应的更长子序列之一。
互异性假设解释了为何不等式是严格的。若有重复值,按下标顺序不可比的一对元素的值可能相等而非递减。可以表述相关的非严格变体,但它们需要选定相等情形的约定,不应从互异值的论证中原样推断。
概念视角结构
高度与宽度刻画不同的障碍
长链迫使反链部分很多。宽反链迫使链部分很多。哈塞图所画出的高度或每行的长度不一定等于这两个量中的任何一个。划分定理所依据的是可比性和经过证明的极值,而不是图中顶点碰巧被放在何处。
秩水平集计算的是什么
高度证明中使用的秩,是以某元素为终点的最长链的大小,而不是图中任意的标记。沿着线性扩张计算时,它等于其严格前驱的最大秩加一,没有前驱时取零。每个前驱的秩此时都已可得。这给出反链水平集,并且只要记住取得每个最大值的前驱,还能得到最长链的证书。
偏序集不必是分级的:不同的极大链可能具有不同的长度。最长链秩依然适用,因为只需要严格递增这一性质。证明中没有用到每个覆盖关系都使秩恰好增加一的假设。强加这一更强的条件只会不必要地排除有效的例子。
常见错误
反例模式
互换高度与宽度会改变问题
四元全序集的宽度为一,高度为四。它需要一个链部分,却需要四个反链部分。反转其序并不改变这两个值:所有元素对仍然可比。正确的命题把最小链划分与宽度配对,把最小反链划分与高度配对;它们不是通过互换措辞、不加新证明就能得到的。
常见错误
(用哈塞图的边代替全部严格比较)
不要未经论证就用哈塞图的边取代严格比较图。对满足 、、、 的五元偏序集,哈塞图的边只容许大小为二的匹配,于是 会给出三条链;而比较 给出大小为三的匹配,正确答案是二。划分中一条链的相邻元素不一定构成覆盖关系。
常见错误
(最少链数不是最长链)
链部分的最小数目必须照顾所有元素,由宽度控制;单条链的最大大小则是高度。在 的因数中,最长链 有四个元素,但两条链 与 已经划分了整个偏序集。
总结
二分图匹配编码了链中相邻的连接,而最小覆盖则揭示出一个大小等于所需划分大小的反链。这以构造性的方式证明了狄尔沃思定理。以某元素为终点的最长链的秩给出互补的反链划分定理,并导出有用的大小界和子序列界。
练习
快速检查
(对三元基集上的子集偏序集,给出划分为三条链的方法,并给出一个三元反链以证明其最优性。)
每个子集(包括空集)必须在划分中恰好出现一次。
解答 · 答案
在基集 上,使用链 、 以及 。这些互不相交的链包含全部八个子集。三个单元素集构成反链,所以至少需要三条链。所给出的划分达到了这个下界。
快速检查
(对满足 、、、 的五元偏序集,求秩水平集和一条最长链。比较这两个划分定理。)
要包含由传递性推出的所有比较。
解答 · 答案
秩在 上为一,在 上为二,在 上为三。它们的水平集给出三个反链部分。一条最长链是 ,证明高度为三。两条链 与反链 证明宽度为二,且最小链划分的大小为二。这两个最优划分的数目确实可以不同。
快速检查
(证明:任何由十个互不相同的实数组成的序列,都含有长度为四的递增子序列或长度为四的递减子序列。)
指明下标偏序集,并应用已证明的大小界。
解答 · 答案
按下标与数值同时增大来对下标排序,并包含相等情形以保证自反性。传递性与反对称性由这两个严格不等式得出。如果所要求的两种子序列都不存在,则每条链和每个反链的大小都至多为三:互异性使得反链按下标顺序读出时是递减的。由大小界将得到十至多为九,矛盾。因此至少存在所述子序列之一。