（运筹学与控制论专业论文）关于给定亏格的非同构地图.pdf

北京交通大学博士学位论文中文摘要 中文摘要 摘要 本论文主要研究的是给定亏格曲面上的非同构根地图 即所谓的带根地 图计数问题 如不特别申明 文中凡提及地图皆指带根地图 其作为一般地图计 数的理论基础 该问题的研究具有重要的理论和实际意义 论文主要分成两大部 分 平面地图计数和非乎面地图计数 所采用的方法主要是一种解析方法 目前是 带根地图计数的核心 其中亦用到组合的技巧 对于平面上非同构根地图的研究 关键在于对地图集合本身给予一适当的分 解 这部分内容主要集中在前三章 第一章首先对地图计数理论的研究背景作简要介绍 随后 给出地图以及一 些与之相关的定义和性质 另外 对本论文主要采用的解析方法作了详细的阐述 第二章主要研究了平面泛扇地图和圈界地图 利用两种不同的方法 给出了 不同参数下一般平面泛扇地图和圈界地图的计数显式 同时 还提供了无环泛扇 地图 边缘3 一正则圈界地图以及受限圈界地图等几类平面地图的计数显式 众 所周知 h a f i n 地图在图的上嵌入理论和计数理论中都有着重要地位 这两类地 图就是在h a l i n 地图的基础上提出来的比之更一般的地图类 而且 一个泛扇地 图的基准图即是一个a p e x 图 5 6 其在拓扑图论中亦为一重要图类 第三章主要研究的是外一无弦平面地图 它是由不可分离平面地图衍生而得 到的一类地图 对于研究射影平面上3 正则地图 5 1 以及曲面上其他地图类的 计数问题都是非常有意义的 文献 2 4 中 给出了外一无弦近三正则平面地图的 个数 在此 我们通过寻找外 无弦一般地图与不可分离平面地图之问的一种关 系 得到了具有佗条边的外一无弦一般平面地图的具体数目 第二部分包括四 五 六三章 主要是在平面地图计数理论的基础上 对曲 面 尤其是高亏格曲面 上地图的计数问题进行研究 解决这一问题的关键在于寻 找合适的参数对其计数函数所满足方程求解 第四章着重讨论了曲面上瓣丛 瓣丛的对偶即是单面地图 在亏格为g 的曲 面上亦为矿本质地图 此两类地图均是地图类中最简单的 详细研究这两类地图 可为其他地图类的研究奠定基础 尤其是在复杂的高亏格曲面上 本章中 我们 对瓣丛做进一步研究 不但给出了多参数下瓣丛在任意亏格可定向雎面 不可定 向曲面 上统一的计数函数方程 而且给出了此类地图在任意亏格曲面上个数的 递推式 通过寻求合适的参数方程 我们得到了瓣丛 以根面次和边数为参数下 北京交通大学博士学位论文中文摘要 在可定向曲面 亏格0 3 及不可定向曲面 亏格1 5 上非同构地图的数日 同时 作为推论 亦得到了瓣丛 单面地图或矿本质地图 在以边数为参数下相应的计 数显式 且比已有结果更为简洁 基于第四章的结果 第五章研究了一类与瓣丛拓扑等价的地图类 近筘正则 地图 通过一种组合方法 不同于文献 2 4 1 给出了多参数下平面近2 一正则地图 的计数显式 同时 得到了任意亏格曲面上该类地图与瓣丛之问的一种关系式 第六章中 我们给出了泛扇地图在任意亏格不可定向曲面上统一的计数函数 方程 而且 得到了射影平面及k l e i n 瓶上此类地图在以根面次和边数为参数下 计数函数的精确解 第七章系统的介绍了地图计数领域中一些需要更进一步研究的问题 如精确 计算高亏格曲面上非同构地图 运用概率方法对地图计数等等 关键词 地图 根地图 计数函数 参数表达式 l a g r a n g i a n 反演 分类号 0 1 5 7 5 北京交通大学博士学位论文英文摘要 a b s t r a c t a b s t r a c t t h ep u r p o s eo ft h i st h e s i si st od i s c u s st h en o n i s o m o r p h i cr o o t e d m a p so fg i v e ng e n u s t h a ti s t h ee n u m e r a t i o no fr o o t e dm a p sw h i c hi st h eb a s i s o ft h ee n u m e r a t i o no fm a p s i ti sd i v i d e di n t ot w om a i np a r t s e n u m e r a t i o no f p l a n a rm a p sa n de n u m e r a t i o no fn o n p l a n a rm a p s ag e n e r a lm e t h o df o rc o u n t i n g r o o t e dm a p si sb ye m p l o y i n ga n a l y t i ct e c h n i q u e w h i c hp l a y sa ni m p o r t a n tr o l ei n t h ee n u m e r a t i o no fm a p s i na d d i t i o n i nt h i st h e s i s s o m es k i l l so fc o m b i n a t o r i e s a r ea l s oe m b o d i e d f o rs t u d y i n gt h en o n i s o m o r p h i er o o t e dm a p so nt h es p h e r e a ni n t e r e s t i n g i m p o r t a n ts t e pi no u rm e t h o di n v o l v e sg i v i n ga na p p r o p r i a t ed e c o m p o s i t i o nf o r t h es e to fm a p sc o n s i d e r e d t h ec o n t e n to ft h i sp a r ti sc o n c e n t r a t e do nt h ef i r s t t h r e ec h a p t e r s i nc h a p t e r1 f i r s t l y w eg i v eab r i e fi n t r o d u c t i o na b o u tt h eb a c k g r o u n do ft h e e n u m e r a t i v et h e o r yo fm a p s t h e ns o m ed e f i n i t i o n sa n dp r o p e r t i e s r e l a t et om a p s a r ep r o v i d e d f i n a l l y t h ea n a l y t i ct e c h n i q u ei se x p o u n d e di nd e t a i l c h a p t e r2 d i c u s s e st h ep l a n a rp a n f a nm a p sa n dc i r c u i tb o u n d a r ym a p s w h i c hb r o u g h tf o r w a r db a s e do nt h eh a l i nm a p s t h ei m p o r t a n c eo fh a l i nm a p s h a sb e e nd i s c o v e r e di ng r a p he m b e d d i n gt h e o r ya sw e l la si nt h ee n u m e r a t i o n s o fm a p s t h e s et w ok i n d so fm a p sa r em o r eg e n e r a lt h a nh a l i nm a p s i nt h i s c h a p t e r u s i n gt w od i f f e r e n tm e t h o d s w eo b t a i nt h e i re x p l i c i te x p r e s s i o n s 谢t h d i f f e r e n tp a r a m e t e r s m e a n w h i l e s o m ee x p l i c i te x p r e s s i o n sa b o u tt h el o o p l e a s p a n f a nm a p s c i r c u i tc u b i cb o u n d a r ym a p sa n ds t r i c tc i r c u i tb o u n d a r ym a p sa r e d e r i v e d i nc h a p t e r3 w es t u d yt h eo u t c h o r d l e e sg e n e r a lm a p sw h i c hd e r i v ef r o m n o n s e p a r a b l em a p s o u t c h o r d l e s sm a p sw e r ep r o p o s e db yy p l i ui nl i t s 1 1w h e n h ee n u m e r a t e dc u b i cm a p so nt h ep r o j e c t i v ep l a n e i nl i t 1 2 4 1 r x h a oo b t a i n e d t h en u m b e ro fo u t e h o r d l e s sn e a r l yc u b i cp l a n a rm a p s h e r e b ys e a r c h i n gt h e r e l a t i o no ft h eo u t e h o r d l e e sm a p sa n dt h en o n s e p a r a b l ep l a n a rm a p s w eg e tt h e n u m b e ro fo u t c h o r d l e s sg e n e r a lm a p sw i t ht h es i z ea sa p a r a m e t e r o nt h eb a s i so ft h ee n u m e r a t i v et h e o r yo fr o o t e dp l a n a rm a p s t h es e c o n dp a r t w h i c hi n c l u d e sc h a p t e r4 5a n d6 m a i n l yi n v e s t i g a t et h en u m b e ro fn o u i e o m o r p h i e 北京交通大学博士学位论文英文摘要 m a p so nt h es u r f a c e sw i t hg e n u sg 0 t h ec r u xo ft h i sp r o b l e mi st oc h o o s e s u i t a b l ep a r a m e t e r s s i n c eh e r et h ef u n c t i o n a le q u a t i o n sa r ea l w a y s c o m p l e x i nc h a p t e r4 p e t a lb u n d l e so i ls u r f a c e sa r es t u d i e dd e t a i l e d l y a sw ek n o w t h ed u a lm a p so fa l lp e t a lb u n d l e so nt h es u r f a c eo fg e n u sga r es i n g u l a rm a p s o r g e s s e n t i a lm a p s t h e s et w ok i n d so fm a p sa r eo ft h es i m p l e s tc l a s s ap a r t i c u l a r d i s c u s s i o na b o u tt h e s em a p sc a nl a yaf o u n d a t i o no no u rf u r t h e rw o r k s e s p e c i a l l y o i ls u r f a c e sw i t hh i g h e rg e n u s al o to fs c h o l a r ss t u d i e dt h e m h o w e v e r e x a c t e n u m e r a t i o nw a sm a i n l yc e n t r a l i z e do ns u r f a c e sw i t hs m a l lg e n u s o rt h er e s u l t s w e r ec o m p l e x i nt h i sc h a p t e r w ep r o v i d et h eu n i f o r me n u m e r a t i v ef u n c t i o n a l e q u a t i o no fo r i e n t a b l e n o n o r i e n t a b l e r o o t e dp e t a lb u n d l e sa n dd e d u c et w or e c u r s i o nf o r m u l a sf o rc a l c u l a t i o n a c c o r d i n g l y t h en u m b e ro ft h e s em a p sw i t hu pt o t w op a r a m e t e r so nt h eo r i e n t a b l es u r f a c e s g e n u s0 3 a n dt h en o n o r i e n t a b l es i l l f a c e s g e n u s1 5 a r eo b t a i n e d a sc o r 0 1 s o m ee x p l i c i te x p r e s s i o n so fr o o t e dp e t a l b u n d l e so ns o m es u r f a c e sw i t ht h es i z ena r ea l s og a i n e d b a s e do nt h ef o r t hc h a p t e r i nt h ef i f t hc h a p t e r w ec o n s i d e r8k i n do fm a p s n e a r l y2 r e g u l a rm a p s t o p o l o g i c a l l ye q u i v a l e n tt op e t a lb u n d l e s b yac o m b i n a t o r i a lm e t h o d t h ee x p l i c i te x p r e s s i o no fr o o t e dn e a r l y2 r e g u l a rm a p so nt h es p h e r e w i t ht h r e ep a r a m e t e r si sp r o v i d e d a n dar e l a t i o nb e t w e e nt h e s em a p sa n dp e t a l b u n d l e so ns u r f a c e sw i t ha r b i t r a r yg e n u si sa l s of o u n d i nc h a p t e r6 w eo b t a i nag e n e r a le n u m e r a t i n gf u n c t i o n a le q u a t i o na b o u t r o o t e dp a n f a nm a p so nn o n o r i e n t a b l es u r f a c e s b a s e no nt h i se q u a t i o n t w oe x p l i c i te x p r e s s i o n so fr o o t e dp a n f a nm a p so nt h ep r o j e c t i v ep l a n ea n dt h ek l e i n b o t t l ea r eg i v e n c h a p t e r7 d i s c u s s e ss o m eu n r e s o l v e dp r o b l e m sa b o u tt h ee n u m e r a t i o no f m a p s s u c h 船 e x a c te n u m e r a t i o no fm a p so nt h eh i g h e rg e n u s e n u m e r a t i o n o fm a p sb yp r o b a b i l i s t i cm e t h o d se t c k e y w o r d s m a p s r o o t e dm a p s e n u m e r a t i n gf u n c t i o n e x p l i c i te x p r e s s i o n l a g r a n g i a ni n v e r s i o n c l a s s n o 0 1 5 7 5 l v 坼 m e r c m r m 朋1o m 2 l l 卜m 符号说明 亏格为p 的可定向曲面 亏格为g 的不可定向曲面 地图m 的节点数 地图m 的边数 地图m 的面数 地图m 的e u l e r 示性数 m 的基准图 g 的准基地图 地图m 的自同构群 自同构群a u t m 的阶 地图m 消去边e 地图m 收缩边e 根地图肘的根 m 中与r 关联的边 根地图m 的根节点 根地图m 的根边 根地图m 的根面 的 z 一差分 脑和m 2 的1 一和 朋l 和朋2 的1 一积 肘与环地图厶1 的内部和 v j i 啡心删删艄一删焖一一 删删 北京交通大学博士学位论文符号说明 l 1 0 m 尬 尬 m l m 2 z 环地图l 与m 的内部积 尬和m 2 的内1 v 和 m 1 和朋2 的内1 v 积 z 对z 求偏导 致谢 本论文是在刘彦佩教授的悉心指导下完成的 正是刘老师辛勤的培养和无微 不至的关怀使我在成长中不断进步 刘老师为人宽厚 待人诚恳 知识渊博 治学 严谨 勤恳敬业 是我学习的楷模 在此对刘老师的帮助与鼓励表示衷心的感谢 感谢常彦勋教授 冯衍全教授 修乃华教授 郝荣霞教授以及何卫力副教授 对于我的科研工作和论文他们都提出了许多的宝贵意见 使我受益匪浅 感谢周垂香 杨艳 刘文忠 孔令臣 邵泽玲 阎爱玲 王俊玲 林海燕以及 程木等同学 在论文完成过程中的巨大帮助 感谢爱人对我生活上的照顾和关怀 使我安心投入到工作中 在此表示衷心 感谢 感谢父母对我培养及教育 正是他们多年来的支持与理解才使我得以顺利完 成学业 深深的感谢他们 第一章预备知识 这一章中 为了便于大家对所研究的地图计数理论有一个清楚的认识 首先 对其由来及发展过程给予系统的介绍 随后 为了能从数学上准确的描述这一理 论 我们对一些与之相关的基本概念 性质以及所采用的研究方法进行了简要的 叙述 1 1 研究背景 二十世纪六十年代初 加拿大著名数学家w t t u t t e 发现 对给定边数的平 面三角图的顶点4 着色的平均数问题要比四色定理的证明相对容易些 由此 作 为地图着色理论中色平均数问题的第一步 平面地图计数理论开始形成 尤其 在 t u t t e 发展了给地图标根的方法后 对地图的计数理论从此开始了广泛的研究 当时 t u t t e 发表了一系列有关平面地图计数方面的综述性文章f 6 6 7 4 他研 究了有限极大平面地图依无限面边界内部的节点数及其上的节点数2 个指标的计 数 随后 又研究了一般带根平面地图单指标的计数 为以后的研究工作奠定了坚实 的基础 之后 w g b r o w n 9 1 0 1 1 1 3 r c m u l l i n 5 7 5 8 5 9 f h a r a r y 2 6 2 7 以及w t t u t t e 本人等对先前的工作进行了必要的简化和相应的推广 十多年后 刘彦佩 3 6 4 s e a b e n d e r 2 6 7 等人对此领域做了进一步的研 究与推广 几乎涉及到了各种类型的平面地图的计数问题 八十年代初平面地图 计数方程的出现 很大程度上简化了平面地图的计数过程和结果 是平面地图计 数方法的一次飞跃 由此 平面地图的计数理论走向了 个新的阶段 近年来 许 多学者如g a of 2 3 颜基义 董峰明 1 7 18 蔡俊亮 1 4 1 5 16 等在此基础上做 了进一步的研究 取得了很好的进展 其中 蔡俊亮深化发展的一种参数技巧在 应用于对计数函数方程 尤其是高次方程 求解时 得到了一些更简洁的结果 在平面地图计数理论的基础上 人们自然会想到将此理论平移到高亏格曲面 上时结果会怎样 怎样才能克服由亏格引起的困难 一般来讲 人们往往采用的 是将高亏格间题转化为若干个低亏格问题 但这样做势必会导致所列函数方程的 复杂度增强 其求解就会变得异常困难 因此 对任何一类非平面地图的精确计 算都是不容易的 二十世纪六十年代中期 w g b r o w nf 1 2 和w t t u t t e 首先计算了一类非 平面地图 而后 t r s w a l s h 和a b l e h m a nf 7 6 7 7 7 s 利用与t u t t e 和b r o w n 1 第 一 章预备知识 不同的方法 研究了一般任意可定向曲面上地图的计数 得到了一类 树根 地 图的精确解 并给出了 个算法用于计算给定边数带根地图的数目 为今后高亏 格曲面上地图的研究起到了奠基性的作用 之后 自二十世纪八十年代起 由于非平面地图计数与现代物理和其他数学 学科的紧密联系 使得这一理论得以被进一步发展 诸多学者 如e a b e n d e r 3 4 5 8 e r c a n i l e l d r wr o b i n s o n 刘彦佩以及g a o 1 9 2 0 2 1 2 2 等人在本 领域均做了大量的有创造性工作 但得到的大部分结果都只是一个渐进估计 统 计方法 或者是只给出了相关的递推式 所以 怎样精确计算高亏格曲面上的地 图仍然是一个公开问题 如今 越来越多的年轻学者 如任韩 6 1 6 2 6 4 郝荣霞 2 5 l 毛林繁 李赵祥 3 0 3 1 3 2 等等 都在进一步深化和发展这一理论 他们对曲面上许多地图类 如射影平面和k l e i n 瓶上的4 正则地图 6 3 l 固定曲面上欧拉地图 6 4 曲面上一 般地图等等都进行了详细的研究 并得到了它们相应的精确解 纵观地图计数理论的由来及发展过程 可以看出它与图的嵌入理论 拓扑图 论 组合数学 分析数学 代数学以及概率论等学科有着紧密的联系 对其进行研 究必将对数学整个学科的发展起到推动作用 有其一定的理论意义和实际意义 1 2 相关的定义与性质 从几何直观上讲 一个地图就是图在某曲面上的一个2 一胞腔嵌入 这里所说的曲面就是无边缘的2 维紧闭流形 带有p 个手柄 或q 个交叉 帽 的曲面 即 o 或心 被称为亏格为p f 或 的可定向曲面傅不可定向曲 面j 一个图g 在曲面s 上的孕胞腔嵌入是指g 能画在s 上使得边与边的交点 只可能是g 的顶点 且g 在s 上的补s g 的每一个连通分支都拓扑等价于圆 盘 下面我们从代数上给出地图的严格定义 令x 是一个有限集和k 为由四个元素组成的k l e i n 群 k 1 q 成a 卢 由于k 是群 自然有a 2 卢2 1 o p a 对任何一个元素z x 在k l e i n 四元群k 的作用下产生一个四元胞腔k x z 口z p z n p z p 是在所有这些 四元胞腔的无公共元的并 x 一 k x z e x 2 北 京交通 大 学博 士学位论文 上的一个置换 可见 a 和p 均可视为x 的置换 在x 上的一个置换p 若对任何z x 均不存在整数k 0 使得p z n z 则被称为基本的 个组合地图 简称为地图 常记为m x 口 p 它被定义为在四元胞 腔无公共元并集x 上的一个基本置换p 且满足下面的公理1 和公理2 公理1o p p 0 1 公理2 由j o 尻p 所生成的群皿j 在x 上可迁 由于任何一个置换均可以表示为循环 置换 的乘积 它的每一个循环中元素 组成的集合被称为轨道 依公理1 可知 若 表示p 的一个循环 则 z p z p 2 p z o t x p 一1 a p 一2 z r p 一 o t x p a x p 2 0 i x q z 也表示p 的一个循环 由对称性 称这样的两个循环为共轭对 性质1 对任何地图m x 邮僻 p 表示置换p 的循环由共轭对组成 根据性质1 我们称p 每一个共轭对为地图m 的节点 或顶点 给定 个地图m x 口 x p 可以验证m x 口 僻 p d p 也是一个 地图 称肘 为m 的对偶 并且 m 的节点成为m 的面 自然 每一个四元 胞腔被称为边 或棱 任何一条边 而口z 触 a 肪 可视为由两个半边 z q o 与 f l z a z x 在m 中 或者 z 触 与 n z 口触 在m 中 组成 若一个图的节点和边的集合与m 的相同 则称它为m 的基准图 常记为 g m 反之 若一个地图的节点和边的集合与一个图g 的相同 则称它为g 的 准基地图 常记为m g 虽然一个地图只有一个基准图 但一个图一般有不只一 个准基地图 为方便 只有 个节点而无边也常视为一个地图 称它为平凡的 或 节点地图 规定它只有一个面 若一个地图只含一条边则称它为边地图 用工表 示 若边地图的边为环 则称为环地图 否则 杆地图 令虬e 和 分别为地图m 的节点数 边数和面数 则 e u l m 一e 妒 被称为m 的e u l e r 示性敷 3 第 一 章 预备知识 性质2 对任何地图m 总有 e u l m 2 性质3 令m 是地图m 的对偶 则 e u l m e u l m 进而 若 个地图m x 郇 p 还满足下面的公理3 则称它为不可定 向的 否则 可定向的 公理3 由i o p p 所生成的群霍j 在x 鲫 上可迁 性质4 若霍f 在x 印 x 上不可迁 则它恰含二个轨道 令m 口 x p 是一个地图和e z o l x 触 n 肛 为与z x a 口 x 关联的那条边 为简化 当不引起混淆时 总是用x 代替 庙记 x x a x 4 z x 口p x 其中 7 x y x l v z x y o 卢和q p 并且 将边e z n z 触 q 触 k x z x 就简记为e 在一个地图m x p 上 若一条边与两个面关联 则称它为单边 否则 为双边 平面地图中的双边亦可称为割边 贯穿整篇论文的一个重要手法就是对地图m x p 上所选取边e 和节点 进行各种运算 现简单介绍如下 1 消去e 即 肘一e 仅一e p 如 其中 p e 为p 限制在x e 上的部分 2 收缩e 即 m e x e p e 其中 p f e j 为将e 在m 上的二端n 马a 口卫 a a 1 或简记乱 扛 a 和口 n 触 b 触 a b 1 或 n 触 b 合成为节点 b a a a 1 b 一1 或 b a 同时 使其他节点不变 4 北京交通大学博 士 学位论文 3 劈分节点 a b 令 为将p 中的 b a 用 墨a 和 n p 而b 代替而得 到的 这里 k x 为新引进的边 容易验证 仅 k x 也是 一个地图 并称之为由m 经过劈分节点 而得到的 4 忽略节点口 a 触 则地图 x k x k y k z 使得p 是从 m 中消去节点口 并且在p 中 令k z 矗 d 叠励 s o u 而得到的 这时 称 为在m 中忽略了节点 消去一条边的逆运算称为添加一条边 忽略一个节点的逆运算为细分一条 边 容易验证 通过边的收缩 劈分节点 忽略节点和它们的逆 e u l e r 示性数不 变 而消去边时以及与之相应的逆运算 添加边 只能当所消去边为单边时 才能 使e u l e r 示性数不变 对于可定向地图和不可定向地图有如下定理成立 定理1 2 1若地图m x p 是可定向的 则有e u l m o m o d 2 而且 m 在亏格为p 的曲面上当 且仅当 e u l m 2 一印 其中e u l m 1 为m 的e u l e r 示性数 定理1 2 2对于不可定向地图m x p m 在亏格为口的不可定向曲面上 当 且仅当 有 e u l m 2 一q 其中q 0 若e u l m 2 即p m 0 则m 被称为平面的 对p m 1 q m 1 或2 分别称m 为在环面上的 在射影平面上的或在k l e i n 瓶上的 二地图m 口 x 1 r 和m 2 口 托 伤 若存在一个双射f p x 一x 印 x 2 使得形式 洳 口 x 1 j jx 口 恐 饥l能l 舶 口 x 1 l a x 2 对饥 讹 n 饥 他 口和 y l r 与铂 伤是可交换的 则称尬和 是同构的 这个双射r 被称为它们之间的一个同构 5 第 一 章预备 知识 若呖 m 2 m 它们之间的同构被称为m 的自同构 易验证 一个地图 m 上的所有自同构形成一个群 并称之为自同构群 用a u t m 表示 若a u t m 只含单位元 则意味m 只有一种表示 若将地图m x a a p 的基本集 口中的一个元素选定 并给以特别的标 记 则称m 为带根地图 这样做的目的就是为了破坏地图的对称性 那个有标记 的元素被称为根 常记为r r m 与根关联的节点 边和面分别称为根点 根边 和根面 分别记为诈 m e m 和f r m 特别地 对于甲 面地图来说 我们一般总是选取其无限面为根面 性质5 对于任何一个带根地图m 均有a u t m 1 即仅由单位元组成的 群 二个带根地图m i 和m 2 当存在一个同构使得它们的根相对应时 才称它们 是同构的 否则 称为非同构的 所谓地图计数就是要确定在给定条件下非同构地图的数目 研究给定条件下 安置事物的方法数 未解释的术语 读者可参见刘彦佩 4 9 5 0 5 2 及 数组合地图论 科学出 版社 2 0 0 1 1 3 研究方法 地图计数理论发展到如今 已有近5 0 年的历史 由最初t u t t e 所采用的构造 性方法到目前最常见的解析方法 许多学者在这一领域做出过贡献 其中一些方 法简要的列举如下 重根方法 w g b r o w n 等人于二十世纪6 0 7 0 年代发展起来的 但仅限于解 2 次方程 双射方法 t u t t e 率先将该方法用于平面标根e u l e r 地图的计数 这种方法 本身就是组合计数的基础 同时还广泛地应用于下面的解析方法和代数方法 中 a l b e r t od e ll u n g o 5 3 在对不可分离带根平面地图进行研究时 就是通 过建立具有n 1 条边的不可分离带根平面地图与具有死个内部节点的l e f t t r e e s 地图之间的1 1 对应开展讨论的 统计方法 二十世纪七十年代中期 b e n d e r 等与刘彦佩等最先将这种方法甩 来渐进估计地图的数目 主要是通过s t i r l i n 公式州一 p j 元 6 北京交通大学博 士学位 论文 解析方法 目前是地图计数 特别是带根地图计数的核心 本篇论文主要就是 基于这种方法开展研究的 后面会给予详细的介绍 代数方法 j a c k s o n 2 s 2 9 和v i a e n t i n 开创了这种群代数理论用于地图计数 的方法 概率方法 自1 9 8 5 年以来 运用这种方法研究给定地图类中含有特定子地图 或特定的次节点 已经成为地图枚举极其应用领域内的一个潮流 r i c h m o n d 等人的文章是这一领域内的第一篇具有影响力的文章 下面我们就解析方法作详细的介绍 该方法自七十年代初 w a l s h 和l e h m a n 用于研究曲面标根地图计数问题后 至今已经发展成为一种计数带根地图的系统 方法 可以分成以下三个步骤 一 将要计数的地图集合进行适当的分解 分解为若干个部分 使每一部分均可 由这个地图集合本身通过一些运算产生 通常是利用节1 2 中提到的边的收缩 与添加以及节点的劈分与合并等运算 对于平面地图 由于没有亏格的出现 因此在其上所进行的一系列运算都可以顺利进行 但当亏格出现时 问题就变 得复杂起来 这时 一般是将此高亏格问题转化为若干低亏格问题来研究 二 在地图集合分解的基础上 建立计数函数所满足的函数方程 这一步骤的关 键就是要选择合适的参数 一般来说 一个合适的参数的选择 会从某种程度 上大大简化计数方程 降低方程的次数 使求解变得相对简单 三 寻找合适的参数表达式 利用l a g r a n g e 反演求解计数方程 从而 得到地图 的计数显式 这是地图计数的关键和难点 尤其是对曲面上地图计数函数所满 足的方程求解时 由于其方程经常是 混合型 的 因而 求解过程就变得愈 加困难 基于此种方法 本文分别就几类平面地图 第二 三章 和非甲面地图 四 五 六章 的计数问题进行了研究 给出了泛扇地图 圈界地图 外一无弦一般地 图 瓣丛以及近2 正则地图等等几类地图在给定亏格曲面上非同构地图的具体 数目 得到了它们在不同参数下的精确解 为高亏格曲面上一般地图的计数打下 基础 7 第二章平面泛扇地图和圈界地图 一个地图 若在它的基准图中存在一个圈 使得去掉这个圈上所有边后为一 个树 而且这个树的所有悬挂点的集合 与这个圈上所有节点的集合相同 则称 它为h a l i n 地图 h a t i a 地图在图的上嵌入理论和地图计数理论中都占有重要地 位 1 9 9 9 年任韩和刘彦佩 6 1 对平面h a l i n 地图进行了精确计算 给出了h a l i n 地图依节点剖分的计数显式 基于h a l i n 地图 我们提出了两类较之更一般的地 图类 泛扇地图和圈界地图 本章中 主要对平面泛扇地图和圈界地图进行研究 通过两种不同的方法 给出了不同参数下 如边数和根面次 根点次及边数等 这 两类地图的计数显式 其一为解析方法 其二为组合方法 同时 亦对由此两地 图类引出的一些特殊平面地图类 如 无环泛扇地图 边缘3 正则圈界地图以及 受限圈界地图进行了精确计算 2 1 一般平面泛扇地图 一个带根地图 若去掉它的根节点以及关联边后所得地图的基准图为一个树 或为空图 则称之为泛扇地图 此时 既允许有自环也允许有重边 而且节点地 图考虑在内 由此定义 可以看出一个泛扇地图的基准图即是一个a p e x 图 所谓 a p e x 图就是这样一个图g 它存在一个节点w 使得g w 为一平面图 a p e x 图在对图的亏格问题研究中具有强大作用 是拓扑图论中较为重要的一种图类 对任一带根泛扇地图m 顶点数v m 23 其根顶点 诈 r 耽p 2r p l r 其中 k 是根点次 令k r 表示与r 关联的边 假定彤 r k x 0 0 k 一1 是第一条连接根 顶点诈到顶点们 诈 口1 如 7 a s x p 2 6 z 7 a k l 1 j z k l 是顶点口l 的次 6 o p 的边 同样地 由于 v m 芝3 第一条连接饥蓟v 2 j 1 珥的边 k 印如0 1 七1 1 亦存在 因此 平面树 m 一 诈 m 定根方式如 下 l m l 9 i 6 z 一个球面 或平面 上的泛扇地图被称为平面泛扇地图 如图2 1 本节中 我们主要研究平面泛扇地图在以边数及根面次为参数下的非同构根地图的数目 9 第 二 章平 面泛 扇地图和圈界地 图 图2 1 带根平面泛扇地图 f i g 2 1 r o o t e dp l a n a rp a n f a nm a p 在此我们先简要介绍两特殊平面地图类 环束和植树 一个带根平面树 若 它根节点的次为1 则称之为植树 环束即只有一个节点和所有边均为自环 令c 和7 i 分别为所有环束和植树的集合 它们的计数函数分别为 妒 州功 扪 t 1 口州t 矽州 其中 n 三 和z 三 分别为l 的边数与根面次 定理2 1 1 z 2 l 计数函数t 1 有如下显式t 牡 象瑞y n z 2 n 2 n 1 7 为叙述方便 下面给出地图之问的一种运算 对任意两个地图尬和m 2 记它们的根为n r 尬 t 1 2 若地图 m m l u m 2 使得尬n 尬 扣 且 t 2 诈l5 j r 2 并规定m 与 具有相同的根 根节点和根边 但其根面为舰和 毛的根面 r l 矗 和g v t 2 的合成 则称这种从 矗和 l 如到m 的运算为j 一加法 记为 m m 1 4 m 2 且 肘被称为它们的j 和 1 0 北京交通大学博 士 学位论文 进而 对任何两个地图的集合朋1 和朋2 集合 朋l o 朋2 m i m i v 舰 m i l 2 被称为m 1 和m 2 的j 一积 其中的运算被称为j 一乘 若m 1 m 2 m 则可写为 朋 朋 朋0 2 类推之 川o k m b 一1 o m 令m 为所有平面泛扇地图的集合 可将之分为三部分m i 朋i i 和朋i i i 使 得 朋 朋i m i i 朋i i i 其中 v h 节点地图 m i i m m l 根边e r m 为割边 m i i i m 朋l 根边e m 不为割边 引理2 1 2 对于m 盯 我们有 m 盯 五0 证明 对任一m m i i 令丑和三分别为与m 有相同根节点的植树和环束 且r 乃 r m 和r l p k m 由1 一和的定义 可知m 噩阜l 由此 m 五o c 相反地 对任一m 五oc 一定存在两地图五 五和l c 使得 m 丑阜三 容易看出 地图肘仍然是泛扇地图 并且根边为割边 因此 m m i i 此引理得证 口 引理2 1 3 令朋 珊 肘一r i m j l l l 月 e r m 那么 m 珊 m 1 1 第 二 章平面泛扇 地图和圈界地图 证明 对予任意地图m m 1 1 1 存在一个地图m i m i i i 使得m m 7 一彭 这 里彤是 的根 由朋i i i 的定义可知 地图m 仍是一泛扇地图 即 m m 进而 朋 i i d 州 另一方面 对于任意地图m 3 4 通过添加一条连接其根节点v r m 和根面 边界上任一节点的边彤 总可以得到一个新地图心 使得m l 一r 其中 r i 岛一 显然 此时共有f m 1 种方式添边以获得地图m 7 这里l m 为 m 的根面次 易知 m i m i i i 从而 m g i l i 且 m i i i 2 朋 引理得 证 口 现在 考察m 的计数函数 f m y y n m z r t y m mn l 0 其中n m 和t m 分别为m 的边数与根面次 定理2 1 4 计数函数 满足如下方程 1 一z y z 2 1 一z t l 妒 y z y 1 一z 2 2 其中广 f y 1 f n y n o 证明 令 i 和 1 1 分别为 m l m i i 和j l l l 的计数函数 根据引理2 1 2 和引 理2 1 3 以下各式成立 五 l 舢 1 州 笔 一z 其中 f y 1 由于 知 f i i i 经过化简合并同类项 即可得方程 2 2 成立 口 关于方程 2 2 的适定性 可由方程两端作为口和2 幂级数的展开式 较之 同幂项系数求得的递推关系式之唯一性中导出 此时 注意到集合m 和c 的区别 对于环束有如下结果成立 因其证明过 程与泛扇地图同且更为简单 在此略之 1 2 尹 十0 蛾 血 北京交通大学博 士 学位论文 定理2 1 5计数函数妒满足如下方程 1 一z y z 2 妒 1 一z y z 妒 其中矿 妒 玑1 由方程 2 3 即可得如下参数表达式 叩 可 叩 1 2 z p q 1 根据式 2 1 容易验证 t l 妒 卵 1 1 妒2 两磊 设f 为方程 2 2 的一个特征解 即 嚣 睁 2 3 2 4 引进变量z p 叩 1 基于方程 2 2 和式 2 4 可以得到计数函数 满足 如下参数表达式 二塑 巡 二笪 二 型 塑 二皿 2 1 一卢 1 一p 口 2 2 1 一f 1 1 一q 1 一p 町 2 5 面 2 5 进一步 我们有 哳 高 利用多变量l a g r a n g i a n 反演公式 见附录定理8 0 6 u p r z 器 a 端 唧 p 所 1 叩 2 n 一 筘 哦咖 m p 鲈1 卜广 第 二 章平面泛扇地 图和 圈界地图 如下定理可以得到 定理2 1 6 边数为n 并且根面次为l 的平面泛扇地图的数日为 f o 0 1 熙 当 孰时 2 元盯i 面 壹 22 嚣q 晶 l 丛措 a 一2 一a n l 2 2 6 篆揣 者高群岛一 甍i 22 卜2 n 1 1 i k k 台削 后 1 n 一 后 1 n 一一1 鲁 n f l j 其中 o k n f 1 2 k 2 n t 一3 一k 1 3 2 n 且 a 2 k f 厶i p 上k lf k 2 k f k 2 p 一k 一i 1 1 定理2 1 7 边数为 1 的平面泛扇地图的数目为 2 n 一2 5 n 一1 2 百 项丽 薹揣卜喜2 两缙 2 其中f o 1 证明 令x 和y 是集合朋的两个子集合 集合x 是由所有边数为n 一1 的泛 扇地图构成的 集合y 是由所有根面次为1 边数为n 的泛扇地图构成的 对于任 一地图m x 通过在其上添加一条新边 我们可以得到一个地图 y 易见 此两个集合之间存在一个一一映射 因此 就式 2 6 取f 1 可以验证此定理成 立 口 基于式 2 6 下表中 我们给出了在n 和f 取小数值时非同构平