伪树

更新时间:2022-09-19 21:21

伪树(pseudo-tree)是由组成的一种集合,在偏序集〈A,R〉中,若对任何a∈A,所有满足bRa的A中元素b的集合B都是R链,则称〈A,R〉为一棵伪树,而集合B称为树枝。

基本介绍

定义 一偏序集合叫做关于R的一伪树,如果,对于每一x∈S,则x的R前节:

都是S的一个R-链,并称它为树枝。

全序集是一棵伪树,并且它的枝叠合在一起,偏序结构〈A,R〉成为伪树时,其哈塞图在直观上像一棵或多棵分离开的树,只有向上的分叉,而无向下的分叉,并且无闭合的枝。如图1表示的结构是伪树,而图2、图3表示的结构不是伪树。当〈A,R〉是伪树时,〈A,R〉称为倒伪树。

例题解析

【例1】令S={2,4,6,8,10},偏序s>是—伪树,因为它的任一元的1s前节都是一1s链。

【例2】令S={2,8,10,20,16,24},那么偏序集合s>也是一伪树。

【例3】令S={2,8,10,16,20,24,32,96}偏序集合s>如图4所示,它不是一伪树,因为96的1s前节O1s(96)={32,16,24,8,2},而24与16在1s下不可比较,不构成一个1s链。

【例4】偏序结构{ω,∈ω)是一伪树。

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}