组合设计大集问题.pptx

《组合设计大集问题.pptx》由会员分享，可在线阅读，更多相关《组合设计大集问题.pptx（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、Kirkmans schoolgirl problemKirkmans schoolgirl problem(T.P.Kirkman 1847)SUN MON TUE WED THU FRI SAT 大集问题的起源和背景大集问题的起源和背景Thomas Penyngton Kirkman (英格兰教会的教区长)19:02:201第1页/共66页a,50,31,01,41,51,00,10,11,20,40,61,30,60,21 SUN MON TUE WED THU FRI SAT (1850 Sylvester,Cayley 1974 Denniston1850 Sylvester,Cay

2、ley 1974 Denniston)219:02:20第2页/共66页经典三元系的大集与超大集经典三元系的大集与超大集 LSTS,LMTS,LDTS,LHTS,OLSTS,OLMTS,OLDTS.LSTS,LMTS,LDTS,LHTS,OLSTS,OLMTS,OLDTS.其它三元系的大集与超大集其它三元系的大集与超大集 LTLT1 1,LT,LT2 2,LT,LT3 3,OLTOLT1 1,OLT,OLT2 2,OLT,OLT3 3;LESTS,LEMTS,LESTS,LEMTS,LEDTS.LEDTS.纯的有向三元系的大集与超大集纯的有向三元系的大集与超大集 LPMTS,LPDTS,OLP

3、MTS,OLPDTS.LPMTS,LPDTS,OLPMTS,OLPDTS.可分解（几乎可分解）三元系的大集与超大集可分解（几乎可分解）三元系的大集与超大集 LKTS,LRMTS,LRDTS,OLKTS,OLRMTS,OLRDTS.LKTS,LRMTS,LRDTS,OLKTS,OLRMTS,OLRDTS.LARMTS,LARDTS,OLARMTS,OLARDTS.LARMTS,LARDTS,OLARMTS,OLARDTS.图设计的大集与超大集图设计的大集与超大集 路分解：P P3 3-LGD,OP-LGD,OP3 3-LGD,P-LGD,P3 3-OLGD,OP-OLGD,OP3 3-OLGD,

4、P-OLGD,P4 4-LGD,P-LGD,Pk k-LGD.LGD.星(圈)分解：K K 1,31,3-LGD,K-LGD,K 1,41,4-LGD,K-LGD,K 1,k1,k-LGD;-LGD;C C4 4-LGD.-LGD.Hamilton圈(路)分解：LHCD,LHPD,LDHCD,LDHPD;LHCD,LHPD,LDHCD,LDHPD;LCS(v,v-1,).LCS(v,v-1,).可分组设计的大集可分组设计的大集 LGDD.LGDD.拉丁方的大集拉丁方的大集 LDILSLDILS,Golf Golf designdesign,.t-设计的大集设计的大集 LSLS(t,k,v)(t

5、,k,v)19:02:203第3页/共66页基基 本本 文文 献献C.J.Colbourn&J.H.Dinitz,TheCRCHandbookofCombinatorialDesigns,CRCPress(SecondEdition),2006.J.H.Dinitz&D.R.Stinson,ContemporaryDesignTheoryAcollectionofsurveys,Wiley,1992.Q.D.Kang,Onlargesetsofcombinatorialdesigns,AdvanceofMathematics,32(2003),269-284.19:02:204第4页/共66页

6、A.A.经典三元系的大集与超大集经典三元系的大集与超大集 LSTS,LMTS,LDTS,LHTS,LSTS,LMTS,LDTS,LHTS,OLSTS,OLMTS,OLDTS,OLHTS,OLSTS,OLMTS,OLDTS,OLHTS,LPMTS,LPDTS,OLPMTS,OLPDTS.LPMTS,LPDTS,OLPMTS,OLPDTS.19:02:205第5页/共66页Six types of triples and Six types of triples and the corresponding triple systemsthe corresponding triple systems

7、19:02:206第6页/共66页The existence of triple systemsThe existence of triple systems19:02:217第7页/共66页19:02:218第8页/共66页 经典三元系大集的存在谱经典三元系大集的存在谱*A short proof for LSTS(v)was given by L.Ji.*Lindner,Street,Colbourn,Rosa and Teirlinck also gave some results for LMTS(v).19:02:219第9页/共66页 经典三元系超大集的存在经典三元系超大集的存在谱

8、谱*遗留问题：19:02:2110第10页/共66页Large Sets ofLarge Sets of pure orinted triple systems*遗留问题:19:02:2211第11页/共66页Overlarge Sets ofOverlarge Sets of pure orinted triple systems*遗留问题:19:02:2212第12页/共66页B.B.其它三元系的大集与超大其它三元系的大集与超大集集 LTLT1 1,LT,LT2 2,LT,LT3 3,OLTOLT1 1,OLT,OLT2 2,OLT,OLT3 3,LESTS,LEMTS,LEDTS.LES

9、TS,LEMTS,LEDTS.19:02:2213第13页/共66页mixed triple systemsmixed triple systemsT T1 1,T T2 2,T T3 319:02:2214第14页/共66页19:02:2215第15页/共66页19:02:2216第16页/共66页Conclusions for LTConclusions for LTi i and and OLTOLTi i*遗留问题遗留问题:Q.Kang,Z.Tian&L.Yuan,2003-2007 19:02:2317第17页/共66页AAclassicaltripleclassicaltriple

10、consistsofthreedistinctelements,butconsistsofthreedistinctelements,butananextendedtripleextendedtripleisallowedtocontainrepeatedisallowedtocontainrepeatedelements.elements.STS,MTS,DTSSTS,MTS,DTS(LSTS,LMTS,LDTSLSTS,LMTS,LDTS)ESTS,EMTS,EDTSESTS,EMTS,EDTS(LESTS,LEMTS,LEDTSLESTS,LEMTS,LEDTS).).Extended

11、triple systemsExtended triple systems19:02:2318第18页/共66页Examples ofExamples ofExamples ofExamples of LESTSLESTS19:02:2319第19页/共66页Examples ofExamples of LEMTS19:02:2320第20页/共66页Examples ofExamples of LEDTSLEDTS19:02:2421第21页/共66页A construction forA construction for LEDTS(7)LEDTS(7)19:02:2422第22页/共66

12、页There exist There exist LEDTS(v)forforThere exist There exist LESTS(v)and and LEMTS(v)19:02:2523第23页/共66页C.C.可分解三元系的大集与超大可分解三元系的大集与超大集集 LKTS,LRMTS,LRDTS,LKTS,LRMTS,LRDTS,OLKTS,OLRMTS,OLRDTS,OLKTS,OLRMTS,OLRDTS,LARMTS,LARDTS,LARMTS,LARDTS,OLARMTS,OLARDTS.OLARMTS,OLARDTS.19:02:2524第24页/共66页LKTSLRMTSL

13、RDTSLARDTSLARMTSRDTSKTSOLKTSOLRDTSARDTSOLARDTSARMTSOLARMTSRMTSOLRMTSDTSMTSSTS19:02:2525第25页/共66页The existence of triple systemsThe existence of triple systems with resolvabilitywith resolvability19:02:2526第26页/共66页KTS(9)LKTS(9)19:02:2527第27页/共66页Known LKTS(v)and small orders 40519:02:2528第28页/共66页LR

14、MTS(12)LRMTS(12)19:02:2629第29页/共66页19:02:2630第30页/共66页OLARDTS(10)OLARDTS(10)19:02:2631第31页/共66页Tripling constructions for LKTSTripling constructions for LKTSProduct constructions for LKTSProduct constructions for LKTS19:02:2732第32页/共66页The existence for The existence for LKTS(v)Kirkman,Denniston,Sch

15、reiber,L.Wu,Y.Chang,G.Ge,L.Zhu,S.Zhang,J.Lei,L.Ji.before 2005 Q.Kang&L.Yuan,2007 19:02:2733第33页/共66页Tripling constructions for LRMTS and Tripling constructions for LRMTS and LRDTSLRDTSProduct constructions for LRMTS and LRDTSProduct constructions for LRMTS and LRDTS19:02:2734第34页/共66页The existence o

16、f LRMTS(v)and LRDTS(v)The existence of LRMTS(v)and LRDTS(v)Q.Kang,J.Lei,Z.Tian,L.Yuan,Y.Chang,J.Zhou,19:02:2735第35页/共66页2000 Kang&Tian 2006 Kang&Yuan 2005 Kang&Yuan 2002 Kang&Tian 19:02:28361996 Kang&Lei 第36页/共66页D.D.图设计的大集与超大集图设计的大集与超大集P P3 3-LGD,OP-LGD,OP3 3-LGD,P-LGD,P3 3-OLGD,OP-OLGD,OP3 3-OLGD,

17、-OLGD,P P4 4-LGD,P-LGD,Pk k-LGD.-LGD.K K 1,31,3-LGD,K-LGD,K 1,41,4-LGD,K-LGD,K 1,k1,k-LGD,C-LGD,C4 4-LGD.-LGD.HCD,LHPD,LDHCD,LDHPD,LCS(v,v-HCD,LHPD,LDHCD,LDHPD,LCS(v,v-1,).1,).19:02:2837第37页/共66页Large sets of Large sets of P P3 3-decompositions-decompositions19:02:2838第38页/共66页Large sets of Large se

18、ts of oriented Poriented P3 3-decompositions-decompositions19:02:2839第39页/共66页Large sets of Large sets of P3-decompositionsLarge sets of Large sets of oriented oriented P3-decompositionsY.Zhang&Q.Kang,2006 Q.Kang&Y.Zhang,200219:02:2940第40页/共66页41Overlarge sets ofOverlarge sets of oriented P3-decompo

19、sitionsOverlarge sets ofOverlarge sets of P3-decompositionsY.Liu&Q.Kang,2009 Y.Liu&Q.Kang,2008 19:02:29第41页/共66页Examples of Examples of LGDLGD forfor cycle,path cycle,path and starand star19:02:2942第42页/共66页19:02:2943第43页/共66页19:02:3044第44页/共66页 在完全图中：在完全图中：Large Sets ofLarge Sets of Hamilton cycle(

20、path)decompositions*无遗留问题19:02:3045第45页/共66页Construction of LHCD2(v)19:02:3046第46页/共66页在二分图中：在二分图中：Large Sets ofLarge Sets of Hamilton cycle(path)decompositions*无遗留问题19:02:3047第47页/共66页 Large Sets ofLarge Sets ofLarge Sets ofLarge Sets of directeddirected Hamilton cycle(path)decompositions*遗留问题:1989

21、 Kang2005 Zhao&Kang 19:02:3148第48页/共66页Tuscan squares of order 6 Tuscan squares of order 6 with or without a crosswith or without a crosswithout crosswith crossRoman square19:02:3149第49页/共66页19:02:3150第50页/共66页A pair of relasional tuscan squares of A pair of relasional tuscan squares of order 7 orde

22、r 7 19:02:3151第51页/共66页 Good tuscan square Good tuscan square T T -T T andand T T-1-1 are are relationalrelational19:02:3252第52页/共66页问题:对于大于 19 的奇素数阶数 是否存在 a tuscan square with a cross？是否存在 a pair of relational tuscan square with a cross？是否存在 a good tuscan square with a cross？(阶数=3=3 mod 4)mod 4)19:

23、02:3253第53页/共66页19:02:3354Large sets of Large sets of cycle systems第54页/共66页问题:是否存在19:02:3355第55页/共66页E.E.其它设计的大集与超大集其它设计的大集与超大集Latin squares,idempotent quasigroups,Latin squares,idempotent quasigroups,group divisible designs,group divisible designs,golf designs,t-designs.golf designs,t-designs.19:0

24、2:3356第56页/共66页Large set of idempotent Latin squares of order 5Large set of idempotent Latin squares of order 519:02:3357第57页/共66页Golf design of order 7(idempotent symmetric latin squares)19:02:3458第58页/共66页Overlarge setsOverlarge sets of ofidempotent quasigroups19:02:3459第59页/共66页Large sets of idem

25、potent quasigroupLarge sets of idempotent quasigroup 共轭不变子群共轭不变子群 大 集 超 大 集 幂等拉丁方大集 幂等拉丁方超大集 单位元群 n3,n6 n3,n6 幂等对称拉丁方大集 幂等对称拉丁方超大集 二阶子群 n 1 mod 2,n5 n 1 mod 2,n3 LMTS OLMTSLMTS OLMTS 三阶子群 n3,n6 n3,n6 n1,3 mod 6 n1,3 mod 6 LSTS OLSTSLSTS OLSTS 对称群S3 n3,n7 n3 n1,3 mod 6 n1,3 mod 6 19:02:3460第60页/共66页Large set of disjoint incomplete Latin squaresJ.Lei,Q.Kang,Y.Chang 2001 第61页/共66页19:02:3562J.Lei,1997 第62页/共66页(t,tt,t+1+1,v,v)-decompositiondecomposition19:02:3563第63页/共66页 (t,t+1,v)-decompositiondecomposition19:02:3564第64页/共66页 Thanks!19:02:3665第65页/共66页19:02:3666感谢您的观看！第66页/共66页