首页 > 其他分享 >浅谈偏序

浅谈偏序

时间:2024-08-15 23:08:25浏览次数:8  
标签:偏序 le 浅谈 定理 极大元 集合 反链

目录

偏序和等价关系

关系:设 \(X\) 是一个集合,\(X\) 上的关系是 \(X\) 的元素的有序对集合 \(X\times X\) 的子集 \(R\)。我们把属于 \(R\) 的有序对 \((a,b)\) 写作 \(aRb\)。把不属于 \(R\) 的有序对 \((a,b)\) 写作 \(a\not R b\)。

集合 \(X\) 上的关系 \(R\) 可能具有的一些特性:

  • 如果对于 \(X\) 中所有的 \(x\),都有 \(xRx\),则称 \(R\) 是自反的。
  • 如果对于 \(X\) 中所有的 \(x\),都有 \(x\not Rx\),则称 \(R\) 是反对称的。
  • 如果对于 \(X\) 中所有的 \(x\),只要 \(xRy\) 就有 \(yRx\),则称 \(R\) 是对称的。
  • 如果对于 \(X\) 中所有的 \(x\),只要 \(xRy\) 就有 \(y\not Rx\),则称 \(R\) 是反对称的。
  • 对于 \(X\) 中的 \(x,y,z\),只要 \(xRy,yRz\),就有 \(xRz\),则称 \(R\) 是传递的。

偏序、偏序集:集合 \(X\) 上的偏序是一个自反、反对称且传递的关系,集合 \(X\) 上的严格偏序是一个反自反、反对称且传递的关系。因此 \(\subseteq,\le,\mid\) 均是偏序,而 \(\subset,<\) 均是严格偏序。在其上定义了偏序 \(\le\) 的集合 \(X\) 也叫做偏序集,记作 \((X,\le)\)。

若 \(xRy\) 或 \(yRx\),则说 \(x\) 和 \(y\) 是可比的,否则不可比。若 \(X\) 的每一对元素都是可比的,则集合 \(X\) 上的偏序 \(R\) 是全序。比如数集上标准的 \(\le\) 是一个全序。

设 \((X,\le)\) 是全序,则存在 \(X\) 的一个排列 \(\{a_1,a_2,\dots,a_n\}\),使得若 \(i,j\) 则 \(a_i\le a_j\)。

如果 \(a<b\) 并且没有元素 \(c\) 能够夹在 \(a\) 和 \(b\) 之间,那么称 \(a\) 被 \(b\) 覆盖 。

反链是 \(X\) 的一个子集 \(A\),使得它的任意两个元素都不可比,链是 \(X\) 的一个子集 \(A\),使得它的任意两个元素都可比,因此链是 \(X\) 的一个全序子集。显然反链和链的交集大小小于等于 \(1\)。

若 \(X\) 存在大小为 \(r\) 的反链 \(C\),则\(X\) 的链划分数大于等于 \(r\)。

将 \((X,\le)\) 放在图上,得到图 \((V,E)\),显然 \((V,E)\) 是一个 DAG,称一个 偏序集的极小元为所有放在 DAG 上的入度为\(0\) 的元素集合,极大元为所有放在 DAG 上的出度为\(0\) 的元素集合。

Dilworth 定理

先说 Dilworth 定理的对偶定理。

定理 1

设 \((X,\le)\) 是有限偏序集,而 \(r\) 是链的最大大小,则 \(X\) 可以被划分成 \(r\) 个反链,但不能划分成少于 \(r\) 个反链。

证明:显然不能划分成少于 \(r\) 个反链,只需证明有划分成 \(r\) 个反链的构造即可,显然 \(X\) 的极小元是一个反链,然后将其从 \(X\) 中删去,重复操作即可,恰好划分为 \(r\) 个反链。

定理 2(Dilworth 定理)

设 \((X,\le)\) 是有限偏序集,而 \(r\) 是反链的最大大小,则 \(X\) 可以被划分成 \(r\) 个链,但不能划分成少于 \(r\) 个链。

证明:设 \(|X|=m\)。当 \(|X|=1\) 时定理成立。

当 \((X,\le)\) 存在一个大小为 \(m\) 的反链 \(A\),满足 \(A\) 既不是 \(X\) 的极小元集合,也不是 \(X\) 的极大元集合,设 \(A^{+}\) 表示所有属于 \(X\) 且满足 \(a\le x,a\in A\) 的元素集合、\(A^{-}\) 表示所有属于 \(X\) 且满足 \(x\le a,a\in A\) 的元素集合。有 \(A^{+}\cap A^{-}=A\),\(A^{+}\cup A^{-}=X\),然后将 \(A^{+},A^{-}\)递归归纳到下面一种情况中,然后将两个集合的解拼在一起即可。

当 \((X,\le)\) 不存在一个大小为 \(m\) 的反链 \(A\),满足 \(A\) 既不是 \(X\) 的极小元集合,也不是 \(X\) 的极大元集合,显然此时长度为 \(m\) 的反链为极小元或极大元。若极小元为长度为 \(m\) 的反链,则在DAG 上极小元指出的点的入度大于 \(1\),此时随便选择属于极小元的元素 \(x\) 和属于极大元的元素 \(y\),则 \(X-\{x,y\}\) 的反链长最大为 \(m-1\),继续递归归纳即可,反链为极大元同理。

标签:偏序,le,浅谈,定理,极大元,集合,反链
From: https://www.cnblogs.com/fzrcy/p/18362013

相关文章

  • 【待做】【WEB安全】浅谈JSONP劫持漏洞
    一、JSONP二、JSONP劫持示例三、JSONP劫持绕过方法3.1Referer过滤(常规)不严格3.2空引用绕过3.3回调可以定义引起的安全问题3.4测试HTML代码四、JSONP修复JSONPJSONP的全称是JSONwithPadding,是一种基于JSON格式来解决跨域请求资源的方案。由于......
  • 浅谈网站更新的频率对SEO的影响
    由于没有企业可以专门耗费时刻天天对网站内容举办更新,以是停止不了有的时辰健忘更新网站的内容。对付这个题目,网站也不知道怎么举办,出格是对付一个SEO博客来说,有的时辰真的不知道该去写什么样的文章。并且写的文章越到最后越没有代价,对于了事凑字数。可是这个更新多几几何会有一些......
  • [OI] 偏序
    \(n\)维偏序即给出若干个点对\((a_{i},b_{i},\cdots,n_{i})\),对每个\(i\)求出满足\(a_{j}\gta_{i},b_{j}\gtb_{i}\cdots,n_{j}\gtn_{i}\)的\(j\)的个数一维偏序直接用权值线段树或者树状数组.或者你直接离散化开桶前缀和.二维偏序考虑到先对全部点对按\(a_{i}\)......
  • 浅谈前端研发链路之构建
    前言我们每天都在说构建构建,你真的了解前端构建吗?文末有我在前端面试多年的经验文章!!!在现代前端开发中,构建过程扮演着至关重要的角色。随着Web应用变得越来越复杂,直接编写原生HTML、CSS和JavaScript已经不能满足开发需求,我们需要工程化的体系去构建前端应用。构建过......
  • 浅谈rabbitmq 死信队列与延迟队列
    目录一、死信队列1、介绍2、死信的三种情况3、队列如何绑定DLX(死信交换机)二、延迟队列一、死信队列1、介绍死信队列,英文缩写:DLX。DeadLetterExchange(死信交换机),其实应该叫做死信交换机才更恰当。当消息成为Deadmessage后,可以被重新发送到另一个交换机,这个交换机就是DLX。......
  • 浅谈AEB的安全设计与技术进化
    浅谈AEB的安全设计与技术进化一、AEB的功能安全需求从HARA角度进行AEB的功能安全分析,可以得出共识性最高的2个安全目标内容描述:非预期的制动过大和非预期的不可释放制动。随着下一步安全目标内容的分解,可以得出:1. 非预期的制动过大(含误触发)的争论点:包括了非预期的AEB触......
  • 浅谈矩阵
    0.前言感谢远古神猴tz1带来的30分钟极速版矩阵乘法讲解,tql!1.矩阵作用矩阵本质是对一个向量的进行变换,也就是描述转移的东西,因此我们常常用其来加速转移过程。2.技巧让我们来结合几道题目来谈谈吧。2.1优化矩阵运算[CF1970E3]Trails首先,暴力矩阵转移是显然的,记\(p_i=l......
  • 【CDQ分治】【模板】三维偏序(陌上花开)
    P3810【模板】三维偏序(陌上花开)-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;template<typenameT>structBIT{#ifndeflowbit#definelowbit(x)(x&(-x));#endifintn;vector<T&......
  • 模拟实现 memcpy --浅谈C语言
    内存拷贝-memcpy描述C库函数void*memcpy(void*str1,constvoid*str2,size_tn)从存储区str2复制n个字节到存储区str1。memcpy是最快的内存到内存复制子程序。它通常比必须扫描其所复制数据的strcpy,或必须预防以处理重叠输入的memmove更高效。memcpy,memcpy......
  • 模拟实现 strcat(字符串追加) --浅谈C语言
    strcat描述char*strcat(char*dest,constchar*src)把src所指向的字符串追加到dest所指向的字符串的结尾。声明下面是strcat()函数的声明。char*strcat(char*dest,constchar*src)参数dest--指向目标数组,该数组包含了一个C字符串,且足够容纳追加后的字符......