查看“︁链”︁的源代码

[[分类:序理论]]{{DEFAULTSORT:lian4}}
{{#seo:
|keywords=链, 偏序集, 偏序集的高度
|description=本文介绍序理论中链的概念、定义和性质，包括链的长度和偏序集的高度，以及链相关的定理。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-02-28
}}
{{InfoBox
|name=链
|eng_name=chain
}}
{{InfoBox
|name=长度
|eng_name=length
}}
{{InfoBox
|name=高度
|eng_name=height
}}
'''链'''('''chain''')指[[偏序集]]中的[[全序]]子集，表现为其 [[Hasse 图]]中一条纵向的路径。
其中的元素个数称为其'''长度'''('''length''')，也有人使用链上的边数，即元素个数减一。
偏序集的最大链元素个数称为偏序集的'''高度'''('''height''')，也有人使用元素个数减一。

'''链'''也用于指全序本身，参见[[全序]]。

== 定义 ==

对偏序集 <math>(P,\preceq)</math> 及其子集 <math>C\subseteq P</math> ，若 <math>(\forall x, y \in C)(x \preceq y \lor y \preceq x)</math> ，即 <math>\preceq|_C</math> 是 <math>C</math> 上的一个全序，则称 <math>C</math> 是偏序集中的一个'''链'''('''chain''')。
称链中元素的个数，即 <math>\operatorname{card}C</math> 为链 <math>C</math> 的'''长度'''('''length''')。

偏序集 <math>(P,\preceq)</math> 的全部链中的最大长度（即最大元素个数）称为偏序集 <math>(P,\preceq)</math> 的'''高度'''('''height''')。

== 性质 ==

* 链是偏序集的全序子集，任意两个元素都可以比较。
** 空集视为空链。
** 单元素集一定是链，是平凡链。
* 运算性质
** 链的[[子集]]仍是链
** 链的[[交集]]仍是链
* 与[[反链]]概念定义正相对
* 相关定理
** [[Mirsky 定理]]：偏序集的最小反链划分等于最大链的大小
** [[Dilworth 定理]]（偏序集分解定理）：偏序集的最小链划分等于最大反链的大小


{{序理论}}