关于与“
反链”标题相近或相同的条目,请见“
反向链接”。
此条目没有列出任何参考或来源。 (2012年5月18日) 维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而移除。 |
在序理论中,设A是一个偏序集,B为A的一个子集,若B中任意两个元素无法相互比较(comparable),则称B是一条反链(Antichain)。为了方便,通常还规定偏序集中的所有单元素子集既是链也是反链。
用形式化语言表述就是:
设是一个偏序集,是的子集,则B是A上的反链等价于
相关结论
直观地说,一条反链实际上确定了一个偏序集上互相无法比较的若干条链。容易看出,全序集上反链的最大长度是1。运用链和反链的概念可以证明如下定理,它刻画了偏序关系与集合划分之间的关系:
设 是一个偏序集,设A中链的最大长度为n,则A中存在一个由n个反链组成的划分。