论文部分内容阅读
计数,作为组合数学的重要分支,不仅应用于数学本身,还广泛的应用于其他学科。随着科技的发展,尤其是计算机科学的发展,它的重要性日趋显示。组合地图计数理论是组合学和拓扑图论的一个交叉学科和分支,主要研究在同构意义下,给定参数的不同地图的个数,它包括地图的计数、地图的色和、双色和等等。组合地图的计数理论与几何学,代数学,分析学以及函数论,概率论和泛函方程论等学科有着紧密的联系,近几十年取得了蓬勃的发展,对它的研究有重大的理论和实际意义。 因组合地图计数理论涉及数学多个分支的知识,其研究方法也被不断的改进和发展。本论文就剖分计数问题的解决提供了一些新的手段,具体的研究工作主要包括以下六个部分: 第一章,首先对地图计数理论的研究背景作了简要介绍。随后,对本论文主要研究内容做了简单阐述。 第二章,应用代数解析法,主要研究了外平面四角剖分。建立了以根面次,非根顶点数和边数为参数的计数函数,并通过求解三次和四次的计数方程,给出了不同参数下外平面四角剖分的计数显式。同时,还提供了2-边连通外平面四角剖分,圆盘上的四角剖分和多边形四角剖分等几类四角剖分的多参数计数显式。最后,分别建立了与Hamilton四角剖分和(4,3)正则Halin图这两类拓扑图论中重要的图类之间的一一对应关系,可由多边形四角剖分的计数结果直接推得这两类地图的计数公式。 第三章,应用求商运算法,主要研究了简单三角剖分和四角剖分。建立了以面数为参数的计数函数,并通过求解两个计数函数所满足的二阶微分方程,给出了以面数为参数简单三角剖分和四角剖分的精确计数显式。在此,我们基于标准商运算,通过找寻对称定向地图的新商运算,将对简单三角剖分(四角剖分)的计数归结为对带根准简单1-剖分(2-剖分)的计数。而后者不论是对地图分解,还是对计数方程求解,都是较前者更简单易行的。 第四章,应用构建双射法,主要研究了d围长d角剖分(d≥3)和p角形边界d围长d角剖分(p≥d≥3)。建立了以根面次和顶点数为参数的计算方程体系,给出了根面次为p的简单三角剖分和根面次为2p的简单四角剖分的计数显式。这里,为对d角剖分加入d围长的限制条件,我们引入了d/(d-2)定向,进而建立d围长d角剖分与d分枝悬挂树和p环形边界d围长d角剖分与(p,d)分枝悬挂树之间的双射关系。其中p环形边界d围长d角剖分即是p角形边界d围长d角剖分,标记了第二个面次为d的面。 第五章,应用递推公式法,主要研究了在可定向曲面,不可定向曲面和全体曲面上的无环地图。刘彦佩[78]研究了所有曲面上一般地图的计数问题,得到了以棱数为参数的计数方程。在此基础上,我们建立了以根顶点次和棱数为参数的Riccati型方程,给出了双参数下无环根地图的三个递推关系式。章末列出了根顶点次为s,棱数为l(l<20,s<20,l=s=0的退化情形未列入其中)的无环地图,在可定向曲面,不可定向曲面和全体曲面上非同构地图的具体数目。这种不考虑亏格的曲面计数法,还可推广到其它图类的计数。 第六章,介绍了本论文涉及到的地图计数领域中一些仍需要改进和进一步研究的问题。