• 产品中心
公告 文档 控制台
登录 免费注册
  • 账户信息
  • 退出账号
    • 意见箱
    恒创运营部门将仔细参阅您的意见和建议，必要时将通过预留邮箱与您保持联络。感谢您的支持！
    意见/建议
    提交建议

    组合学笔记(一)偏序集概念与应用

    来源：恒创科技 编辑：恒创科技编辑部
    2022-08-26 14:16:54


    tags: Combinatorics写在前面

    最近看论文需要用到偏序集的有关概念, 在这里先梳理一下, 方便以后的使用. 主要参考的书籍是Stanley的经典名著《计数组合学(第一卷)》.

    下面若不特别指明, 均用代表偏序集.


    组合学笔记(一)偏序集概念与应用

    定义

    偏序集(partially-ordered set, poset)是一个集合, 连同一个记为()的二元关系, 满足下面的三条公理:

    对所有的,(自反性).如果且, 则(反对称性).如果且, 则(传递性).偏序集中的两个元素可比, 如果或者, 否则称其为不可比的.偏序集同构:
    之间存在一个保持序关系的双射使得他的逆也保持序关系. 即:
    弱子偏序集: 偏序集的子集连同上满足"如果在中有, 则在中"的偏序关系, 则为的弱子偏序集.加细: 若是的弱子偏序集, 且作为集合有, 则称是的加细.诱导子偏序集:的子集连同上的偏序关系:“, 在中有在中有”.诱导序:是的诱导子偏序集, 则具有诱导序. 有限偏序集恰好有个诱导子偏序集.局部有限偏序集: 偏序集的任一区间都是有限的. (可完全由其覆盖关系所确定)凸子偏序集: 若在偏序集中有且, 就有, 此时区间也是凸的.
    覆盖: 设, 若且不存在使得. 充要条件:且.(有限偏序集的)Hasse图: 顶点为中元素, 边为覆盖关系, 并且若则绘制在"上面"的图形.
    Hasse图的一些例子, 可以参考我的前面的博客. 含有四个元素的偏序集有16个, Hasse图如下图所示

    组合学笔记(一)偏序集概念与应用_算法_64

    偏序集具有: 若存在某个元素使得对所有的都有.偏序集具有: 若存在某个元素使得对所有的都有.: 表示在中加入得到的偏序集(不管本身是否含有和).
    若, 那么的上界为满足的元素.的最小上界为的上界, 使得对的每一个上界, 都有.若最小上界存在, 则唯一, 记为, 同理, 最大下界记为.格(lattice): 是一个偏序集, 其中每一对元素的最小上界和最大下界都存在.格满足的一些性质:
    链(chain, 全序集,线性序集)指任意两个元素都可以比较大小的偏序集. 例如及其上的普通序关系, 记为.偏序集的子集为链, 若 作为的子偏序集的时候是链.偏序集中的链为饱和的(不可加细的), 如果不存在使得对于中某两个元素有, 并且仍然构成链. (有点像上确界的定义, 没办法再塞进去一个元素)局部有限偏序集中的链是饱和的, 对有覆盖.有限链的长度.有限偏序集的长度(秩)定义为.偏序集的区间的长度记为.秩为的分次偏序集: 若偏序集的所有极大链都具有相同长度. 此时存在唯一秩函数, 满足:若是的极小元, 则;若在中有覆盖, 则.如果, 称元素具有秩.偏序集的秩生成函数: 对秩为的分次偏序集, 其中有个元素的秩为, 则的秩生成函数为:
    偏序集的可重链: 具有重复元素的链, 即基集为的某个链的可重集合.反链(Sperner族, 集群): 偏序集的子集, 其中任意两个不同元素不可比较.序理想的序理想(半理想, 下集, 下降子集): 满足下列条件的的子集. (有点像左开右闭区间)
    对偶序理想(滤子): 满足下列条件的的子集. (有点像左闭右开区间)
    偏序集有限时, 的反链和序理想之间存在一一对应.
    也就是说, 为的极大元构成的集合, 而
    偏序集的所有序理想按照包含关系排序, 构成一个偏序集, 记为.生成: 若序理想和极大元所成集合之间满足式. 若, 记为由生成的序理想.主序理想: 序理想为由生成的主序理想, 记为.主对偶序理想:表示由生成的主对偶序理想.偏序集上的运算直和(不交并): 即定义在上的偏序集, 记为, 指两不相交集合上定义的偏序集, 使得在中有.即在中, 或者有, 或者有.若一个偏序集不是两个非空偏序集的不交并, 这称之为连通的. 和自身的次不交并记为.一个元反链同构于.有序和: 即定义在上的偏序集记为, 使得在中.即在中, 或者有, 或者有, 或者有.一条元链由给出.串并联偏序集: 在个四元偏序集中, 恰有一个是不能由偏序集通过直和运算与有序和运算构造出来.

    这个偏序集为上图中的第二行的最后一个, 显然他不能够通过直和以及有序和运算生成.

    直积(笛卡尔积): 定义在集合上的偏序集, 满足在中有.即, .和它自身的次直积记为..如果是分次的且秩生成函数为和, 则也是分次的且:
    有序积:, 定义在上, 满足, 若且, 或.如果是分次的并且的秩为, 则对于有序积, 有
    对偶: 记为, 是与定义在同一集合上的偏序集, 但在中.自对偶:.
    下面是所有含四个元素的偏序集中的自对偶图这里是所有含有四个元素的偏序集中的非自对偶偏序集, 共有8个, 显然这些偏序集的对偶都是成对出现的
    格(lattice)

    格是这样一类偏序集: 其中每一对元素的最小上界和最大下界都存在的偏序集.

    子集格

    , 的所有子集的集合构成偏序集, 称为子集格.

    因子格

    ,(为正整数) 定义, 若可以被整除, 记为, 的所有正整数因子以"自然的"方式成为一个偏序集.


    本文地址：https://www.henghost.com/jishu/5823/
    上一篇： 租用美国服务器：潜在的风险与应对策略。 下一篇： 企业网站为什么托管服务器
    相关文章
    查看更多
    [2024-05-08] python算法(python算法库有哪...
    [2024-05-06] Linux中的IO调度算法有哪些
    [2024-04-29] C语言浮点数压缩算法如何实现
    [2024-04-29] C语言浮点数在机器学习算法中有什么作用
    [2024-04-29] C语言浮点数的排序算法怎么实现
    [2024-04-29] C#字符串模糊匹配算法怎么实现
    [2024-04-29] C#中的字符串反转算法如何实现
    [2024-04-28] 分析C语言中处理回文问题时的算法复杂度

    热门文章

    热门活动

    热门标签 查看详情