（运筹学与控制论专业论文）组合设计的大集.pdf

摘要 设x 是一个有限集。x 上的一个循环三元组如，y ，z ) 是指由x 中的三 个有序对( 茹，) ，( 玑力和( 2 ，z ) 构成的集合x 上的一个可迁三元组扛，! f ，z ) 是指由x 中的三个有序对( ，可) ，( ，z ) 和扛，。) 构成的集合一个。阶的有 向三元系是一个对子( x ，聊，其中x 是一个口元集，b 是x 上一些循环 或可迁三元组( 称为区组) 的集合，并且x 中的任意有序对恰好属于b 的 一个区组特别地，如果b 中的区组都是循环的( 或可迁的) ，则( x ，聊叫 做m e n 础o h n ( 或可迁) 三元系，并记作m t s ( v ) ( 或d 丁s ( 口) ) 设( x ，砷是一个m t s ( v ) ，如果( n ，b ，c ) a 蕴涵c b ，隹4 ，则此设计 叫做纯的，并记作p m t s ( v ) 类似地，一个纯的d t s ( ) ( 简记作p 凹s ( 口) ) 僻，4 ) 是一个这样的胛s ( 口) ，( 口，b ，c ) a 蕴涵( c 6 ，口) 譬4 如果m t s ( v ) 或d r s ( u ) 的区组集能够划分成若干个子集，每个子集 包含x 的每个元素恰好一次，更9 称此设计为可分解的可分解的m t b ( v ) 与可分解的刃s ( 口) 分别记为r m t s ( v ) 及r 胛s ( 口) m t s ( v ) ( 或砑s ( ) ) 的大集，记作l m t s ( v ) ( 或l 砑s ( ) ) ，是u 元集 x 上口一2 个m t s ( v ) ( 或3 扣一2 ) 个d z 苫( ) ) 的集合，并使得x 上任 意循环( 或可迁) 三元组作为区组恰好出现予一个m t s ( v ) ( 或d t s 扣) ) 之 中l p m t s ( v ) ( 或l p 凹s c v ) ) 表示一个l m t s ( v ) ( 或l d t s ( v ) ) ，其中每 个m t s ( v ) ( 或d r s 0 ) ) 都是纯的l r m t s ( v ) ( 或r d t s ( ) ) 表示一个 l m t s ( v ) ( 或二d 7 苫( 口) ) ，其中每个m t s ( v ) ( 或d t s ( v ) ) 都是可分解的 m t s ( v ) 的超大集，记作o l m t s ( 口) ，是一个集合 僻 z ) ，玩) ：茹x ， 其中x 是口+ 1 元集，僻缸 ，玩) 是m t s ( v ) ，并且u 蚝x 改正好包畲x 上 所有循环三元组o l p m t s ( v ) 表示一个o l m t s ( v ) ，其中每个m t s ( v ) 都 是纯的 1 8 5 0 年，l ( i r l c m 缸在l m y 8 锄dg e n t l e m 柚sd i a r y 中提出了一个 问题：十五个女生捧成三列出去散步，能否在一周内使得任意两人不在 同一行出现两次? 这个问题实际上是要寻找一个1 5 阶的k i r 虹瑚三元系 摘要 k t s ( 1 5 ) k i r k m a n 十五女生问题提出之初，s y l v e s t e r 进一步提出；1 5 元 集合上的4 5 5 个3 - 子集能否划分成1 3 个k t s ( 1 5 ) ? s y l v e s t e r 十五女生问题是数学史上第一类大集问题，激发了许多专业 人士与业余爱好者的兴趣自此之后各种各样的大集问题相继被提出与研 究1 9 8 3 至1 9 8 4 年，我国数学家陆家羲为解决s t e i n e r 三元系大集问题做 出了突出的贡献到目前为止，l s t s ，l m t s 及l d t s 的存在性问题已 完全解决，而l p m t s ，l p d t s ，l k t s ，l r m t s 及l r d t s 的研究结果却 很少 本文研究组合设计的大集问题，诸如l p m t s ，l p d t s ，l r m t s 及 l r d t s b e n n e t t ，k a n g , l e i 及z h a n g 给出了l p m t s 的一些递归构造，并证明 了l p m t s ( 1 2 k ) 及l p m t s ( 1 2 k + 4 ) 是存在的日子红应用类似的方法， 给出了关于l p d t s 的递归构造，证明了l p d t s ( 6 k ) 及l p d t s c 6 k + 4 ) 的 存在性本文采用新的得力递归构造，结合必要的直接构造，彻底解决了 l p m t s 及l p d t s 的存在性问题 l r m t s 及l r d t s 的存在结果非常有限若 为奇数，l r m t s ( v ) 及 l r d t s ( v ) 的大部分结论从l k t s ( v ) 得到，而l k t s ( v ) 的存在性问题亦 尚未解决这些问题还需要更多技巧本文给出了l r d t s 的一个三倍构 造，给出了l r m t s 及l r d t s 的乘积构造，建立了几个新的无穷类 论文的主要结果总结如下； ( 1 ) 当且仅当口三0 ，1 ( r o o d3 ) 且口4 时存在l p d t s ( v ) ( 2 ) 当且仅当 兰0 ，1 ( r o o d3 ) ，1 ，之4 且口6 ，7 时存在l p m t s o , ) ( 3 ) 对下列阶数 存在l r m t s ( v ) 及l r d t s ( v ) ；1 0 = 3 ”m ( 2 w ，+ 1 ) ( 2 磅2 + 1 ) ( 2 婶+ 1 ) ，其中n 1 ，t 0 ，啦之1 ， 。 7 ，1 3 0 = 1 ，2 ，一，t ) ， m 1 ，4 ，5 ，7 ，1 1 ，1 3 ，1 7 ，2 3 ，2 5 ，3 5 ，3 7 ，4 1 ，4 3 ，4 7 ，5 3 ，5 5 ，5 7 ，6 1 ，6 5 ，6 7 ，9 l ， 1 2 3 u ( 7 + 2 ) 3 ，( 1 3 + 2 ) 3 ，( 2 5 + 2 ) 3 ，2 曲+ 1 2 5 j + 1 ：0 且j o 全文分为五章 第一章本章为引言，回顾了大集问题的历史背景，介绍了相关问题 的进展，列出了本文的主要方法及结果 ；v 摘要 第二章本章确定了l p d t s 的存在谱首先引入扛纯可划分的可迁 烛台系( 简记作v p p d c s ) 的概念，给出了用0 p p d c s 构造l p d t s 的方 法接着，利用s - f a n 设计给出了扛p p d c s 的递归构造然后通过一些输入 设计的直接构造，确定了l p d t s ( 6 k + 3 ) ，l p d t s ( 1 2 k + 7 ) 及l p d t s ( 1 2 k + 1 ) 的存在性最后l p d t s 的存在谱完全确定 第三章本章确定了l p m t s 的存在谱一方面，首先类似于第二章，列 出了l p m t s 及v p p m c s 的递归构造然后直接构造了1 - p p m c s ( 6 3 ：4 ) 及o - p p m c s ( 6 3 ：3 ) ，从而确定了l p m t s ( 1 2 k + 9 ) 及l p m t s ( 1 2 k + 1 ) 的存 在性另一方面，对于奇数口7 ，建立了从l p m t s ( v ) 及o l p m t s ( v ) 到 l p m t s ( 2 v + 1 ) 的特殊构造最终确定了l p m t s 的存在谱 第四章本章建立了l r d t s 的三倍构造首先引入了双可迁的可分解 幂等拟群( 筒记作d t r i q ) 的概念然后证明当且仅当3 印且”2 ( r o o d4 ) 时存在d t m q o , ) 最后建立了从l r d t s ( v ) 及d t r i q ( v ) 到l r d t s ( 3 v ) 的 三倍构造，同时得到了一个偶数阶的无穷类，l j w t s ( 4 3 n ) 第五章本章建立了l r m t s 及l r d t s 的乘积构造证明了若存在 l r m t s ( u ) ( 或l r d t s ( u ) ) ，t r i q ( u ) ( 或d t r i q ( v ) ) 及l r ( , j ) ( l e i 引入的一 种设计) ，则存在l r m t s ( u v ) ( 或l r d t s ( u v ) ) 利用这样的构造得到了更多 的无穷类 关键词t 大集；m e n d e l s o h n 三元系；可迁三元系；纯的；烛台系；乒纯可 划分的；可分解的；拟群；双可迁的 e x t e n d e da b s t r a c t ac y c h c t r i p l e ( ，y ，z ) o n x i sa8 e to f t h r e eo r d e r e dp a i r s ( z ，私) ，( y ，z ) a n d ( ：，。) o f x at r a n s i t i v et r i p l e ( ，z ) o nxi sa8 e to ft h r e eo r d e r e dp a i r s ( z ，掣) ，( 箩，2 ) a n d ( 毛：) o fx a no r i e n t e dt r i p t es y s t e mo fo r d e r 口i sap a i r ( x ，b ) w h e r exi sa v - s e t a n d 艿i sac o l l e c t i o no fc y c l i co rt r a n s i t i v et r i p l e so nx ，c a l l e db l o c k s ，s u c ht h a te v e r y o r d e r e dp a i ro fx b e l o n g st oe x a c t l yo n eb l o c ko f 舀i np a r t i c u l a r i ft h et r i p l e si n ba r ea l lc y c l i c ( o rt r a n s i t i v e ) ，t h e n 廖) i sc a l l e dam e n d e l s o h n ( o rd i r e c t 唧t r i p l e s y s t e ma n dd e n o t e db ym t s ( v ) ( o rd t s ( v ) ) a nm t s ( v ) ( x ，a ) i sc a l l e dp u r ea n dd e n o t e db yp m t s ( v ) i f ( 峨b ，c ) ai m p l i e s c , b ，口) 聋a s i m i l a r l y , ap u r ed t s ( v ) ( p d t s ( v ) i ns h a f t ) i x ，川i snl y l s ( v ) i n w h i c h ( d ，b ，c ) i m p l i e s ( c ，b ，口) 隹a a nm t s ( v ) ( o ra d t s ( v ) ) i sc a l l e dr e s o l v a b l ef fi t sb l o c k s c a l lb ep a r t i t i o n e di n t o s u b s e t s ( c a l l e dp a r a l l e lc l a s s e s ) ，e a c hc o n t a i n i n ge v e r ye l e m e n to fxe x a c t l yo n c e a r e s o l v a b l em t s ( v ) a n dar e s o l v a b l ed t s ( v ) a r ed e n o t e db yr m t s ( v ) a n dr d t s ( v ) r e s p e c t i v e l y a l a r g es e to fm t s ( v ) s ( o rd t s ( v ) s ) ，d e n o t e db yl m t s ( v ) ( o rl d t s ( v ) ) ，i sn c o l l e c t i o no fv - 2m r s 扣) s ( o r3 ( v 一2 ) d t s ( v ) s ) o nxs u c ht h a te v e r yc y c l i ct r i p l e f o rt r a n s i t i v et r i p l e ) o nxo c c u r s nb l o c ki ne x a c t l yo n eo ft h e 口一2m t s ( v ) s ( o r3 ( v 一2 ) d t s ( v ) s ) a nl p m t s ( v ) ( o rl p d t s ( v ) ) d e n o t e s 衄l m t s ( ( o rl d t s ( v ) ) i nw h i c he a c hm t s ( v ) ( o rd t s ( v ) ) i sp u r e a nl r m t s ( v ) ( o r l r d t s ( v ) ) d e n o t e sa nl m t s ( v ) ( o rl d t s ( v ) ) i nw h i c he a c hm t s ( v ) ( o rd t s ( v ) ) i sr e s o l v a b l e a no v e r l a 缯es e to fm r s ( v ) ，d e n o t e db yo l m t s ( v ) ，i snc o n e c t i o n ( x “i e x t e n d e c la b s t r a c t z ) ，玩) ：z x ，w h e r ex i sa ( 口+ 1 ) - s e t ，e a c h ( x 。) ，艮) i sa nm t s ( v ) a n d u “岛i sp r e c i s e l ya l lc y c l i ct r i p l e so nx s i m i l a r l y ，w ec a n d e f i n ea no l p m t s ( v ) a sa l lo l m t s ( v ) i nw h i c he a c hm t s ( v ) i sp u r e i n1 8 5 0k i r k m a np o s e dap r o b l e mi nl a d y 0a n dg e n t l e m a n sd i a r y 嬲f o l l o w s ： f i f t e e ny o u n gl a d i e si nas c h o o lw a l ko u tt h r e ea b r e a s tf o rs e v e nd a y si ns u c c e s s i o n ： i t i sr e q u i r e dt oa r r a n g et h e md a i l y ，8 0t h a tn ot w os h a l lw a l kt w i c ea b r e a s t hm o d e r nl a n g u a g e w ea r et of i n do u tak i r k m a nt r i p l es y s t e mo fo r d e r1 5 ( k t s ( 1 5 ) ) e a r l yo ni nt h es t u d y o ft h ek i r k m a ns c h o o l g i r l sp r o b l e m ，a ni n t e r e s t i n ge x t e n s i o n w a ss u g g e s t e db ys y l v a s t e r ： c a nt h e4 5 5t r i p l e so ft h ee l e m e n t so fa1 5 - s e tb eg r o u p e di n t o1 3d i f f e r e n t k t s ( 1 5 ) d e s i g n s ? t h i 8i st h ef i r s tl a r g es e tp r o b l e mi nt h em a t h e m a t i c sh i s t o r y , w h i c he x c i t e dg r e a t i n t e r e s ta m o n ga m a t e m - sa n dp r o f e s s i o n a l s f r o mt h e no nv a r i o u sl a r g es e tp r o b l e m s w e r ep o s e da n di n v e s t i g a t e d 1 9 8 3a n d1 9 8 4w i t n e s s e dt h er e m a r k a b l ew o r ko fl u j i a x io nt h ec h a l l e n g i n gl a r g es e tp r o b l e mo fs t e i n e rt r i p l es y s t e m s t i l ln o wt h e e x i s t e n c ep r o b l e m so fl s t s s ，l m t s sa n dl d t s sh a v eb e e nc o m p l e t e l ys e t t l e d h o w e v e r ，t h er e s e i 9 , r c h e so nl p m t s s ，l p d t s s ，l k t s s ，l r m t s sa n dl r d t s s h a v en o ta c h i e v e de n o u g hr e s u l t s i nt h i st h e s i sw ei n v e s t i g a t es u c hl a r g es e tp r o b l e m sa sl p m t s s l p d t s s ， l r m t s sa n dl r d t s s b e n n e t t ，k a n g ，l e ia n dz h a n gg a v es o m er e c u r s i v ec o n s t r u c t i o n st o tl p m t s s a n d p r o v e d t h ee x i s t e n c e o f l p m t s ( 1 2 k ) s a n d l p m t s ( 1 2 k + 4 ) s f o l l o w i n gs i m i l a r a p p r o a c h t i a ns h o w e da n a l o g o u sc o n s t r u c t i o n s 奴l p d t s sa n dg a v et h ee x i s t e n c e o fl p d t s ( 6 k ) sa n dl p d t s ( 6 k + 4 ) s i nt h i st h e s i s ，w es o l v ec o m p l e t e l yt h ee x - i s t e n c ep r o b l e m so fl p m t s sa n dl p d t s sb yc o m b i n i n gn e wp o w e r f u lr e c u r s i v e c o n s t r u c t i o n sw i t hn e c e s s a r yd i r e c tc o n s t r u c t i o n s a sf o rl r m t s sa n dl r d t s s ，t h ee x i s t e n c er e s u l t sa r ev e r yl i m i t e d f o ro d d m o s to fl r m t s ( v ) sa n dl r d t s ( v ) sw e r eo b t a i n e df r o ml k t s ( v ) s ，w h o s ee x - 、，i i j e x t e n d e da b s t r a c t i 8 t e n c eh a sn o ty e tb e e ns e t t l e d m o r et e c h m q u 髑a r er e q u i r e df o rt h e s ep r o b l e m s w ed e v e l o pi nt h i st h e s i sat r i p l i n gc o n s t r u c t i o nf o rl r d t s sa n dp r o d u c tc o n s t r u e - t i o n sf o rl r m t s sa n dl r d t s 8 f i n a l l yw ee s t a b l i s hs e v e r a ll l e wi n f i n i t ee x i s t e n c o c k l 8 懈 t h em a i nr e s u l t so f 也i 8t h i 8a r es u m m a r i z e db e l o w ： ( ”t h e r ee x i s t sa n l p d 硝扣) i f a n do n l y f f 郇三0 ，1 ( r o o d3 ) a n d 4 ( 2 ) t h e ee x i s t s a n l p m t s ( v ) i f a n d o n l y i f v 兰0 ，1 ( m o d 3 ) ，口4 a n d u 6 ，7 ( 3 ) t h e me x i s ta nl r m t s ( v ) a n d 蛐l r d t s ( v ) f o r 口= 3 “m ( 2 七 1 + 1 ) ( 2 垮+ 1 ) - ( 2 妒+ 1 ) w h e r en 1 ，t 0 ，啦l ， 7 ，1 3 “= 1 ，2 ， a n dm 1 ，4 ，5 ，7 ，1 1 ，1 3 ，1 7 ，2 3 ，2 5 ，3 5 ，3 7 ，4 l ，4 3 ，4 7 ，5 3 ，5 5 ，5 7 ，6 l ，6 5 ，6 7 ，9 l ， 1 2 3 u ( 7 + 2 ) 3 ，( 1 3 + 2 ) 3 ，( 2 5 + 2 ) 3 ，2 “+ 1 2 + 1 ：0 a n d j o t h et h e s i si sd i v i d e di n t of i v ec h a p t e r s c h a p t e r1 t h i si sa ni n t r o d u c t o r yc h a p t e r t h eh i s t o r i c a lb a c k g r o u n d so fl a r g e s e tp r o b l e m sa r er e c a l l e da n dt h er e c e n td e v e l o p m e n t so nt h er e l a t e dp r o b l e m s & r e i n t r o d u c e d o u rm a i nm e t h o d sa n dr e s u l t sa x ea l s ol i s t e d c h a p t e r2i nt h i sc h a p t e rt h es p e c t r u mt 髓l p d t s si se s t a b l i s h e d f i r s t l y t h ec o n c e p to f t - p u r e l yp a r t i t i o n a b l ed i r e c t e dc a n d e l a b r as y s t e m 协p p d c si ns h o r t 、 i si n t r o d u c e df o rc o n s t r u c t i n gl p d t s ( v ) s s e c o n d i ya p o w e r f u lr e c u r s i v ec o n s t r u c - t i o nf o rt - p p d c s si sa l d i s p l a y e db yu t m z i n gs - f a nd e s i g n s t h i r d l yb yd i r e c t c o n s t m c t m n so ft h en e c e s s a r ys m a l ld e s i g n s ，t h ee x i s t e n c eo fl p d t s ( 6 k + 3 ) s ， l p d t s ( 1 2 k + 7 ) sa n dl p d t s ( 1 2 k + 1 ) si ss u c c e s s i v e l ye s m b l i 8 h e d f i n n yt h e s p e c t r u mf o rl p d t s si sc o m p l e t e l yd e t e r m i n e d c h a p t e r3i nt h i sc h a p t e rt h es p e c t r u mf o rl p m t s si se s t a b l i s h e d o no n e h a n d 、s i m i l a rr e c u r s i v ec o n s t r u c t i o n sf o rl p m t s sa n dt - p p m c s sa si nc h a p t e r2 啪l i s t e d t h e nt h ed i r e c tc o n s t r u c t i o n so fa1 - p p m c s ( 6 a ：4 ) ，ao - p p m c s ( 6 s ：3 ) a n ds o m es m a l ld e s i g n si nc h a p t e r2a r eu s e dt oe s t a b l i s ht h et d s t e n c eo fl p m t s ( 1 2 k + 9 ) s a n d l p m t s ( 1 2 k + 1 ) s o n t h e o t h e r h a n d ，f o r o d d i n t e g e r 口7 ，a s p e c i a l c o n s t r u c t i o nf r o mb o t ha l ll p m t s ( v ) a n da o l p m t s ( v ) t oa nl p m t s ( 2 v + 1 ) _ j 8s e tu p f i n n yt h es p e c t r u mf o rl p m t s si sd e t e r m i n e d e x t e n d e da b s t r a c t c h a p t e r4 i n t h i sc h a p t e r t r i p l i n gc o n s t r u c t i o nf o rl r d t s si sd i s p l a y e d a c o n c e p tc a l l e dd o u b l yt r a n s i t i v er e s o l v a b l ei d e m p o t e n tq u a s i g r o u p ( b r i e f l yd t r i q ) i si n t r o d u c e da n dad t r i q ( v ) i ss h o w nt oe x i s tf fa n do n l yi f3 va n dv 2 ( m o d4 ) t h e nat r i p l i n gc o n s t r u c t i o nf r o mb o t ha nl r d t s ( v ) a n dad t r i q ( v ) t oa n l r d t s ( 3 v ) i se s t a b l i s h e d m e a n w h i l ea ni n f i n i t ed a 辎o fl r d t s ( 4 3 “) i so b t a i n e d c h a p t e r5 i nt h i sc h a p t e rp r o d u c tc o n s t r u c t i o n sf o rl r m t s sa n dl r d t s s a r ed i s p l a y e d t h ee x i s t e n c eo fa nl r m t s ( u ) ( o rl n d t s ( u ) ) ，at r i q ( u ) ( o r d t m q ( t ，) ) a n da nl r ( v ) ( ad e s i g ni n t r o d u c e db yl e i ) i ss h o w n t 0g u a r a n t e et h e e x i s t e n c eo fa nl r m t s ( t 口) ( o rl n d t s ( t v ) ) m o r ei n f i n i t ee x i s t e n c ec l a s s e sa l e o b t a i n e db yu t i l i z i n gs u c hp r o d u c tc o n s t r u c t i o n s k e y w o r d s ：l a l g es e t ；m e n d e l s e h nt r i p l es y s t e m ；d i r e c t e dt r i p l es y s t e m ；p u r e ；c a n - d e l a b r as y s t e m ；t - p u r e l yp a t t i t i o n a b l e ；r e s o l v a b l e ；q u a s i g r o u p ；d o u b l yt r a n s i t i v e x a c k n o w l e d g e m e n t s a tt h eb e g i n n i n go ft h i st h e s i s ，1w i s ht oc o n v e ys o m eh e a r t f e l tt h a n k st oa l lt h o s e w h o s ek i n d n e s sa n da d v i c eh a v em a d et h i sw o r kp o s s i b l e ia mg r e a t l yi n d e b t e dt om ya d v i s o rp r o f e s s o rc h a n gy a n x u n i ti sh i mw h o l e dm et ot h ef a s c i n a t i n gf i e l do fc o m b i n a t o r i a ld e s i g n s w h a ti m p r e s s e sm em o s t i sh i sg o o dc o m m a n do fm a t h e m a t i c sa n dd e v o t i o nt os c i e n c e h eh a sa l w a y sb e e n e n c o u r a g i n g 。s u p p o r t i v ea n dp a t i e n ta n do f t e no f f e r i n gm ev a l u a b l ei n s t r u c t i o n so n e a c hp r o b l e mt h r o u g h o u tt h ep a s ts e v e r a ly e a r s 1w o u l dl i k et oe x p r e s sm ya p p r e c i a t i o nt od r j il i j u n ，a l li n t e l l i g e n ta n dd i l i g e n t y o u n gs c h o l a ri ns u z h o uu n i v e r s i t y , f o rh i 8c o o p e r a t i o ni nt h ef i r s tt w oc h a p t e r so f t h et h e s i s i 蛐a l s og r a t e f u lt op r o f e s s o rz h ul i ef o rh i se n c o u r a g e m e n ta n ds u g g e s t i o no n t h et o p i co fl a r g es e t so fp u r em e n d e l s o h nt r i p l es y s t e m s f i n a l l y , ie x t e n dm yt h a n k st om yh u s b a n da n dm yd a u g h t e r t h e i rl o v ea n d s u p p o r t ，a n df o r g i v e n e s sf o rt h eh o u r ss p e n to v e rp a p e r sm a d e m ei i l o r ed e d i c a t e dt o t h i sw o r k c h a p t e r1 i n t r o d u c l i o n 1 1 b a s i cd e f i n i t i o n s a8 t e i n e rt r i p l es f s t e mo fo r d e r 口( b r i e f l yb ys t s ( v ) ) i sa p a i r ( x ，舀) w h e r ex i sa v - s e ta n d 3j 8ac o l l e c t i o no f3 - s u b 6 e t so fx ，c a l l e db l o c k s ，s u c ht h a te v e r ym a o r d e r e d p a i ro fd i s t i n c tp o i n t so fx i sc o n t a i n e di ne x a c t l yo n eb l o c ko f 召 1 nw h a tf o l l o w s ，8 , 1 1o r d e r e dp a i ro fxi sa l w a y sa no r d e r e dp a i r y ) w h e r e 可t e x ac 剪c “c t r i p l e 扛，y ，z ) 0 n x i sas e t o f t h r e e o r d e r e dp a i r s ( ，) ，白，孑) a n d ( z ，) o fx at r a n s i t i v et r i p l e ( 茹，9 ，z ) 0 1 1x i s1 3 , s e to ft h r e eo r d e r e dp a i r s ( z ，) ， ( ，：) a n d ( ，：) o f x a no r i e n t e dt r i p l es ! t s t e mo fo r d e r i sap a i r ( x ，尽) w h e r exi sa , v - s e ta a t d8i s 8c o l l e c t i o no fc y c l i co rt r a n s i t i v et r i p l e s0 1 1x ，c a l l e db o c k s , s u c ht h a te v e r yo r d e r e d p a i ro fxb e l o n g st oe x a c t l yo i l eb l o c ko f8 i np a r t i c u l a r ，i ft h et 却1 嚣i n8 眦a l l c y c l i c ( o rt r a m i t i v e ) ，t h e n ( x ，8 ) i sc a l l e dam e n d e l s o h n ( o rc “r e c t e d ) t r i p l es 妒t e m a n dd e n o t e db ym t s ( v ) ( o rd t s ( 口) ) a nm t s ( v ) ( x ，棚i sc a l l e dp u r ea n dd e n o t e db yp m t s ( v ) i f ( 8 ，b ，c ) 4i m p f i e s 他6 ，n ) as i m i l a r l y , ap u r ed t s ( v ) ( p d t , c ( v ) i ns h o r t ) c x 棚i sad 粥( 口) i n w l a i e h ( 口，6 ，c ) 4i m p l i e s ( c 6 ，口) 圣 a ns t s ( v ) ( o r m ? s ( ) ，o r8d 了百( ) ) i sc a l l e dr e s o l v a b l ei fi t sb l o c k sc a nb e p a r t i t i o n e di n t os u b s e t , s ( c a l l e dp a r a e c a s s e s ) ，e a c he o i l t a i n i n ge v e r ye l e m e n t ；o fx 1 c h a p t e r1 i n t r o d u c t i o n e x a c t l yo n c e ar e s o l v a b l es t s ( v ) ，ar e s o l v a b l em t s ( v ) a n dar e s o l v a b l ed t s ( v ) a r ed e n o t e db yk ? s ( 口) ，r m t s ( v ) a n dr d t s ( v ) a n dt h en u m b e r so fp a r a l l e lc l a s s e s a r e 一1 ) 2 ，口一1a n d 一1r e s p e c t i v e l y a l a ，y es e to fs t s ( v ) s ( o rm t s ( v ) s ，o rd t s ( v ) s ) ，d e n o t e db yl s t s ( v ) ( o r l m t s ( v ) ，o rl d t s ( v ) ) ，i sac o l l e c t i o no f 口一2s t s ( v ) sf o r ”一2m t s ( v ) s ，o r 3 扣一2 ) d t s ( v ) s ) o nx s u c ht h a te v e r yt r i p l e ( o rc y c h ct r i p l e ，o rt r a n s i t i v et r i p l e ) o f xo c c l l r sa sab l o c k i ne x a c t l yo n eo f t h e 一2s t s ( v ) s ( o r 一2 m t s ( v ) s ，o r 3 ( v - 2 ) d t s ( v ) s ) t w os t s ( v ) s ( o rm t s ( v ) s ，o rp r s ( v ) s ) ( x ，棚a n d ( x ，回a r e c a l l e dd i