匹配分配格的分解定理

《匹配分配格的分解定理》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、兰州人学研究生学位论文捅要平面二部图的完美匹配集合上的分配格结构已经被建立．如果一个格同构于这样的分配格，则称它为匹配分配格(简记为MDL)．我们已经知道并不是所有的有限分配格都是MDLs，因此很自然地需要刻画MDL．在本文中，我们得到了关于MDL的一些基本结果．如果平面二部图G是基本的，则相应的MDL是既约的．进而。关于MDL的一个分解定理被得到：即一个有限分配格(FDL)是MDL当且仅当它的一个卡氏积分解中的每一因予是MDL．因此．只要研究清楚既约的MDL，就可以判断能进行卡氏积分解的分配格是否为MDL．从同构的角度看，则只需对平面基本二部图进行研究．作为应用，本文也给出了两类既约的MDL

2、s：分别是J(m×n)与J(Z。)，其中m×n是m·元链和n．元链的卡氏积，而z。是具有元素{zl，⋯，‰}以及覆盖关系zⅨ一l<3：2／和X21>_X21+1的“zigzag”偏序集．关键词：直积分解，分配格，完美匹配，平面二部图，偏序集，z-变换图兰州大学研究生学位论文AbstractAdistributivelatticestructurehasbeenestablishedOOthesetofperfectmatchingsofanyplanebipartitegraph．Alatticeiscalledmatchingdistributivelattice(simplyMDL)ifi

3、tisisomorphictosuchadistributivelattice．ItisnaturaltocharacterizeanMDLbecausenotalldistribufivelatticesaleMDLs．Inthispaper,weobtainedsomefundamentalresultsonMDL．IfaplanebipartitegraphGiselementary,thenthecorrespondingMDLisirreducible．Funher'adecom—positionthCOl'eraonMDLiSobtained：afinitedistributive

4、lattice(FDL)iSanMDLifandonlyifeachfactorinacartesianproductdecompositionisallMDL．Thusweonlyneedconsiderirreducibledistributivelatticesthatcorrespondtoplanelementarybipar-tiregraphs．Asapplication，twotypesofirreducibleMDLsaIBpresented：J(m×n)andJ(Zn)，wherem×ndenotesthecartesianproductbetweenrn-elementc

5、hainandn·elementchain，andzn)isa“zigzag”posetwithelements缸l，⋯，xn}andcovertelationso缸一l

6、据，观点等，均己明确注明出处．除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果．对本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式标明．本声明的法律责任由本人承担．论文作者签名：扭徨垒同期：趁!￡：￡蔓』兰州人学研究生学位论文关于学位论文使用授权的声明本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大学．本人完全了解兰州大学有关保存．使用学位论文的规定同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和汇编本学位

7、论文．本人离校后发表，使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学．保密论文在解密后应遵守此规定．论文作者签名：蕴趁导师签名：—L避兰州大学研究生学位论文第一章引言设G是一个有限阶的简单图，顶点集为y(G)，边集为E(G)．M称为G的一个完美匹配(perfectmatching)或者1．因子(1-factor)是指饱和G中所有顶点的独立边集．在图中，完美匹配M的所有