１ 基 本 概 念
定义 １ 两条长为 ｎ的路为 Ｐ ＝ 。ｉｔ２－．． Ｐ２＝Ｖ１口２－．．Ｖ ＋１’分别 连接 路 Ｐ１与 Ｐ２的顶 点 ｕｉ与
（ｉ＝ １，２，… ，ｎ＋１）所 得 到 的 图 ，称 为 长 为 ｎ的 梯 子 ，记为 。
定 义 ２ 设 ｍ ＋ １条 长 为 ｎ 的 路 Ｐｉ＝ ｎ／￣／２ …Ｕ ＋１（ｉ＝１，２，… ，ｍ，ｍ ＋１），连接 路 Ｐ 与 Ｐ 中的顶点 与 ．ｆ （ ＝ １，２，… ，ｍ； ＝ １，２，
Ａｂｓｔｒａｃｔ： Ｐｅｒｆｅｃｔ ｍａｔｃｈｉｎｇ ｃｏｕｎｔｉｎｇ ｐｒｏｂｌｅｍｓ ｇｒａｐｈ ｈａｓ ｂｅｅｎ ｐｒｏｖｅｎ ｔｏ ｂｅ ＮＰ－ｈａｒｄ．Ｔｏ ｇｅｔ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｐｅｒｆｅｃｔｌｙ ｍａｔｃｈｅｄ ｇｅｎｅｒａｌ ｇｒａｐｈ ｉｓ ｖｅｒｙ ｄｉｆｆ ｉｃｕｌｔ．Ｔｈｅ ｉｓｓｕｅ ｈａｓ ｉｍｐｏｒｔａｎｔ印 ｐｌｉｃａｔｉｏｎｓ ｉｎ ｐｒｏｔｅｉｎ ｓｔｒｕｃ－ ｔｕｒｅ ｐｒｅｄｉｃｔｉｏｎ，ｃｒ ｙｓｔａｌ ｐｈｙｓｉｃｓ，ｑｕａｎｔｕｍ ｃｈｅｍｉｓｔｒｙ ａｎｄ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ．Ｔｈｅ ｒｅｓｅａｒｃｈ ｏｎ ｔｈｉｓ ｉｓｓｕｅ ｈａｓ ｖｅｒ ｙ ｉｍｐｏｒｔａｎｔ ｔｈｅｏｒｅｔｉｃａ ｌ ａｎｄ ｐｒａｃｔｉｃａｌ ｓｉｇｎｉｆ ｉｃａｎｃｅ． Ｔ ｈ ｅ ｃｏｕｎｔｉｎｇ ｆｏｒｍｕｌａ ｏｆ ｔｈｅ ｐｅｒ ｆｅｃｔ ｍａｔｃｈｉｎｇ ｆｏｒ
第 ５６卷 第 ３期
中山大学学报 （自然科学 版）
２０１７年 ５月
ＡＣＴＡ ＳＣＩＥＮＴＩＡＲＵＭ ＮＡＴＵＲＡＬＩＵＭ ＵＮＩＶＥＲＳＩＴＡＴＩＳ ＳＵＮＹＡＴＳＥＮＩ
ＶＱ１．５６ Ｎｏ．３ Ｍａｖ ２０１７
ＤＯＩ：１０．１３４７１／ｊ．ｃｎｋｉ．ａｃｔａ．ＳｎＵＳ．２０１７．０３．００６
收 稿 日期 ：２０１６—０８—０５ 基金项 目：国家 自然科 学基金 （１１１７１１１４） 作者简 介 ：唐保 祥 （１９６１年生 ），男 ；研究方 向：图论和组合数学 ；Ｅ—ｍａｉｌ：ｔｂｘ０６１８＠ｓｉｎａ．ｔｏｍ
第 ３期
唐保祥等 ：３类特殊 图完美匹配数 的计算公式
３７
… ，／７，，／／，＋１） 所 得 的图 ，称 为 ｍ ｘ ｎ的棋 盘 。本 文 将 ／７／，Ｘ ｔ＇ ｂ的 棋 盘 记为 Ｑ 。
Ｔｈｅ ｃｏｕｎｔｉｎｇ ｆｏｒｍｕｌａ ｏｆ ｔｈｅ ｐｅｒｆｅｃｔ ｍ ａｔｃｈｉｎｇｓ ｏｆ ｔｈｒｅｅ ｔｙｐｅｓ ｏｆ ｓｐｅｃｉａｌ ｇｒａｐｈｓ
ＴＡＮ Ｇ Ｂａｏｘｉａｎｇ ，ＲＥＮ Ｈａｎ
（１．Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｓｔａｔｉｓｔｉｃｓ，Ｔｉａｎｓｈｕｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｓｈｕｉ ７４１００１，Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｅａｓｔ Ｃｈｉｎａ Ｎｏｒ ｍ ａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０００６２，Ｃｈｉｎａ）
定义 ３ 若图 ｃ的两个完美匹配 和 中有一 条边不同，贝 Ｕ称 Ｍ 和 是 Ｇ的两个不同完美匹配。
ｎ 个长为 ２的梯子 的顶点集 （ ）＝ ｛ ｍ
２×２棋盘 Ｑ 的顶点集为 （Ｑ ）＝ ｛／４， ，
２ｉ，
，
，２１￣１ ，Ｕ ｉ＋Ｉ ２１—１ ，Ｕ ｉ＋１２ｉ，／．ｔｉ＋１ ２ｉ＋１，Ｕｉ＋２ ２ｉ一１ ，／／＇ｉ＋２ ２ｉ，
ｇｒａｐｈｓ ３一 ，５一凡 ａｎｄ ２—２ｎＱ２ ２ ａ ｒｅ ｏｂｔａｉｎｅｄ ｂｙ ａｐｐｌｙｉｎｇ ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ，ｓｕｍｍａｔｉｏｎ ａｎｄ ｒｅ—ｒｅｃｕｒ－
ｓｉｏｎ ．Ｔｈｉｓ ｐｒｏｖｉｄｅｓ ｔｈｅ ｔｈｅｏｒｙ ｓｕｐｐｏｒｔ ｆｏｒ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｐｅｒｆｅｃｔ ｍａｔｃｈｉｎｇ ｉｎ ｇｒａｐｈ． Ｋｅｙ ｗｏｒｄｓ：ｐｅｒｆｅｃｔ ｍａｔｃｈｉｎｇ；ｌａｄｄｅｒ；ｒｅｃｕｒｒｅｎｃｅ ｒｅｌａｔｉｏｎ；ｃｈｅｓｓｂｏａｒｄ
３类特殊 图完美匹配数 的计算公 式
唐 保 祥 ，任 韩２
（１．天水师范学院数学与统计学院，甘肃 天水 ７４１００１； ２．华东师范大学数学系，上海 ２０００６２）
摘 要 ：图的完美对集计数问题已经被证实是 ＮＰ一难问题 ，因此要得到一般图的完美对集的数 目是非常困难 的。该 问题在 蛋白质结构 预测 、晶体物理学 、计算机 科学 和量子 化学 中都有重要 的应 用 ，对此 问题的研究 具有 非 常重要的理论价值和现实意义 。用划分 ，求 和 ，再 递推 的方法 分别给 出了 图 ３一 ，５一ｎ 和 ２—２ｎＱ： ｚ的 完美 匹配数 目的计算公式 ，为图 的完美 匹配 问题 的应用 提供了理论支持 。 关键 词 ：完美匹配；梯子；递推式；棋盘 中 图分类 号 ：Ｏ１５７．５ 文 献标 志码 ：Ａ 文章编 号 ：０５２９—６５７９（２０１７）０３—００３６—０５
图 的完 美 匹配 计 数 理 论 的 研 究 成 果 已经 在 化 学 、物理学 和 计算 机科 学 中得 到应用 ，图 的完 美 匹 配 的理 论在 很 多领域 有 广泛 应用 ，例 如 ：积 和式在 计算机科学 ，特别是计算复杂性理论 中有重要的地 位 ，二分 图 的完美 匹 配 的数 目可 以方 便 地表 示为 计 算积和式的值 ；它也是组合数学的思想源泉 ，因此 受到众多学者的关注ｕ ，本 文给 出了 ３类 图完 美匹配数 目的计算公式 ，文中所给方法 ，适合相同 结构 重复 出现 的很 多类 图完 美 匹配数 的求解 。
ห้องสมุดไป่ตู้
，
，
，
，
，
ｍ ｌ２ｌ＋ｔ｝（ｉ ＝ １，２，… ，２ ），将 棋 盘 ： 的 边
Ｕ ｉ＋１ ，２ｉ＋１ ｍ
＋ｌ 与 棋 盘
Ｑ ×２的边
／ｄ＇ｉ＋１２ｉ＋１“ｍ ＋１重 合 ，