线性扩展

偏序集上与原偏序相容的全序;有限情形等价于保序编号,也等价于覆盖关系 DAG 的拓扑序。

标签 数学 / 偏序 / 线性扩展 / 拓扑排序 / 序理论

定义

设 (𝑃,≤) 是偏序集。𝑃 上的全序 ⪯ 若满足:只要 𝑥≤𝑦 就有 𝑥⪯𝑦,则称 ⪯ 是 ≤ 的一个线性扩展。也就是说,线性扩展保留原偏序的全部先后关系,只把不可比的元素补成可比。

有限情形也可以写成保序双射

ℓ:𝑃→{1,…,𝑁},𝑁=|𝑃|,

满足 𝑥<𝑦 时 ℓ(𝑥)<ℓ(𝑦)。这里 {1,…,𝑁} 只是 𝑁 元有限链的标准代表;任何 𝑁 元全序都与它保序同构。

例子

  • 链:线性扩展唯一。
  • 反链:任意排列都是线性扩展,共有 𝑁! 个。
  • 𝑃={𝑎,𝑏,𝑐},𝑎<𝑏,𝑐 与 𝑎,𝑏 不可比:线性扩展为 𝑎<𝑏<𝑐、𝑎<𝑐<𝑏、𝑐<𝑎<𝑏。

与拓扑序的关系

有限偏序集的覆盖关系构成一个 DAG。这个 DAG 的拓扑序恰好是原偏序集的线性扩展;反过来,DAG 的拓扑序也是其可达偏序的线性扩展。若 DAG 有环,则既不存在拓扑序,也不存在对应的线性扩展。

构造

反复取当前偏序集的极小元并删除,得到的顺序就是线性扩展;这就是 Kahn 拓扑排序。极小元不唯一时,不同选择会得到不同的线性扩展。

有限偏序集一定有线性扩展;无限偏序集也有,这就是 Szpilrajn 扩展定理,证明通常依赖选择公理。

计数

线性扩展一般不唯一。反链有 𝑁! 个,链只有 1 个;一般偏序集的线性扩展精确计数是困难的,没有简单的乘积公式。

常见误解

  • 认为任意排列都是线性扩展:只有不违反原偏序的排列才是。
  • 认为线性扩展唯一:反链有 𝑁! 个;极小元不唯一时通常也不唯一。
  • 认为线性扩展要保持不可比关系:它只要求不违反原序;不可比元素在扩展中可以变得可比。
  • 认为线性扩展就是拓扑排序算法:线性扩展是序论对象,拓扑排序是构造它的算法。
  • 认为有环 DAG 也有线性扩展:环上同时有 𝑥<𝑦 和 𝑦<𝑥,无法放进全序。
  • 把线性扩展和线性化混为一谈:线性化是选取或使用线性扩展的过程。
  • 认为无限偏序集也能直接反复取极小元:无限情形需要 Szpilrajn 扩展定理,通常依赖选择公理。
  • 把“线性扩展”写成“线性拓展”:标准术语是线性扩展,线性扩张也可。
源码位置