首页 > 其他分享 >序理论

序理论

时间:2024-08-20 10:17:07浏览次数:8  
标签:偏序 理论 aRb 二元关系 集合 传递性 forall

在 \(sort\) 的时候, 我们的 \(cmp\)函数应该满足 \(<\)

可什么是小于 它需要满足什么性质才能等价于小于?

序理论给出了严格的定义

二元关系

集合\(X\)和集合\(Y\)上的一个二元关系, \(G(R) \subseteq X \times Y = \{ (x,y); x \in X, y \in Y \}\)

\(xRy\) 成立当且仅当 \((x,y) \in G(R)\)

例如 \(N_+\) 上的整除 与 小于等于都是二元关系

性质

  • 自反性 \(\forall a \in S, aRa\)

  • 反自反性 \(\forall a \in S, \neg (aRb)\)

  • 对称性 \(\forall a, b \in S, (aRb) \Longleftrightarrow (bRa)\)

  • 反对称性 \(\forall a, b \in S, (aRb \wedge bRa) \Longrightarrow a = b\)

  • 非对称性 \(\forall a, b \in S, (aRb) \Longrightarrow \neg (bRa)\)

  • 传递性 \(\forall a, b, c \in S, (aRb \wedge bRc) \Longrightarrow aRc\)

  • 连接性 \(\forall a, b \in S, a \ne b \Longrightarrow (aRb \vee bRa)\)

  • 不可比的传递性 \(\forall a,b,c \in S, (\neg (aRb \vee bRa) \wedge \neg (bRc \vee cRb)) \Longrightarrow \neg(aRc \vee cRa)\)

这就是它所有的定义

等价关系

满足自反性, 对称性, 传递性

例子:

  • =

  • 有集合\(S\), 这是集合 \(S\)的一种划分 $S = \sqcup_{\alpha \in I}S_{\alpha} $

\(\{ (a,b) \in S \times S;a,b \in S_{\alpha},\alpha \in I \}\)

  • 有线性空间 \(L\) , \(V\) 是 \(L\)的一个线性子空间

\(\{ (a,b) \in L \times L; a + V = b + V\}\)

等价关系与集合的划分

如果把一个二元关系理解成为一条边 那么它形成的图就是多个无向子图

所以我们可以把每一个无向子图看成一个等价类 于是这个就形成了一个原集合的一种划分!

也就是说一个等价关系会诱导形成一个集合的划分

一个集合的划分也会诱导形成一个等价关系

全序

满足自反性, 反对称性, 传递性, 连接性

例子

  • \(\le\)

  • 一条链

若 \(a\) 可以到达 \(b\), 则\(aRb\)成立

偏序

满足自反性, 反对称性, 传递性

例子:

  • 一个 \(DAG\)

若 \(a\) 可以到达 \(b\), 则\(aRb\)成立

偏序集

若集合 \(S\) 上的一个二元关系 \(\preceq\) 具有 自反性、反对称性、传递性,则称 \(S\) 是 偏序集,\(\preceq\) 为其上一偏序。

链与反链

链就是偏序集的全序子集

若 \(S\) 的子集 \(T\) 中任意两个不同元素均不可比,(即 \((\forall~a,b \in T)~~a \neq b \implies (a \npreceq b \land b \npreceq a)\)),则称 \(T\) 为反链

Dilworth定理

最长反链长度等于最小的链覆盖数

同理也有 \(S\) 的最长链长度等于最小的反链覆盖数

证明

咕咕咕

例题

  • 导弹拦截

  • 组合数学

咕咕咕

严格弱序

满足反自反性 非对称性 传递性 不可比的传递性

这个是C++ STL里面要求排序的二元关系

例子

  • <

严格弱序与贪心

在一种贪心题目中 我们通常需要确定一种排列 让他最优

我们通常会使用一种方法是考虑相邻交换满足什么条件的时候是不用交换的 然后以这个条件作为二元关系 进行 \(sort\) 排序

容易证明这样是对的 因为考虑 \(i\) 和 \(j (i < j)\) 交换会不会更优我们考虑每次交换相邻的 然后每次交换都是不优的, 所以排完序后就是最优的

但是 这里有一个非常重要的点就是它必须满足严格弱序

例题

  • 国王游戏

  • 皇后游戏

咕咕咕

标签:偏序,理论,aRb,二元关系,集合,传递性,forall
From: https://www.cnblogs.com/aqz180321/p/18368920

相关文章

  • AUTOSAR&UDS 理论要点及isolar实战-22服务讲解及配置实战(2)
    1.读取数据22服务此部分和22服务讲解及配置实战(1)中保持一致,有需要的小伙伴前往上一博客查看。2.配置实战2.1DcmDsdServiceTables的配置1.DcmDsdSidTabFnc:工具自带的回调函数,调用静态代码包中的服务函数2.DcmDsdSidTabServiceId为0x22,配置22服务;3.DcmDsdSidTabSub......
  • 何谓相等 (Equality),在类型理论(Type Theory)语境下
    两个元素a,b相等,即a=b,就是a和b是被完全一样地构建出来的。在《类型(Type)是可构建集合(constructiveset)》 一文中,说到,类型中的每个元素都是可构建的,因此,如果在一个类型中的两个元素a,b,是通过一样的方式构建出来,包括其构建时的输入,构建函数,那么,就说a等于b,a=b。......
  • 算法刷题记录 八十五【图论的广度优先搜索理论基础】
    前言图论章节第2篇。第1篇:记录八十二【图论理论基础及深度优先搜索算法】;本文:记录八十五【图论的广度优先搜索理论基础】一、广度优先搜索理论基础广度优先搜索理论基础参考链接1.1知识点框架1.2模拟广度搜索的过程在有向图中,以下图为例,如何进行广度优先搜索......
  • 理论 - 向量对向量的投影公式的简单推导
    https://www.bilibili.com/read/cv22449403/https://www.cnblogs.com/graphics/archive/2010/08/03/1791626.html 下面是对此公式的简单推导:如下图所示,可以知道投影向量 A(projected)的方向和 B的方向相同,长度是 |A|·cosθ所以有:A(projected) =B(normalize......
  • 热力学平衡、Liftshitz 理论和朗道理论
    科学家们经过广泛的实验发现:熔化往往始于固体表面。熔化时,体系由“固体-气体接触”变为"固体-熔化层接触+熔化层-气体接触“。如果后者的能量更稳定,则说明熔化的确更容易在表面发生。将这一结论推广到温度低于熔点的情况即可在热力学平衡角度解释预熔现象。下面简要考察这一......
  • 理论 - 向量的叉乘、点乘
    https://zhuanlan.zhihu.com/p/672847151  (点乘的结果,也可以理解为向量A在B上的投影,再乘上向量B的模长,即模长的叠加) (由点乘的几何意义,我们可以知道,如果要计算向量A在向量B的投影模长,只需要先对这两向量进行点乘操作,然后除以向量B的模长即可) (叉乘的结果,也可......
  • 【通信理论知识】数据传送的方式:串/并行;传输方向:单工、半/全双工;传输方式:同步/异步
    串行/并行通信按数据传送的方式,通讯可分为串行通讯与并行通讯。串行通讯就像单个车道的公路,同一时刻只能传输一个数据位的数据。并行通讯就像多个车道的公路,可以同时传输多个数据位的数据。传输方向(单工、半/全双工)全双工和半双工通信的本质区别(SPI、IIC)半双工......
  • 区块链技术的基本理论
    本文分享自天翼云开发者社区《区块链技术的基本理论》,作者:z****n2008年10月31日,“中本聪”首次提出数字加密货币的概念。2009年,第一枚加密数字货币——比特币诞生。区块链技术作为比特币的核心技术,凭借去中心化、公开透明、不可篡改的特点受到国内外各界人士的高度关注,将其应用于......
  • 【代码随想录】二、链表:理论基础
    原文链接:代码随想录-链表理论基础。1.什么是链表?链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。链表的入口节点称为链表的头结点也就是head。2.链表的类型2.1.......
  • 【数据结构】关于树(二叉树)的基础理论知识,你知道吗???
    前言:......