更新时间:2022-09-19 21:21
定义 一偏序集合叫做关于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】偏序结构{ω,∈ω)是一伪树。