组合设计大集问题PPT课件.ppt

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

1、组合设计的大集与超大集组合设计的大集与超大集已解决的和待解决的已解决的和待解决的康康 庆庆 德德 河北师范大学数学研究所河北师范大学数学研究所2009.7.29Kirkmans schoolgirl Kirkmans schoolgirl problemproblem(T.P.KirkmanT.P.Kirkman 18471847)SUN MON TUE WED SUN MON TUE WED THU FRI SATTHU FRI SAT 大集问题的起源和背景大集问题的起源和背景Thomas Penyngton Kirkman (英格兰教会的教区长)*2a,50,31,01,41,51,00,

2、10,11,20,40,61,30,60,21 SUN MON TUE WED THU FRI SAT (1850 Sylvester,Cayley 1974 Denniston1850 Sylvester,Cayley 1974 Denniston)3*经典三元系的大集与超大集经典三元系的大集与超大集 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

3、,OLT,OLT3 3;LESTS,LEMTS,LESTS,LEMTS,LEDTS.LEDTS.纯的有向三元系的大集与超大集纯的有向三元系的大集与超大集 LPMTS,LPDTS,OLPMTS,OLPDTS.LPMTS,LPDTS,OLPMTS,OLPDTS.可分解（几乎可分解）三元系的大集与超大集可分解（几乎可分解）三元系的大集与超大集 LKTS,LRMTS,LRDTS,OLKTS,OLRMTS,OLRDTS.LKTS,LRMTS,LRDTS,OLKTS,OLRMTS,OLRDTS.LARMTS,LARDTS,OLARMTS,OLARDTS.LARMTS,LARDTS,OLARMTS,OLAR

4、DTS.图设计的大集与超大集图设计的大集与超大集 路分解：P P3 3-LGD,OP-LGD,OP3 3-LGD,P-LGD,P3 3-OLGD,OP-OLGD,OP3 3-OLGD,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,).可分组设计的大集

5、可分组设计的大集 LGDD.LGDD.拉丁方的大集拉丁方的大集 LDILSLDILS,Golf design Golf design,.t t-设计的大集设计的大集 LSLS(t,k,v)(t,k,v)12:48:354基 本 文 献C.J.Colbourn&J.H.Dinitz,The CRC Handbook of Combinatorial Designs,CRC Press(Second Edition),2006.J.H.Dinitz&D.R.Stinson,Contemporary Design Theory A collection of surveys,Wiley,1992.Q

6、.D.Kang,On large sets of combinatorial designs,Advance of Mathematics,32(2003),269-284.*5A.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.*6Six types of triples and Six types of tr

7、iples and the corresponding triple the corresponding triple systemssystems*7The existence of The existence of triple systemstriple systems*8*9 经典三元系大集的存在谱*A short proof for LSTS(v)was given by L.Ji.*Lindner,Street,Colbourn,Rosa and Teirlinck also gave some results for LMTS(v).12:48:3610 经典三元系超大集的存在谱

8、*遗留问题：12:48:3611Large Sets of pure orinted triple systems*遗留问题:*12Overlarge Sets of pure orinted triple systems*遗留问题:*13B.B.其它三元系的大集与超大集其它三元系的大集与超大集 LTLT1 1,LT,LT2 2,LT,LT3 3,OLTOLT1 1,OLT,OLT2 2,OLT,OLT3 3,LESTS,LEMTS,LEDTS.LESTS,LEMTS,LEDTS.*14mixed triple systemsmixed triple systemsT T1 1,T T2 2,

9、T T3 3*15*16*17Conclusions for LTConclusions for LTi i and and OLTOLTi i*遗留问题遗留问题:Q.Q.Kang,Z.Kang,Z.Tian&L.Tian&L.Yuan,2003-Yuan,2003-20072007 12:48:3818A A classical triple classical triple consists of three distinct elements,but consists of three distinct elements,but an an extended triple extende

10、d triple is is allowed to contain repeated elements.allowed to contain repeated elements.STS,MTS,DTSSTS,MTS,DTS (LSTS,LMTS,LDTS LSTS,LMTS,LDTS)ESTS,EMTS,EDTS ESTS,EMTS,EDTS (LESTS,LEMTS,LEDTS LESTS,LEMTS,LEDTS).).Extended triple systemsExtended triple systems*19Examples ofExamples of LESTS*20Example

11、s ofExamples of LEMTS*21Examples ofExamples of LEDTS*22A construction forA construction for LEDTS(7)LEDTS(7)*23There exist There exist LEDTS(v)LEDTS(v)forforThere exist There exist LESTS(v)LESTS(v)and and LEMTS(v)LEMTS(v)*24C.C.可分解三元系的大集与超大集可分解三元系的大集与超大集 LKTS,LRMTS,LRDTS,LKTS,LRMTS,LRDTS,OLKTS,OLRMT

12、S,OLRDTS,OLKTS,OLRMTS,OLRDTS,LARMTS,LARDTS,LARMTS,LARDTS,OLARMTS,OLARDTS.OLARMTS,OLARDTS.*25L LKTSKTSL LRMTSRMTSL LRDTSRDTSL LARDTSARDTSL LARMTSARMTSRDTSRDTSKTSKTSOLOLKTSKTSOLOLRDTSRDTSARDTSARDTSOLOLARDTSARDTSARMTSARMTSOLOLARMTSARMTSRMTSRMTSOLOLRMTSRMTSDTSDTSMTSMTSSTSSTS12:48:4026The existence of tr

13、iple systemsThe existence of triple systems with with resolvabilityresolvability*27KTS(9)LKTS(9)*28Known LKTS(v)and small ordersKnown LKTS(v)and small orders 405405*29LRMTS(12)*30*31OLARDTS(10)*32Tripling constructions for Tripling constructions for LKTSLKTSProduct constructions for Product construc

14、tions for LKTSLKTS*33The existence for LKTS(v)Kirkman,Denniston,Schreiber,L.Wu,Y.Chang,Kirkman,Denniston,Schreiber,L.Wu,Y.Chang,G.Ge,L.Zhu,S.Zhang,J.Lei,L.Ji.G.Ge,L.Zhu,S.Zhang,J.Lei,L.Ji.before 2005before 2005 Q.Kang&L.Yuan,2007Q.Kang&L.Yuan,2007*34THANK YOUSUCCESS2023/2/1035可编辑Tripling constructio

15、ns for LRMTS and Tripling constructions for LRMTS and LRDTSLRDTSProduct constructions for LRMTS and Product constructions for LRMTS and LRDTSLRDTS*36The existence of LRMTS(v)and LRDTS(v)Q.Kang,J.Lei,Z.Tian,L.Yuan,Y.Chang,Q.Kang,J.Lei,Z.Tian,L.Yuan,Y.Chang,J.Zhou,J.Zhou,*372000 2000 Kang&Kang&TianTia

16、n 2006 2006 Kang&YuanKang&Yuan 2005 2005 Kang&Kang&YuanYuan 2002 2002 Kang&Kang&TianTian 12:48:43381996 1996 Kang&Kang&LeiLei D.D.图设计的大集与超大集图设计的大集与超大集P P3 3-LGD,OP-LGD,OP3 3-LGD,P-LGD,P3 3-OLGD,OP-OLGD,OP3 3-OLGD,-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-L

17、GD,C-LGD,C4 4-LGD.-LGD.HCD,LHPD,LDHCD,LDHPD,LCS(v,v-HCD,LHPD,LDHCD,LDHPD,LCS(v,v-1,).1,).*39Large sets of Large sets of P3-decompositions*40Large sets of Large sets of oriented P3-decompositions*41Large sets of Large sets of P3-decompositionsLarge sets of Large sets of oriented oriented P3-decomposi

18、tionsY.Zhang&Q.Kang,Y.Zhang&Q.Kang,2006 2006 Q.Kang&Y.Zhang,Q.Kang&Y.Zhang,2002200212:48:444243Overlarge sets ofOverlarge sets of oriented P3-decompositionsOverlarge sets ofOverlarge sets of P3-decompositionsY.Liu&Q.Kang,Y.Liu&Q.Kang,2009 2009 Y.Liu&Q.Kang,Y.Liu&Q.Kang,2008 2008 12:48:44Examples of

19、Examples of LGDLGD forfor cycle,path and star*44*4512:48:4546 在完全图中：Large Sets of Hamilton cycle(path)decompositions*无遗留问题*47Construction of LHCD2(v)*48在二分图中：Large Sets of Hamilton cycle(path)decompositions*无遗留问题*49 Large Sets of directeddirected Hamilton cycle(path)decompositions*遗留问题:1989 Kang1989

20、 Kang2005 Zhao&Kang2005 Zhao&Kang*50Tuscan squares of order 6 with or without a crosswithout crosswith crossRoman square*5112:48:4752A pair of relasional tuscan squares of order 7*53 Good tuscan square T -T and T-1 are relational*54问题:对于大于 19 的奇素数阶数 是否存在 a tuscan square with a crossa tuscan square w

21、ith a cross？是否存在 a pair of relationala pair of relational tuscan square tuscan square with a crosswith a cross？是否存在 a gooda good tuscan square with a crosstuscan square with a cross？(阶数=3=3 mod 4)mod 4)*55*56Large sets of Large sets of cycle systems问题:是否存在*57E.E.其它设计的大集与超大集其它设计的大集与超大集Latin squares,i

22、dempotent Latin squares,idempotent quasigroups,quasigroups,group divisible designs,group divisible designs,golf designs,t-designs.golf designs,t-designs.*58Large set of idempotent Latin squares of order 5*59Golf design Golf design of order 7(idempotent symmetric latin squares)*60Overlarge setsOverla

23、rge sets ofidempotent quasigroups*61Large sets of idempotent quasigroup 共轭不变子群共轭不变子群 大 集 超 大 集 幂等拉丁方大集 幂等拉丁方超大集 单位元群 n3,n6 n3,n6 幂等对称拉丁方大集 幂等对称拉丁方超大集 二阶子群 n 1 mod 2,n5 n 1 mod 2,n3 LMTS LMTS OLMTSOLMTS 三阶子群 n3,n6 n3,n6 n1,3 mod 6 n1,3 mod 6 LSTS LSTS OLSTSOLSTS 对称群S3 n3,n7 n3 n1,3 mod 6 n1,3 mod 6*62Large set of disjoint incomplete Latin squaresJ.Lei,Q.Kang,Y.Chang J.Lei,Q.Kang,Y.Chang 2001 2001 *64J.Lei,J.Lei,1997 1997 (t,t+1,v)-decomposition*65 (t,t+1,v)t,t+1,v)-decompositiondecomposition*66 ThanksThanks !12:48:5067THANK YOUSUCCESS2023/2/1068可编辑