线性扩展
偏序集上与原偏序相容的全序;有限情形等价于保序编号,也等价于覆盖关系 DAG 的拓扑序。标签 数学 / 偏序 / 线性扩展 / 拓扑排序 / 序理论
定义
设 是偏序集。 上的全序 若满足:只要 就有 ,则称 是 的一个线性扩展。也就是说,线性扩展保留原偏序的全部先后关系,只把不可比的元素补成可比。
有限情形也可以写成保序双射
满足 时 。这里 只是 元有限链的标准代表;任何 元全序都与它保序同构。
例子
- 链:线性扩展唯一。
- 反链:任意排列都是线性扩展,共有 个。
- ,, 与 不可比:线性扩展为 、、。
与拓扑序的关系
有限偏序集的覆盖关系构成一个 DAG。这个 DAG 的拓扑序恰好是原偏序集的线性扩展;反过来,DAG 的拓扑序也是其可达偏序的线性扩展。若 DAG 有环,则既不存在拓扑序,也不存在对应的线性扩展。
构造
反复取当前偏序集的极小元并删除,得到的顺序就是线性扩展;这就是 Kahn 拓扑排序。极小元不唯一时,不同选择会得到不同的线性扩展。
有限偏序集一定有线性扩展;无限偏序集也有,这就是 Szpilrajn 扩展定理,证明通常依赖选择公理。
计数
线性扩展一般不唯一。反链有 个,链只有 个;一般偏序集的线性扩展精确计数是困难的,没有简单的乘积公式。
常见误解
- 认为任意排列都是线性扩展:只有不违反原偏序的排列才是。
- 认为线性扩展唯一:反链有 个;极小元不唯一时通常也不唯一。
- 认为线性扩展要保持不可比关系:它只要求不违反原序;不可比元素在扩展中可以变得可比。
- 认为线性扩展就是拓扑排序算法:线性扩展是序论对象,拓扑排序是构造它的算法。
- 认为有环 DAG 也有线性扩展:环上同时有 和 ,无法放进全序。
- 把线性扩展和线性化混为一谈:线性化是选取或使用线性扩展的过程。
- 认为无限偏序集也能直接反复取极小元:无限情形需要 Szpilrajn 扩展定理,通常依赖选择公理。
- 把“线性扩展”写成“线性拓展”:标准术语是线性扩展,线性扩张也可。