精华内容
下载资源
问答
  • 这是一个从文件读入一个关系R的矩阵表示,然后计算他的偏序关系矩阵 和最小偏序关系矩阵,最后由最小偏序矩阵画出哈斯图的程序。
  • 一、哈斯图示例 ( 整除关系 ) 、 二、哈斯图示例 ( 包含关系 ) 、 三、哈斯图示例 ( 加细关系 ) 、





    一、哈斯图示例 ( 整除关系 )



    集合 A = { 1 , 2 , 3 , 4 , 5 , 6 , 9 , 10 , 15 } A = \{ 1, 2, 3, 4, 5, 6, 9, 10, 15 \} A={1,2,3,4,5,6,9,10,15} ,

    集合 A A A 上的整除关系 “ ∣ | ” 是偏序关系 ,

    偏序集是 < A , ∣ > <A, |> <A,>

    x x x 整除 y y y , x x x 是除数 (分母) , y y y 是被除数 (分子) ; y x \dfrac{y}{x} xy
    y y y 能被 x x x 整除 , x x x 是除数 (分母) , y y y 是被除数 (分子) ; y x \dfrac{y}{x} xy


    绘制上述偏序集的哈斯图 :

    在这里插入图片描述


    1 1 1 是最小的 , 1 1 1 能整除所有的数 ;

    1 1 1 上面的一层是素数 , 素数只能被 1 1 1 和其本身整除 ; 素数肯定是覆盖 1 1 1 的 ; 即素数与 1 1 1 之间没有元素 ;


    素数之上的数 , 由素数相乘的数组成 ;

    6 6 6 既可以整除 2 2 2 , 又可以整除 3 3 3 , 因此其既覆盖 2 2 2 , 又覆盖 3 3 3 ;

    10 10 10 既可以整除 2 2 2 , 又可以整除 5 5 5 , 因此其既覆盖 2 2 2 , 又覆盖 5 5 5 ;

    15 15 15 既可以整除 3 3 3 , 又可以整除 5 5 5 , 因此其既覆盖 3 3 3 , 又覆盖 5 5 5 ;

    4 4 4 可以整除 2 2 2 , 因此 4 4 4 覆盖 2 2 2 ;

    9 9 9 可以整除 3 3 3 , 因此 9 9 9 覆盖 3 3 3 ;





    二、哈斯图示例 ( 包含关系 )



    集合 A = { a , b , c } A = \{ a, b , c \} A={a,b,c} ,

    集族 A \mathscr{A} A 包含于 A A A 集合的幂集 , A ⊆ P ( A ) \mathscr{A} \subseteq P(A) AP(A) ,

    集族 A = { ∅ , { a } , { b } , { c } , { a , b } , { b , c } , { a , c } } \mathscr{A} = \{ \varnothing , \{ a \} , \{ b \} , \{ c \} , \{ a , b \} , \{ b,c \} , \{ a, c \} \} A={,{a},{b},{c},{a,b},{b,c},{a,c}}

    集族 A \mathscr{A} A 上的 包含关系 “ ⊆ \subseteq ” 是偏序关系 ,

    偏序集是 < A , ⊆ > <\mathscr{A} , \subseteq > <A,>

    在这里插入图片描述

    空集 包含于 所有集合 , 是最小的 , 在哈斯图最下面 ;

    空集 之上是单元集 , 单元集 覆盖 空集 , 它们之间并不会有第三个元素 ;

    三个单元集之间相互没有包含关系 , 是不可比的 ;

    单元集 之上是 双元集 , 每个 双元集 之下就是其包含的对应的单元集 ;





    三、哈斯图示例 ( 加细关系 )



    加细关系 是 有序对集合 , 其中每个 有序对的元素 是 集族 ;


    集合 A A A 非空 , π \pi π A A A 集合划分组成的集合 , 每个划分都是一个集族 ;

    划分参考 : 【集合论】划分 ( 划分 | 划分示例 | 划分与等价关系 )

    集族之间有一种关系 , 加细关系 , 使用符号 ≼ 加 细 \preccurlyeq_{加细} 表示 ;

    加细关系 ≼ 加 细 \preccurlyeq_{加细} 符号化表示 :

    ≼ 加 细 = { < x , y > ∣ x , y ∈ π ∧ x 是 y 的 加 细 } \preccurlyeq_{加细} = \{ <x, y> | x, y \in \pi \land x 是 y 的加细 \} ={<x,y>x,yπxy}


    前提 :

    • 集合 A = { a , b , c , d } A = \{ a, b , c , d \} A={a,b,c,d}

    • 集族 A 1 = { { a } , { b } , { c } , { d } } \mathscr{A}_1= \{ \{ a \} , \{ b \} , \{ c \} , \{ d \} \} A1={{a},{b},{c},{d}}

    • 集族 A 2 = { { a , b } , { c , d } } \mathscr{A}_2 = \{ \{ a , b \} , \{ c , d \} \} A2={{a,b},{c,d}}

    • 集族 A 3 = { { a , c } , { b , d } } \mathscr{A}_3= \{ \{ a,c \} , \{ b,d\} \} A3={{a,c},{b,d}}

    • 集族 A 4 = { { a } , { b , c , d } } \mathscr{A}_4= \{ \{ a \} , \{ b, c , d \} \} A4={{a},{b,c,d}}

    • 集族 A 5 = { { a } , { b } , { c , d } } \mathscr{A}_5= \{ \{ a \} , \{ b \} , \{ c , d \} \} A5={{a},{b},{c,d}}

    • 集族 A 6 = { { a , b , c , d } } \mathscr{A}_6 = \{ \{ a , b , c , d\} \} A6={{a,b,c,d}}

    上述集族都是 A A A 集合的划分 ;


    划分关系的哈斯图 :

    在这里插入图片描述

    A 1 \mathscr{A}_1 A1 是所有划分的加细 , 是最细的划分 , 在哈斯图最下面 ;

    所有的划分都是 A 6 \mathscr{A}_6 A6 的加细 , 是最粗粒度的划分, 在哈斯图最上面 ;

    A 5 \mathscr{A}_5 A5 既是 A 2 \mathscr{A}_2 A2 的加细 , 又是 A 4 \mathscr{A}_4 A4 的加细 ;

    A 3 \mathscr{A}_3 A3 A 4 \mathscr{A}_4 A4 互相不是对方的加细 , 不可比 ;

    A 2 \mathscr{A}_2 A2 A 4 \mathscr{A}_4 A4 互相不是对方的加细 , 不可比 ;

    A 2 \mathscr{A}_2 A2 A 3 \mathscr{A}_3 A3 互相不是对方的加细 , 不可比 ;

    A 3 \mathscr{A}_3 A3 A 5 \mathscr{A}_5 A5 互相不是对方的加细 , 不可比 ;

    展开全文
  • 绘制哈斯图(可画出图片),等价矩阵,计算等价类
  • c语言代码 txt文本 数据结构的c语言课程设计的习题 从从偏序关系中导出哈斯图并层次遍历图
  • MFC做的等价闭包,等价类和哈斯图的实现
  • 【离散】画哈斯图--最好理解绝不会出错

    万次阅读 多人点赞 2020-05-19 08:50:48
    离散数学哈斯图的画法 两个步骤:(1)排点的层数 (2)把有关系的点连接起来 看一道题: 设A={1,2,3,4,6,8,9},偏序集S={A,《},其中《为整除关系,画出S的哈斯图 首先把他们的所有的关系列出来 <1,2>...

    离散数学哈斯图的画法

    两个步骤:(1)排点的层数 (2)把有关系的点连接起来

    看一道题:

    设A={1,2,3,4,6,8,9},偏序集S={A,《},其中《为整除关系,画出S的哈斯图

    首先把他们的所有的关系列出来(后面的数可以整除前面的数,这两个数就有整除的关系)

    <1,2> <1,3> <1,4> <1,6> <1,8> <1,9>

    <2,4> <2,6> <2,8>

    < 3,6> < 3,9>

    <4,8>

    然后来排点的层数。

    首先看,所有关系里面不在值域的元素有哪几个:在这里是1.所以我们把1放到第一层

    在这里插入图片描述

    然后我们删掉<1,x>的所有元素(就不看那些元素)

    <1,2> <1,3> <1,4> <1,6> <1,8> <1,9>

    <2,4> <2,6> <2,8>

    < 3,6> < 3,9>

    <4,8>

    继续找(没被加入哈斯图的)不出现在值域的元素,我们找到了2,3,那么把2,3放在第二排.
    在这里插入图片描述同样删除<2,x>和<3,x>的所有元素

    <1,2> <1,3> <1,4> <1,6> <1,8> <1,9>

    <2,4> <2,6> <2,8>

    < 3,6> < 3,9>

    <4,8>

    这时不出现在值域且没被加入哈斯图的元素有4,6,9。那么把4,6,9放到第三排。
    在这里插入图片描述

    最后还剩下8,那么把8放在第四排。
    在这里插入图片描述

    现在我们点的排序就排好了。

    最后把每一层之间有关系的点连起来就好了。⚠️注意,这里每一层只会和上一层相连,不会跨两层连。
    在这里插入图片描述
    有帮助的话就给我点个赞吧!
    5个赞更新极大极小元。

    更新一下极大极小元:
    极小元就是 没有元素比它小
    如果有的关系只有它自己 那么也是极小的 那也是极小元
    极大元同理 :)


    楼主最近在准备保研 要复习专业课内容

    大家如果有什么想看的科目也可以评论我 (毕竟我都会复习到)

    展开全文
  • 一、偏序关系、 二、偏序集、 三、可比、 ...六、哈斯图、 七、全序关系 ( 线序关系 )、 八、拟序关系、 九、拟序关系相关定理、 十、偏序关系八种特殊元素、 十一、链、 十二、反链、 十三、链与反链示例、



    参考博客 :





    一、偏序关系



    偏序关系 :

    给定非空集合 A A A , A ≠ ∅ A \not= \varnothing A= , R R R 关系是 A A A 集合上的二元关系 , R ⊆ A × A R \subseteq A \times A RA×A ,
    如果 R R R 关系满足以下性质 :

    • 自反 : 关系图中所有顶点 都有环 ;
    • 反对称 : 两个顶点之间 有 0 0 0 个或 1 1 1 个有向边 ;
    • 传递 : 前提 a → b , b → c a \to b , b\to c ab,bc 不成立 默认传递 ; 前提 a → b , b → c a \to b , b\to c ab,bc 成立 必须满足 a → c a \to c ac 存在 ;

    则称 R R R 关系是 A A A 集合上的 偏序关系 ;

    偏序关系表示 : 使用 ≼ \preccurlyeq 符号表示偏序关系 , 读作 “小于等于” ;

    符号化表示 : < x , y > ∈ R ⇔ x R y ⇔ x ≼ y <x,y> \in R \Leftrightarrow xRy \Leftrightarrow x \preccurlyeq y <x,y>RxRyxy , 解读 : < x , y > <x,y> <x,y> 有序对在偏序关系 R R R 中 , 则 x x x y y y 之间有 R R R 关系 , x x x 小于等于 y y y ;


    等价关系 是用于 分类 的 , 偏序关系 是用于 组织 的 , 在每个类的内部 , 赋予一个结构 ;


    参考博客 : 【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )





    二、偏序集



    偏序集 :

    ≼ \preccurlyeq 关系 是 A A A 集合上的偏序关系 , 则称 集合 A A A偏序关系 ≼ \preccurlyeq 构成的 有序对 < A , ≼ > <A, \preccurlyeq> <A,> 称为偏序集 ;

    如果集合上有偏序关系 , 那么这个集合就称为偏序集 ;


    参考博客 : 【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )





    三、可比



    可比 :

    A A A 集合 , 该集合上存在 偏序关系 ≼ \preccurlyeq 小于等于 ,

    偏序集 是 集合 和 偏序关系 组成的有序对 < A , ≼ > <A, \preccurlyeq> <A,> ,

    x , y x, y x,y A A A 集合中的两个元素 , x , y ∈ A x , y \in A x,yA ,

    要么是 x ≼ y x \preccurlyeq y xy , 要么就是 y ≼ x y \preccurlyeq x yx , 符号化表示是 x ≼ y ∨ y ≼ x x \preccurlyeq y \lor y \preccurlyeq x xyyx , 两种情况必选其一 ,

    则称 x x x y y y 是可比的 ;


    只要 x , y x, y x,y 之间 存在偏序关系 , 不管谁在前 , 谁在后 , 都 统一称 x x x y y y 是可比的 ;


    参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )





    四、严格小于



    严格小于 概念需要基于 可比概念


    严格小于 :

    A A A 集合 与 A A A 上偏序关系 ≼ \preccurlyeq , 组成 偏序集 < A , ≼ > <A, \preccurlyeq> <A,> ,

    x , y x, y x,y A A A 集合中的两个元素 , x , y ∈ A x , y \in A x,yA ,

    如果 x , y x , y x,y 是可比的 ( x , y x,y x,y 之间存在偏序关系 ) , 但是 x x x y y y 不相等 , 则称 x x x 严格小于 y y y ;


    符号化表示 : x ≼ y ∧ x ≠ y ⇔ x ≺ y x \preccurlyeq y \land x \not= y \Leftrightarrow x \prec y xyx=yxy


    参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )





    五、覆盖



    覆盖 概念需要基于 严格小于概念


    覆盖 :

    A A A 集合 与 A A A 上偏序关系 ≼ \preccurlyeq , 组成 偏序集 < A , ≼ > <A, \preccurlyeq> <A,> ,

    x , y , z x, y , z x,y,z A A A 集合中的元素 , x , y , z ∈ A x , y , z \in A x,y,zA ,

    x x x 严格小于 y y y , x ≺ y x \prec y xy ,

    不存在 z z z , 使 x x x 严格小于 z z z , 并且 z z z 严格小于 y y y ,

    则称 y y y 覆盖 x x x ; ( 注意是 大 覆盖 小 )


    偏序关系中 大 覆盖 小


    符号化表示 : x ≺ y ∧ ¬ ∃ z ( z ∈ A ∧ x ≺ y ≺ z ) x \prec y \land \lnot \exist z( z \in A \land x \prec y \prec z ) xy¬z(zAxyz)


    参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )





    六、哈斯图



    A A A 集合 A A A 上偏序关系 ≼ \preccurlyeq , 组成 偏序集 < A , ≼ > <A, \preccurlyeq> <A,> ,

    x , y x, y x,y A A A 集合中的两个元素 , x , y ∈ A x , y \in A x,yA ,


    哈斯图 :

    ① 顶点 : 使用 顶点 表示 A A A 集合中的元素 ;

    ② 无向边 : 当且仅当 y y y 覆盖 x x x , y y y 顶点在 x x x 顶点 上方 , 并且在 x x x 顶点 与 y y y 顶点之间 绘制一条 无向边 ;



    在这里插入图片描述

    上图是 6 6 6 元集 上的偏序关系 ≼ \preccurlyeq

    A A A 元素比 B , C , D B,C,D B,C,D 元素都小

    偏序关系是传递的 , A A A B B B 小 , B B B F F F 小 , 因此 A A A F F F

    最下面的元素 A A A 是最小的 , 所有的元素都比 A A A 大 ( 包括 A A A , 偏序关系是自反的 )

    最上面的元素 F F F 是最大的 , 所有的元素都比 F F F 小 ( 包括 F F F , 偏序关系是自反的 )

    B C D E BCDE BCDE 四个元素互相都不可比



    哈斯图 与 关系图对比 省略的内容 :

    ① 环 : 偏序关系是自反的 , 因此 每个顶点上都有环 , 可以省略掉环

    ② 箭头 : 偏序关系是反对称的 , 因此 两个顶点两两之间肯定没有双向边 , 都是单向边 , 因此可以省略箭头方向

    ③ 默认方向 : 使用上下位置表示箭头的方向 , 箭头默认向上 , 偏序是 小于等于 , 最小的在最小面, 最大的在最上面 ;


    参考博客 :





    七、全序关系 ( 线序关系 )



    A A A 集合与该集合之上的 偏序关系 ≼ \preccurlyeq 组成的有序对是 : < A , ≼ > <A, \preccurlyeq> <A,> 偏序集 ;

    A A A 集合中 任意元素 x , y x, y x,y 都 可比 ;

    则称 ≼ \preccurlyeq 关系是 A A A 集合上的 全序关系, 又称为 线序关系 ;

    < A , ≼ > <A, \preccurlyeq> <A,> 为全序集 ( 线序集 ) ;



    < A , ≼ > <A, \preccurlyeq> <A,> 偏序集 是全序集

    当且仅当

    < A , ≼ > <A, \preccurlyeq> <A,> 偏序集的哈斯图是一条直线


    参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )





    八、拟序关系



    非空集合 A A A , 二元关系 R R R A A A 集合上的二元关系 ;

    符号化表示 : A ≠ ∅ A \not= \varnothing A= , R ⊆ A × A R \subseteq A \times A RA×A ;

    如果 二元关系 R R R反自反 , 传递 的 ,

    则称 R R R 关系是 A A A 集合上的拟序关系 ,

    使用 ≺ \prec 表示拟序关系 ,

    < A , ≺ > <A , \prec> <A,> 是拟序集 ;


    偏序关系 ≼ \preccurlyeq 是 小于等于 关系 , 拟序关系 ≺ \prec 就是 严格小于 关系 ;


    拟序关系示例 : 大于 , 小于 , 真包含 , 都是拟序关系 ;


    拟序关系 完整的性质是 反自反 , 反对称 , 传递 ,
    之所以概念中没有提 反对称 性质 , 是因为 根据 反自反 , 传递性质 , 可以推导出 反对称 性质 ;

    数学中倾向于使用最小的条件进行定义 , 因此这里将反对称性去掉 ;


    参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )





    九、拟序关系相关定理



    定理 1 :

    非空集合 A A A , A ≠ ∅ A \not= \varnothing A= ,

    ≼ \preccurlyeq 是非空集合 A A A 上的偏序关系 ,

    ≺ \prec 是非空集合 A A A 上的拟序关系 ;


    ① 偏序关系性质 : ≼ \preccurlyeq 自反 , 反对称 , 传递的

    ② 拟序关系性质 : ≺ \prec 反自反 , 反对称 , 传递的

    ③ 偏序关系 -> 拟序关系 : 偏序关系 减去 恒等关系 就是 拟序关系 , ≼ − I A = ≺ \preccurlyeq - I_A = \prec IA=

    ④ 拟序关系 -> 偏序关系 : 拟序关系 与 恒等关系 的并集就是 偏序关系 , ≺ ∪ I A = ≼ \prec \cup I_A = \preccurlyeq IA= ;





    定理 2 :

    非空集合 A A A , A ≠ ∅ A \not= \varnothing A= ,

    ≺ \prec 是非空集合 A A A 上的拟序关系 ;


    x ≺ y x \prec y xy , x = y x=y x=y , y ≺ x y \prec x yx 中最多有一个成立 ;

    使用反证法 , 任意两个成立都会导致 x ≺ x x \prec x xx ;


    ( x ≺ y ∧ x = y ) ∧ ( y ≺ x ∧ x = y ) ⇒ x = y (x\prec y \land x = y) \land (y \prec x \land x=y) \Rightarrow x = y (xyx=y)(yxx=y)x=y





    定理 3 三歧性 , 拟线序 :

    非空集合 A A A , A ≠ ∅ A \not= \varnothing A= ,

    ≺ \prec 是非空集合 A A A 上的拟序关系 ;


    如果 x ≺ y x \prec y xy , x = y x=y x=y , y ≺ x y \prec x yx 中仅有一个城里 , 那么称 ≺ \prec 拟序关系 具有 三歧性 ;

    有三歧性的 逆序关系 ≺ \prec 称为 A A A 集合上的 拟线序关系 , 又称为拟全序关系 ;

    < A ≺ > <A \prec> <A> 被称为 拟线序集 ;


    参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )





    十、偏序关系八种特殊元素



    参考博客 : 【集合论】序关系 ( 偏序关系中八种特殊元素 | ① 最大元 | ② 最小元 | ③ 极大元 | ④ 极小元 | ⑤ 上界 | ⑥ 下界 | ⑦ 最小上界 上确界 | ⑧ 最小下界 下确界 )





    十一、链



    < A , ≼ > <A, \preccurlyeq> <A,> 是 偏序集 , B ⊆ A B \subseteq A BA ,

    偏序集中一组元素组成集合 B B B , 如果 B B B 集合中的元素两两都可比 , 则称 B B B 集合是该偏序集 < A , ≼ > <A, \preccurlyeq> <A,> 的链 ;

    符号化表示 : ∀ x ∀ y ( x ∈ B ∧ y ∈ B → x 与 y 可 比 ) \forall x \forall y ( x \in B \land y \in B \to x 与 y 可比 ) xy(xByBxy)


    链的本质是一个集合

    ∣ B ∣ |B| B 是链的长度

    参考博客 :





    十二、反链



    < A , ≼ > <A, \preccurlyeq> <A,> 是 偏序集 , B ⊆ A B \subseteq A BA ,

    偏序集中一组元素组成集合 B B B , 如果 B B B 集合中的元素两两都 不可比 , 则称 B B B 集合是该偏序集 < A , ≼ > <A, \preccurlyeq> <A,> 的 反链 ;

    符号化表示 : ∀ x ∀ y ( x ∈ B ∧ y ∈ B ∧ x ≠ y → x 与 y 不 可 比 ) \forall x \forall y ( x \in B \land y \in B \land x\not= y \to x 与 y 不可比 ) xy(xByBx=yxy)


    反链的本质是一个集合

    ∣ B ∣ |B| B 是反链的长度


    参考博客 :





    十三、链与反链定理



    参考博客 :

    展开全文
  • 偏序关系中的特殊元素问题 偏序关系证明 哈斯图 链 反链



    偏序关系中的特殊元素问题


    题目 : 偏序关系 特殊元素 ;

    • 条件 : 下图是 某一 偏序集 &lt; A , ⪯ &gt; &lt;A, \preceq&gt; <A,> 的哈斯图 , 其中 A = { a , b , ⋯ &ThinSpace; , k } A=\{a,b,\cdots,k\} A={a,b,,k}
    • 问题 1 1 1 : B 1 = { a , c , d , e } B_1 = \{a,c,d,e\} B1={a,c,d,e} 是什么链 ;
    • 问题 2 2 2 : B 2 = { a , e , h } B_2 = \{a,e,h\} B2={a,e,h} 是什么链 ;
    • 问题 3 3 3 : B 3 = { b , g } B_3 = \{b,g\} B3={b,g} 是什么链 ;
    • 问题 4 4 4 : B 4 = { g , h , k } B_4 = \{g,h,k\} B4={g,h,k} 是什么链 ;
    • 问题 5 5 5 : B 5 = { a } B_5 = \{a\} B5={a} 是什么链 ;
    • 问题 6 6 6 : B 6 = { a , b , g , h } B_6 = \{a, b, g, h\} B6={a,b,g,h} 是什么链 ;
    • 问题 7 7 7 : B 1 B_1 B1 的上界, 下界, 上确界 , 下确界 ;
    • 问题 8 8 8 : B 4 B_4 B4 的上界, 下界, 上确界 , 下确界 ;

    在这里插入图片描述

    解答 :

    ① 问题 1 1 1 : B 1 = { a , c , d , e } B_1 = \{a,c,d,e\} B1={a,c,d,e} 是一条 长为 4 的 链 ;
    这四个元素互相之间是可比的 ; 并且也是覆盖的 , e e e 覆盖 d d d , d d d 覆盖 c c c , c c c 覆盖 a a a ;

    ② 问题 2 2 2 : B 2 = { a , e , h } B_2 = \{a,e,h\} B2={a,e,h} 是一条 长为 3 的链 ;
    a , e , h a,e,h a,e,h 之间都是可比的 , 但没有覆盖关系 , 即他们之间都有其它元素相隔 , 这也是链 ;
    集合中有 n n n 个元素 , 且这些元素可比 , 那么这个集合就是一个长为 n n n 的链 , 中间可以隔着其它元素 ;

    ③ 问题 3 3 3 : B 3 = { b , g } B_3 = \{b,g\} B3={b,g} 是一条 长为 2 的链 ;
    b , g b,g b,g 之间隔着 4 个元素 , 但这个集合中元素是可比的 , 也是链, 长度为集合的元素个数 ;

    ④ 问题 4 4 4 : B 4 = { g , h , k } B_4 = \{g,h,k\} B4={g,h,k} 是一条 长为 3 的 反链 ;
    集合中的元素 , 都不可比 , 那这个集合就是反链 ;
    如果一部分可比 , 另一部分不可比 , 那这个集合什么都不是 , 既不是链 , 也不是反链 ;

    ⑤ 问题 5 5 5 : B 5 = { a } B_5 = \{a\} B5={a} 是一条 长为 1 的 链 , 同时也是一条长为 1 的反链 ;
    如果集合中只有一个元素 , 那么该集合 既是 链 , 又是 反链 , 长度为 1 1 1 ;

    ⑥ 问题 6 6 6 : B 6 = { a , b , g , h } B_6 = \{a, b, g, h\} B6={a,b,g,h} 既不是链 , 也不是反链 ;
    g , a g,a g,a 是可比的, h , a h,a h,a 是可比的 , g , b g,b g,b 是可比的 , h , b h,b h,b 是可比的 , g , h g,h g,h 不可比 , a , b a,b a,b 不可比 , 因此其 既不是链 , 也不是反链 ;

    ⑦ 问题 7 7 7 :

    上界问题 :

    • 1> 上界集合 : B 1 = { a , c , d , e } B_1 = \{a,c,d,e\} B1={a,c,d,e} 上界集合为 { e , f , g , h } \{e, f,g,h\} {e,f,g,h} ;
    • 2> 上确界 ( 最小上界 ) : B 1 B_1 B1 的上确界 是 e e e , 即 上界集合的 最小元 ;

    注意 :
    上界 是一个元素 , 一个集合的上界 可能有很多个, 上界集合 是 上界元素 的集合 ;
    上界集合中的最小元 是 上确界 或 最小上界 ;
    集合不一定有上界 ( 有可能上面有两个极大元, 互不可比 ) , 有上界 不一定有 上确界 ;

    下界问题 :

    • 1> 下界集合 : B 1 = { a , c , d , e } B_1 = \{a,c,d,e\} B1={a,c,d,e} 下界集合为 { a } \{a\} {a} ;
    • 2> 下确界 ( 最大下界 ) : B 1 B_1 B1 的下确界 是 a a a , 即 下界集合的 最大元 ;

    注意 :
    下界 是一个元素 , 一个集合的下界 可能有很多个, 下界集合 是 下界元素 的集合 ;
    下界集合中的最大元 是 下确界 或 最大下界 ;
    集合不一定有下界 ( 有可能下面有两个极小元, 互不可比 ) , 有下界 不一定有 下确界 ( 最大下界 ) ;

    求 一个 集合 的 下界和上界 , 注意从集合的 最小元 ( 下界 ) 和 最大元 ( 上界 ) 开始算 , 不要忽略这两个元素 ;


    ⑧ 问题 8 8 8 : B 4 = { g , h , k } B_4 = \{g,h,k\} B4={g,h,k} 是反链 , 其没有 上界 和 下界 , 自然 也 不存在 上确界 和 下确界 ;
    反链 是 没有 上界 和 下界的 , 元素之间都不可比 ;




    偏序关系证明 哈斯图 链 反链


    题目 :

    • 条件 : 集合 A A A 120 120 120 的所有因子组成的集合 , " ∣ | " 是 A A A 上的整除关系 ;
    • 问题 1 : 证明该 关系 是 偏序关系 ;
    • 问题 2 : 画出关系的哈斯图
    • 问题 3 : 确定 A A A 中的最长链 ; 写出所有最长链 ;
    • 问题4 : A A A 中的元素至少可以划分成多少个互不相交的反链 , 并写出这些反链 ;

    解答 :

    问题 1 : 偏序关系证明 :

    ① 写出 120 120 120 的因子集合 : 先列出其素因子 , 然后使用素因子组合即可 ;
    ( 注意 x x x 整除 y y y , x x x 是较小的数 , 是除数 , y y y 是较大的数 , 是被除数 , 除 数 ∣ 被 除 数 除数 | 被除数 是整除关系的表示 )
    A = { 1 , 2 , 3 , 4 , 5 , 6 , 8 , 10 , 12 , 15 , 20 , 24 , 30 , 40 , 60 , 120 } A=\{1, 2,3,4,5,6,8,10,12,15,20,24,30, 40,60,120\} A={1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120}

    ② 证明偏序关系 需要证明其 三个性质 自反 反对称 传递 ;

    • 1.证明自反性 : ∀ x ∈ A \forall x \in A xA , x x x 本身 肯定能整除 它自己 , x x x x x x 是可比的 , 因此 x x x 是自反的 ;
    • 2.证明反对称性 : x x x 能整除 y y y , 并且 x x x 不等于 y y y , y y y 肯定不能整除 x x x , 举例 1 1 1 能整除 2 2 2 , 2 2 2 不能整除 1 1 1 ;
    • 3.证明传递性 : x x x 能整除 y y y , y y y 能整除 z z z , 那么 x x x 能整除 z z z 成立 , 举例 1 1 1 能整除 2 2 2 , 2 2 2 能整除 4 4 4 , 那么 1 1 1 能整除 4 4 4 ;

    问题 2 : 画哈斯图 : 先画出 1 1 1 , 从底下向上画, 画完后 逐个检查 是否有遗漏 ;

    在这里插入图片描述

    问题 3 : 确定最长链 并 找出最长链 :

    ① 逐个寻找 , 最长链为 6 , 从底部到上面 从左到右 逐个分支进行遍历 写出 长度为 6 的链 ;
    从底部 1 1 1 开始写 , 最左侧的链 为 :
    { 1 , 2 , 4 , 8 , 24 , 120 } \{1,2,4,8,24,120\} {1,2,4,8,24,120}

    这个最左侧链从顶部向下走 , 从 8 8 8 开始有个分支 , 写下这个链
    { 1 , 2 , 4 , 8 , 40 , 120 } \{1,2,4,8,40,120\} {1,2,4,8,40,120}

    继续往下走 , 4 4 4 的位置有个分支 , 其下对应着 3 3 3 个分支 分别是 :
    { 1 , 2 , 4 , 12 , 24 , 120 } \{1,2,4,12,24,120\} {1,2,4,12,24,120}
    { 1 , 2 , 4 , 12 , 60 , 120 } \{1,2,4,12,60,120\} {1,2,4,12,60,120}
    { 1 , 2 , 4 , 20 , 60 , 120 } \{1,2,4,20,60,120\} {1,2,4,20,60,120}

    继续往下走 , 2 2 2 的位置有分支 , 对应

    给出参考答案 , 不在详细列出 :

    124824120
    
    124840120
    
    1241224120
    
    1241260120
    
    1261260120
    
    1263060120
    
    1361224120
    
    1361260120
    
    1363060120
    
    13153060120
    
    15102040120
    
    15103060120
    
    15153060120
    

    问题 4 : 集合 A A A 至少划分成 多少 互不相交的反链 , 完整写出这些反链 :

    分析 : 将集合 A A A 划分成最多的反链个数 是 16 16 16 个 , 即每个元素都划分成一个单独的反链 ;
    { { 1 } , { 2 } , { 3 } , { 4 } , { 5 } , { 6 } , { 8 } , { 10 } , { 12 } , { 15 } , { 20 } , { 24 } , { 30 } , { 40 } , { 60 } , { 120 } } \{\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{8\}, \{10\}, \{12\}, \{15\}, \{20\}, \{24\}, \{30\}, \{ 40\}, \{60\}, \{120\}\} {{1},{2},{3},{4},{5},{6},{8},{10},{12},{15},{20},{24},{30},{40},{60},{120}}

    现在需要将其尽可能多的将上述集合进行合并 , 每个集合必须是反链 :
    { { 1 } , { 120 } , { 2 , 3 , 5 } , { 4 , 6 , 15 , 10 } , { 8 , 12 , 30 , 20 } , , { 24 , 60 , 40 } } \{ \{ 1 \}, \{ 120 \}, \{2,3,5\} , \{ 4,6,15,10 \} , \{ 8, 12 , 30, 20 \} , , \{ 24, 60 , 40 \} \} {{1},{120},{2,3,5},{4,6,15,10},{8,12,30,20},,{24,60,40}}

    结果 : 至少能划分成 6 个互不相交的反链 ;

    技巧 : 哈斯图 横向 没有关联的一条线 可以组成一条反链 ;


    展开全文
  • 一、可比 、 二、严格小于 、 三、覆盖 、 四、哈斯图
  • 数学中的哈斯图如何构造?附实例

    千次阅读 2019-06-22 10:25:57
    首先写出偏序集合;...最后构造哈斯图,值域一般在最上方,定义域在下方。 例子:设A为54的因子构成的集合R A×A, x,y∈A, xRy x整除y.画出偏序集的哈斯图, 并求最大元最小元极大元极小元. 在这里先...
  • 下面是习题与解析 文章目录 第一题 序偶与类型 第二题 关系图,矩阵与类型 第三题关系图,矩阵与类型 第四题 复合关系 第五题 求t( R) 第六题 求表达式 第七题 求关系图等价类 第八题 写出序偶与哈斯图 第一题 序偶...
  • 哈斯图的画法,以及利用哈斯图寻找极大元之类

    万次阅读 多人点赞 2017-06-02 12:00:28
    哈斯图的画法要确定层数。也就是谁在上,谁在下。我在看过这个文章偏序集的哈斯图的画法之后结合书上的一些定义进行总结:(恒等关系在哈斯图上体现不出来就不说了。) 1.先把没有出现在值域(<a,b>, 其中b为...
  • 那么对于某一偏序集的哈斯图,我们只需对图中任意两个不同元素都验证其最大下界以及最小上界的存在性。 注意到:这里的最大下界和最小上界都是针对下界集和上界集而言的。 要求最大下界满足与下界集合
  • 将挺好的:B站上可以找到资源,也是我想说的 https://blog.csdn.net/hpdlzu80100/article/details/102952763
  • 离散数学偏序关系哈斯图上(下)确界极小(大)值最大(小)值 关于关系,看了好多感觉这篇好是不错的,主要记着最后一个总结即可。 偏序关系 哈斯图画法 最小元 最大元 极小元 极大元 上界 下界 上确界 下确界 ...
  • 如何确定哈斯图极大极小元、最大最小元、最大最小上下界 1.如果图中有孤立结点,那么这个结点既是极小元也是极大元,并且图中既无最小元也无最大元(特殊情况) 2.除了孤立结点以外,其他的极小元是图中所有向下通路...
  • 目录 示例 极小元与极大元 最小元与最大元 上界与下界 最小上界(上确界)和最大下界(下确界) 练习题 示例 前置知识: 1)偏序关系与偏序集 2)哈斯图的概念及绘画 示例是整除关系,C表示全集{1,2,3,6,12,24,36}。...
  • 1. 哈斯图的引入背景 2. 哈斯图(Hasse Diagram)的定义 3. 哈斯图示例 4. 最大元和最小元的定义 5. 极大元和极小元的定义 6. 上界和上确界的定义及示例 7. 下界和下确界的定义及...
  • 求出n的偏序关系下的哈斯图的边数求出n的偏序关系下的哈斯图的边数求出n的偏序关系下的哈斯图的边数 如图 n = 60 题解 考虑对n质因子分解考虑对n质因子分解考虑对n质因子分解 分解为m个质数因子每个因子...
  • 哈斯图伪代码

    千次阅读 2013-04-18 18:47:45
    最近离散学了哈斯图,网上关于哈斯图的东西还挺少的,其实我觉得哈斯图主要就是表示偏序关系的,下面是我写的哈斯图编程的伪代码~  关系R所在的集合为B集合。  For(int i= 1;集合B不为空集;i++)  将以B中任何...
  • 哈斯(Hasse)

    2020-12-01 18:52:00
    \)的Hasse的作法如下: 用小圆圈(或小圆点)表示集合A中的元素; 如果a≤b,且a\(\ne\)b,则将代表a的小圆圈画在代表b的小圆圈的下方。 只有当a是b的直接前辈(后裔)时,才将代表a的小圆圈和代表b的小圆圈用直线连接。...
  • 题意:开始时有n堆糖,每堆开始时有1个把这些糖果聚在一堆。但她每次只能把两堆糖果合并成一堆。 已知把两堆数量为a和b的糖果聚在一堆的代价是|a-b|。 kotori想知道,她把这n块糖果聚在一堆的最小代价是多少?...
  • 介绍偏序集Hasse的画法和重要元素
  • hdu 拓扑排序归纳

    2018-01-08 19:03:41
    拓扑排序,其本质是输出一个全序关系,对于按要求输出给定关系的题目,一般就是按照题目要求实现这个全序关系,这种题时常会先给一个偏序关系,然后给出剩下的元素如何建立... 哈斯图:对一个偏序关系画的图,每个点
  • ,≼>,≼> 偏序集 是全序集 当且仅当 ,≼>,≼> 偏序集的哈斯图是一条直线 二、全序关系示例 非空集合 AAA 包含于 实数集 RRR , ∅≠A⊆R\varnothing \not= A \subseteq R∅​=A⊆R , AAA 集合上的 大于等于 ≥\...
  • 离散数学偏序关系

    千次阅读 2020-05-09 19:43:38
    比较重要的就是哈斯图,有了哈斯图理解偏序关系就很容易。 哈希图就是在关系图的基础上进行简化,去掉自环和直通路以及方向(默认下到上) 做哈斯图关键的就是求“盖住”关系,将Warshall算法改进即可容易的求出盖住...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 619
精华内容 247
关键字:

哈斯图