钱建国，金贤安，杨维玲

(厦门大学数学科学学院，福建 厦门 361005)

图论中的计数问题可追溯到1857年Cayley第一次用树表示烷烃研究同分异构体的计数问题时所建立的递归公式[1].随后，对图结构计数问题的研究始终伴随着分析化学的应用，并由此催生了基于对称原理的离散结构计数理论，即：Redfield-Pólya计数理论[2].100多年来，包括图结构计数在内的各种图论计数问题得到了很好的发展并各自形成了较完整的理论体系，如匹配计数[3-5]、着色计数(色多项式)[6]及图计数[7]等理论，在统计物理、分析化学及信息生物学等领域得到了很好的应用.

本文主要对以张福基教授为代表的厦门大学组合图论研究团队20多年来在图论中的计数问题，以及在统计物理和分析化学中的应用方面的研究成果进行回顾.限于篇幅，在此仅包括部分具有代表性的工作，主要包括匹配计数、组合计数、拓扑图论、组合纽结理论、随机图理论、网络优化以及相关应用等方面的研究成果，并提出未来研究的展望.

1 匹配理论及应用

图的匹配理论是图论中非常活跃的研究领域.著名图论专家Lovsz(Wolf奖及Abel奖得主，国际数学家大会ICM邀请报告人，曾任国际数学联盟主席)的专著《匹配理论》对匹配理论进行了系统的论述[8].2006年Fields奖获得者Okounkov的获奖工作之一也与匹配计数理论有着密切的关系[4].在应用方面，匹配理论中的匹配计数问题等价于统计物理中的二聚体(Dimer)问题，是统计物理计算可解模型的热门研究对……