图论中的计数理论及其应用

2021-04-17钱建国金贤安杨维玲

厦门大学学报（自然科学版） 2021年3期

钱建国，金贤安，杨维玲

(厦门大学数学科学学院，福建厦门 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)问题，是统计物理计算可解模型的热门研究对象[9-11].此外，匹配理论也是量子化学家研究芳香碳氢化合物的重要工具之一[12-13]，如Kekule结构及Clar 覆盖[14].

本团队运用组合学、代数、概率及Pfaffian定向等理论方法，在匹配计数问题的理论研究及应用取得了许多突破性的成果，丰富了匹配理论.

1.1 匹配计数

匹配计数是匹配理论中的一个核心问题，也是一个非常难的问题.Robertson等[3]和Kenyon等[4]先后发表文章对此进行论述.在匹配计数理论的研究中，来源于积和式计算问题的Pfaffian定向是完美匹配计数的一个强有力工具：若一个图有Pfaffian定向，那么就可以在多项式时间内计算其完美匹配数.然而，确定一个图是否有Pfaffian定向也是非确定性多项式(NP)-困难的.2006年Thomas[5]提出了值得进一步研究的若干重要问题(猜想7.5，9.5).该问题被列入在教育部、科学技术部、中国科学院和国家自然科学基金委联合编撰的《10 000个科学难题(数学卷)》中，相当程度上代表了我国相关学科研究的前沿问题，不仅具有深刻的理论意义，而且在统计物理、量子化学中也将具有很好的应用价值.

本团队多年来一直致力于图的Pfaffian定向及其应用问题的探索，解决了一系列经典图类的Pfaffian定向问题[15-17].确定一个图的Pfaffian定向的本质是要研究对应的匹配覆盖的brick结构.Norine 和Thomas猜想每个极小brick的三度点至少有4个，我们证明了该猜想[18].进一步地，Lucchesi等猜想：三正则solid brick中的任意两个奇圈必相交.我们证明了一类三正则solid brick存在两个点不交的奇圈，从而否定了该猜想[19].此外，我们刻画了边等价类阶数可以任意大的匹配覆盖图，推广了Lovsz关于brick中的边等价类中最多含2条边的结果，回答了Lu等[20-21]提出的问题.这些猜想和问题的解决，有助于更好地认识brick结构，推动图的Pfaffian定向问题的进展.

美国数学家Ciucu利用纯组合方法研究了具有反射对称的平面二部图的完美匹配的计数问题，得到了匹配因子定理，但该结果要求对称轴不能与图的边相交.我们运用组合与Pfaffian定向相结合的方法，结合代数理论，对多种具有反射对称图的完美匹配的计数问题进行了全面而又系统的研究，给出了这些对称图的完美匹配的计数公式[22-23].进一步，运用这一方法以及对称图的匹配计数理论也得到了反射对称图的生成树数目的一个因子分解定理，并首次建立了树的匹配数与Wiener数这两个看似无关的拓扑指标之间的关系[24-25].Pfaffian定向不仅在匹配计数理论中扮演着重要角色，也反过来促进了积和式问题的研究.Borowiecki和Jozwiak于1981年提出了刻画匹配计数理论积和式多项式只有纯虚数根的所有图的公开问题，但直到现在此问题还没有完全解决；本团队运用Pfaffian定向的方法部分地解决了此问题，是迄今为止此问题的最好结果[26].

1.2 应用

匹配及其计数是图论最具应用背景的理论之一，在优化理论、统计物理及分析化学中扮演着重要的角色.

在统计物理中单体-二聚体(Monomer-Dimer)问题等价于匹配理论中的匹配多项式问题.然而，二维以上(含二维)的大规模图的Monomer-Dimer问题之前从未得到过精确计算公式，已有结果都是通过数字模拟的方法得到近似解.我们运用Pfaffian定向与组合计数相结合的方法给出了一类任意维数的大规模图的Monomer-Dimer构型的精确解，这是迄今为止有关此问题的第一个非平凡的精确解[27].此外，我们得到了克莱因瓶上网格图Dimer构型的数目[28]; 计算了几类化学图的Kekule结构数[29]；得到了一些平面网格图、若干环面上图的完美匹配数[20]；推广了著名物理学家Kasteleyn的一个被引用880多次的经典结果，该结果被收录于HandbookofProductGraphs一书中；给出了多米诺图完美匹配数的线性算法及不存在线性算法的刻画[30].

自C60被人工合成以来，石墨烯成为了现代材料科学的一个热点.本团队运用转移矩阵、积和式及随机过程等理论方法给出了纳米管、随机石墨烯的Dimer与Monomer-Dimer的计数公式[31-35].特别是在文献[31-32]中，运用统计的方法解决了随机生长石墨烯Monomer-Dimer的计数问题，从而建立了石墨烯绳随机生长过程的数学模型.

Clar芳香六隅体理论是著名化学家Clar[14]于1972年提出的理论模型.基于分子轨道的性质，芳香性反映一定类型的共轭系统的特定稳定性.从多种实验测量计算所得到的共振能表示在不同的Kekule(完美匹配)结构之间互相转换所得到或失去的能量，也表示共轭系统的特定稳定性.在半经验的分子价-键视角中，处理这个问题的不同价-键模型相继建立[38].在这些模型中，Clar 芳香六隅体理论描述了苯类碳氢化合物的芳香性.在估算分子共振能的多种方法中，化学家Randic在1976年建立的共轭圈模型是基于共轭圈的组合计数[39]，它能用于多环共轭系统的芳香性和共轭的研究.从Clar芳香六隅体理论和Randic共轭圈模型，能够发展出一系列有化学背景的数学模型和数学计算方法.六隅体多项式、Clar多项式、Clar覆盖多项式和线性独立极小共轭圈多项式等被相继引入[40-42].六隅体结构，Kekule结构以及线性独立极小共轭圈结构的性质被深入研究.这些多项式的计算和多种结构的性质研究提出了非常有趣并具有挑战性的研究课题.本团队在上述课题的研究中取得丰富的开创性研究成果[41-45]，其中张和平和张福基教授首次引入的Clar覆盖多项式[41]被国际数学化学界称为Zhang-Zhang多项式[46].郭晓峰等首次引入了线性独立极小共轭圈多项式，并对此多项式的递归计算方法和解析计算方法进行了较深入的探索，进而在k-共振苯系统，k-共振冠状苯系统和k-圈共振图的研究中得到一系列新成果[46-50].

2 组合计数

组合计数是古老且有广泛应用背景的理论.本团队在组合计数理论，特别是容斥理论、Pólya计数理论及应用方面取得了丰硕的成果，部分成果具有较好的创新性.

2.1 容斥理论及应用

容斥原理是组合计数最经典和最基本的方法之一，是组合数学教科书中的基本内容.在容斥表达式中，基于容斥原理的“项”多达指数量级，其中大多数是重复计算的.由此产生了一个自然而深刻的问题：是否有可能使一些项事先相互对消而使最终的计算简化？1932 年著名数学家 Whitney 建立了计算图的色多项式的破圈定理[6]，对这个问题给予了一个肯定的回答，由此开创了容斥对消(inclusion-exclusion cancellation)理论.特别对色多项式而言，破圈结构实现了“完全对消”并据此获得了色多项式系数的组合解释.Whitney的破圈定理对图多项式理论无疑产生了深刻的影响，不仅在图的色多项式理论中扮演着重要角色，也被推广到超图、符号图、拟阵的多项式理论以及格论的研究中[51-52].

本团队首次将容斥对消理论用于图的列表着色计数问题[52]，大幅改进了 Donner 和 Thomassen 的重要结果.这一方法也为研究更一般图类(如超图、符号图等)的(列表)着色计数问题提供了很好的借鉴.在文献[53]中本团队将上述成果推广到超图上，其技术难点是如何对消超图结构中的边子集.为此，我们对超图的圈结构进行了合理的刻画，对超图“圈”的概念给予了新的诠释.文献[54]运用容斥对消理论研究符号图着色的对偶问题，首次给出了符号图处处非零流计数的容斥对消表达式，并就奇数的情形给出了符号图流多项式系数的一个组合解释.

破圈定理所蕴含的容斥对消思想也发展了组合学中经典的容斥原理，并进一步获得了各种形式的推广.最具代表的是Narushima[55]、Dohmen等[56]、Brylawski[57]以及Naiman等[58]分别从组合学和代数拓扑的角度所建立的定义在一般度量空间上的容斥对消理论，其主要思想是对指标集进行排序(index ordering，全序或偏序或格系统)，进而运用单纯复形的计数理论对重复计算做对消分析.最近，在文献[59]中本团队首次创立了不依赖指标序(ordering-free)的容斥对消方法，并进一步证明不依赖指标序的容斥对消集优于所有依赖指标序的对消集.这一结果实质性地改进了容斥对消理论，进一步发展了经典的容斥原理，在图的各种计数多项式以及更一般的基于容斥原理的计数问题上具有广阔的应用前景.

2.2 Pólya计数理论在图论中的应用

1857年，著名数学家 Cayley[1]首次用树表示烷烃来研究同分异构体的计数问题，由此开启了图的计数问题的研究.100多年来，对图的计数问题的研究始终伴随着化学及生物学的应用，并由此催生了许多经典的计数理论和方法[60].最具代表性的是 Redfield 和 Pólya 的工作：他们把代数学家 Burnside 揭示的群与不变元之间关系的理论进一步完善，并成功应用到同分异构体的计数中，其核心是将置换与结构等价类之间的内在联系用轮换示式(cycle index)给出了一个清晰的刻画.Pólya 计数理论不仅在化学中的应用意义重大，也极大地丰富和发展了组合计数理论.1987 年，Read 将 Pólya 计数理论的原始著作翻译成英文并对这一理论的发展给予了精彩的回顾[2].

本团队应用 Pólya 计数理论在分子结构的计数问题取得了丰富的研究成果：运用 Pólya 计数理论给出了富勒烯的计数公式[61]；运用颜色集上的置换给出了苯环及其手性结构数目的解析表达式，其中苯环抽象为具有两种互为手性对映的颜色和一种非手性颜色的着色平凡纽结[62].文献[62]中方法的另一个意义是通过颜色集上的置换简化了目标集置换群的作用，通过引入多面体全着色的概念以及简化手性颜色轨道的计算，给出了该类多面体链环的计数公式，为研究更一般的多面体链环打下了很好的理论基础[63-64].Harary 等[7]将生成函数处理树的计数问题总结概括为“二十步”法，其核心是用分析的手段对生成函数的收敛域及临界点(critical point)进行估计.本团队运用这一方法给出了两类树状分子结构的递归计数公式及渐近值[65].此外，在运用 Pólya 理论处理等价类的研究中，本团队也提出了一个新的思想方法，其核心是将边置换的每一个循环转化为边集在该置换所生成的群的作用下的等价类[66-67]，对处理图的计数问题有很好的效果.

3 纽结理论及带子图

纽结的分类是纽结理论研究的基本问题，其基本思想是通过引入合适的不变量(多项式)来区分不同的纽结.因此，对不变量的研究是纽结理论的重要课题.本团队以组合数学和图论为工具研究纽结不变量，在组合纽结理论及带子图理论这两个拓扑学与图论交叉领域取得了较好的研究成果，是国内少有的涉足这一领域的研究团队.

3.1 组合纽结理论

本团队建立了更广泛的基于图的链环类的Homfly多项式与该图的Tutte多项式的联系[68].该工作大大拓展了著名组合纽结领域专家Jaeger F和Traldi L教授的工作，即从用个别整tangle覆盖图的边推广到用无穷类具有交错定向的tangle覆盖图的边，证明了排叉纽结Jones多项式零点在整个复平面上分布是稠密的[69]，该工作与统计物理密切关联.著名的纽结不变量专家Lin X S生前曾从事纽结Jones多项式的零点的研究，做了大量的数值试验，数值结果显示零点在复平面上有些空洞.本团队的理论结果与Lin X S数值计算结果比较颇为意外，这可能是由于数值计算结果只考虑有限个(尽管很多)小的纽结，而本团队考虑的是一类无限个纽结所造成的.

此外，本团队还证明：除(2,n)环面结和(p,q,r)排叉结外，所有的素链环都对应一个cubic 3-polytope的符号平图[70]，由此可以得到所有链环的Kauffman bracket多项式.最小stick数是纽结理论中的一个基本参数.数学家很早就知道至少6个stick才能构成一个非平凡的纽结，即三叶结.20世纪90年代，化学家在生物聚合物中发现了许多DNA纽结和蛋白质纽结，可抽象为立方体格子中的纽结.由此，人们开始关注立方晶格中纽结的最小长度.1992年，Diao[71]证明立方体格子中三叶结的最短长度是24.2005年，Huh[72]得到立方体格子中八字结的最少stick数.本团队证明：除了三叶结和八字结外，其他纽结的SL(K)均不小于 16，且交叉点指标为 5的两个纽结SL(K)均为 16，并具体给出了 16 个线段拼成的 5 个交叉点的立方体纽结[73].

3.2 带子图理论

本团队在扭曲对偶以及相关领域取得了系列成果：给出了平图部分对偶中的欧拉图的一个刻画[76]，解决了Huggett[77]提出的一个问题；对任意带子图部分对偶图中的二部图和欧拉图进行了刻画；研究了极值带子图刻画问题[78]，解决了文中提出的两个关于环面嵌入图的问题，并将相关结果推广到更高亏格的曲面；证明了一个虚纽结是可图的当且仅当它是棋盘可着色的[79]；将空间图的Yamada多项式[80]推广到虚空间图；针对Gross等[81]引入的部分对偶定向亏格多项式和部分对偶欧拉亏格多项式，猜测不存在定向带子图且它的部分对偶亏格多项式只有一项且该项不是常数项的结论，本团队分别给出了一类反例，并进一步猜测该反例在某种程度上是仅有的一类反例[82].

4 图网络及应用

图网络是现实各种网络的统一抽象，在计算机科学、理论物理及信息生物学等领域扮演着重要的角色.本团队在图上随机游动、电网络及网络优化方面取得了较好的研究成果.

网络上的随机游动是一个随机过程，与物理中的电网络[83]、布朗运动、沙堆模型等各种扩散过程都有紧密的联系[84].近年来，它更是被广泛应用于各种复杂网络的研究中，如社会网络的关系预测、社团识别、万维网的规模估计、网页的排序等.此外，设计图上的随机游动来近似地处理一些经典的特别是组合数学中的NP-困难问题，已成为当今的一个热门研究课题.2002年，Kannan[85]在北京世界数学家大会45 min大会报告中对此做了较详细的介绍；2006年Fields奖获得者俄罗斯数学家Okounkov获奖的工作也和随机游动有关；Wolf奖获得者Lovsz[84]在这方面也做了很多工作.

本团队运用图上的随机游动和电网络之间的紧密联系，发现了随机游动转移矩阵的谱和电阻距离之间的一个优美关系式.在此基础上，提出了一个全新的拓扑指标：度乘Kirchhoff指标.该指标与Kirchhoff指标(由国际著名数学化学家Klein和Randic于1993年提出)以及度和Kirchhoff指标(由国际著名的数学化学家、塞尔维亚科学院及俄罗斯非线性科学院院士Gutman 于2012年提出)一起被称为电阻距离的三大重要指标[86-87].进一步，本团队给出了计算图上电阻距离的两种新方法：一是关于电阻距离的一个完备的局部和法则，从这个局部和法则不仅可以推得几乎所有已知的和公式(如著名的Foster公式)，而且把任意两图之间电阻距离的计算问题转化成解线性方程组问题；二是得到了电阻距离关于转移矩阵及其最小多项式的一个全新表达式，利用此表达式得到了几类图任意两点间电阻距离的具体表达式[88].在文献[89]中首次运用图上沙堆模型的常返构型和生成树之间的一一对应关系，得到了一类广义Bethe 格上沙堆模型的高度分布函数精确表达式，从而不仅理论上证明了物理学家Grassberger和Manna由数据模拟发现的结果，并且推广了印度著名统计物理学家Dhar和Majumdar关于无限Bethe格高度分布函数的结果.在文献[90]中运用图的临界群和图的圈空间及割空间之间的关系，建立了一类变换图-团插入图的临界群与其原图临界群之间的同态.此外，本团队运用代数和组合相结合的方法，证明了标准遗传算法中变异算子的快速收敛性[91].

在网络优化理论中，高效、大容量、高可靠性、经济性的网络设计具有重要的理论意义和应用价值，其中高效和高可靠性与图的连通性密切相关，大量有实际应用背景的理论课题需要深入研究.在张福基和郭晓峰早期得到的几类2-连通图的可约链和临界k-边连通图的构造方法[92-93]基础上，本团队进一步在临界2-连通图的构造方法、5-连通图的可去边和构造方法、k-连通图的可去边和k-连通图的构造方法、各种有应用背景的特殊图类的多种限制性连通度、超连通度等一系列课题研究中取得丰富的成果[94-104].