2类图完美匹配的数目

《2类图完美匹配的数目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３６卷第５期西南师范大学学报（自然科学版）２０１１年１０月Ｖｏｌ．３６Ｎｏ．５ＪｏｕｒｎａｌｏｆＳｏｕｔｈｗｅｓｔＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｏｃｔ．２０１１文章编号：１０００－５４７１（２０１１）０５－００１６－０６①２类图完美匹配的数目唐保祥１，２，任韩２１．天水师范学院数学与统计学院，甘肃天水７４１００１；２．华东师范大学数学系，上海２０００６２摘要：一般图的完美匹配计数问题是ＮＰ－困难的．用划分、求和、再递推的方法给出了２类特殊

2、图完美匹配数目的计算公式．所给出的方法，可以计算出许多二分图的所有完美匹配的数目．作为应用，计算出了一类棋盘１×２的多米诺覆盖数目．关键词：线性递推式；四角系统；棋盘；完美匹配中图分类号：Ｏ１５７．５文献标志码：Ａ本文所指的图均是有限简单无向标号图（即顶点间是有区别的），未给出的定义见文献［１］．图的完美匹配数作为一个很重要的拓扑指标，已经在多个领域得到应用．例如，估计共振能量和π－电［２－３］子能量，计算鲍林键级（ｐａｕｌｉｎｇｂｏｎｄｏｒｄｅｒ）等．物理学家Ｋａｓｔｅｌｅｙｎ用匹配理论研究磁学

3、伊辛（Ｉｓｉｎｇ）［４－５］模型时，首先提出用Ｐｆａｆｆｉａｎ法计算图的完美匹配个数．目前，图的完美匹配计数已经引起了众多数学［６－８］家、物理学家和化学家的广泛关注．遗憾的是，Ｖａｌｉａｎｔ在１９７９年提出了：一个图（即使是偶图）的完美匹配计数是ＮＰ－难问题．四角系统作为特殊图类，它的完美匹配计数既与组合理论中棋盘的多米诺覆盖问［９－１０］题有关，又与统计晶体物理学中的ｄｉｍｅｒ问题有关．目前，有文献对一些特殊图类给出了完美匹配的［１１－１７］计数方法．本文给出了２类特殊图完美匹配数的显式表达式

4、．［１５］定义１设Ｇ是２－连通平面图，其每个内部面都是边长为１的单位正方形（又称细胞），且每条边至少属于一个细胞，则称Ｇ为四角系统．定义２若图Ｇ的２个完美匹配Ｍ１和Ｍ２中有一条边不同，则称Ｍ１和Ｍ２是Ｇ的２个不同完美匹配．设Ｑｍ×ｎ表示ｍ×ｎ的棋盘，其中Ｖ（Ｑｍ×ｎ）＝｛ｕｉｊ｜１≤ｉ≤ｍ＋１，１≤ｊ≤ｎ＋１｝，Ｅ（Ｑｍ×ｎ）＝｛ｕｉｊｕｋｌ｜ｉ＝ｋ且ｌ＝ｊ＋１，或ｊ＝ｌ且ｋ＝ｉ＋１，１≤ｉ，ｋ≤ｍ＋１，１≤ｊ，ｌ≤ｎ＋１｝．容易知道ｍ×ｎ的棋盘Ｑｍ×ｎ有完美匹配的充要条件是ｍ和ｎ中至少有一个是奇

5、数．定理１设ｆ（ｎ）表示３×ｎ（ｎ≥１）的棋盘Ｑ３×ｎ（如图１所示）的所有不同的完美匹配数，则ｆ（ｎ）＝ｆ（ｎ－１）＋５ｆ（ｎ－２）＋ｆ（ｎ－３）－ｆ（ｎ－４），其中图１棋盘Ｑ３×ｎｆ（１）＝５ｆ（２）＝１１ｆ（３）＝３６ｆ（４）＝９５ｎｎ烄１－槡２９－槡１４－２槡２９烌烄１－槡２９＋槡１４－２槡２９烌ｆ（ｎ）＝ｃ１·＋ｃ２·＋烆４烎烆４烎①收稿日期：２０１０－０６－０８基金项目：国家自然科学基金（１０６７１０７３）；上海市自然科学基金（０７ＸＤ１４０１１）；上海市重点学科建设基金（Ｂ４０７）．作

6、者简介：唐保祥（１９６１－），男，甘肃天水人，副教授，主要从事图论和组合数学的研究．第５期唐保祥，等：２类图完美匹配的数目１７ｎｎｃ烄槡２２９烌烄１＋槡２９＋槡１４＋２槡２９烌３·１＋槡２９－１４＋槡＋ｃ４·烆４烎烆４烎５ＢＣＤ－１１（ＢＣ＋ＣＤ＋ＤＢ）＋３６（Ｂ＋Ｃ＋Ｄ）－９５ｃ１＝Ａ（Ｂ－Ａ）（Ｃ－Ａ）（Ｄ－Ａ）－５ＡＣＤ＋１１（ＡＣ＋ＣＤ＋ＤＡ）－３６（Ａ＋Ｃ＋Ｄ）＋９５ｃ２＝Ｂ（Ｂ－Ａ）（Ｃ－Ｂ）（Ｄ－Ｂ）５ＡＢＤ－１１（ＡＢ＋ＢＤ＋ＤＡ）＋３６（Ａ＋Ｂ＋Ｄ）－９５ｃ３＝Ｃ（Ｃ－Ａ）（Ｃ－

7、Ｂ）（Ｄ－Ｃ）－５ＡＢＣ＋１１（ＡＢ＋ＢＣ＋ＣＡ）－３６（Ａ＋Ｂ＋Ｃ）＋９５ｃ４＝Ｄ（Ｄ－Ａ）（Ｄ－Ｂ）（Ｄ－Ｃ）１－槡２９－槡１４－２槡２９１－槡２９＋槡１４－２槡２９Ａ＝Ｂ＝４４１＋槡２９－槡１４＋２槡２９１＋槡２９＋槡１４＋２槡２９Ｃ＝Ｄ＝４４证设Ｑ３×ｎ的所有完美匹配的集合为Ｍ，ＭｉＭ（ｉ＝１，２，３），其中ｕ１１ｕ１２∈Ｍ１，ｕ１２ｕ２２∈Ｍ２，ｕ１２ｕ１３∈Ｍ３．显然有Ｍｉ≠（ｉ＝１，２，３），且Ｍｉ∩Ｍｊ＝（ｉ≠ｊ，１≤ｉ，ｊ≤３），Ｍ＝Ｍ１∪Ｍ２∪Ｍ３．于是ｆ（ｎ）＝｜Ｍ｜＝

8、｜Ｍ１｜＋｜Ｍ２｜＋｜Ｍ３｜．由ｆ（ｎ）的定义容易知道，ｆ（１）＝５，ｆ（２）＝１１．设ｕ和ｖ是２个孤立顶点，令Ｇ１＝Ｑ３×ｎ＋ｕｖ＋ｕｕ１２＋ｖｕ１３，Ｇ１如图２所示；Ｇ２＝Ｑ３×ｎ＋ｕｖ＋ｕｕ１３＋ｖｕ１４，Ｇ２如图３所示．显然图Ｇ１和Ｇ２存在完美匹配．图２Ｇ１图图３Ｇ２图令ｈ（ｎ）和ｇ（ｎ）分别表示图Ｇ１和Ｇ２的完美匹配数．由Ｍｉ（ｉ＝１，２，３），Ｇ１和Ｇ２的定义知：｜Ｍ１｜＝ｇ（ｎ－１）｜Ｍ２｜＝ｆ（ｎ－２）＋ｇ（ｎ－２）｜Ｍ３｜＝ｈ（ｎ－２）于是ｆ（ｎ）＝ｇ（ｎ－１）＋