偏序集上的组合学中的几个问题的任务书.docx

该【偏序集上的组合学中的几个问题的任务书 】是由【niuwk】上传分享，文档一共【2】页，该文档可以免费在线阅读，需要了解更多关于【偏序集上的组合学中的几个问题的任务书 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。偏序集上的组合学中的几个问题的任务书任务:阅读并分析偏序集上组合学中的三个问题,并给出解决这些问题的思路和方法。问题一:最长反链问题定义:在偏序集P=(S,≤)中,一个反链是指其中任意两个元素之间都不满足≤关系的子集。反链的长度指该反链元素个数的最大值。问题:求出偏序集P中最长反链的长度。思路:构造一个算法,利用贪心策略不断地将偏序集中一些可比的元素删去,直到剩下的元素中不再存在可比关系。根据传递性,从剩下的元素中任选一个元素,所有与其不可比的元素组成的集合即为反链。此时,反链的长度为集合大小。问题二:杨表计数问题定义:在偏序集P=(S,≤)中,一个杨表是指将P的元素按行列分布在一个矩阵中,使得每行和每列上的元素满足≤关系,且每行和每列上的元素都不重复的矩阵。问题:求出所有可能的大小为n的杨表数目。思路:从左上角开始逐行填充杨表,对于每个空格枚举可填充元素的种类,即所有满足≤关系且未被占用的元素。可用回溯算法实现。问题三:Dilworth定理定义:在偏序集P=(S,≤)中,一个链划分指将P划分成若干个链的集合。其中最小链划分指将P划分成最少个数的链的集合。Dilworth定理:偏序集P的最小链划分个数等于P的最长反链长度。问题:证明Dilworth定理。思路:对于任意一个偏序集P,构造一个令P子集之间存在≤关系的偏序集Q。证明偏序集P的最小链划分个数等价于偏序集Q的最长链长度。通过对偏序集Q进行证明,得到Dilworth定理成立的证明。