（运筹学与控制论专业论文）曲面地图的不对称普查.pdf

北京交通大学博士学位论文中文摘要 曲面地图的不对称普查 摘要 摘要：地图计数理论起源于w t t u t t e 在二十世纪六十年代初关于平面三角化的研 究经过半个多世纪的发展，这个理论吸引了众多学者的关注，并不断被发展和推广， 它包括地图的计数、色和，双色和等多个研究方向 本论文主要研究曲面地图的不对称普查，对平面地图和非平面地图都作了一定的 探讨，得到了一些新结果 第一章是绪论，简要的介绍了所研究问题的背景和意义，基本概念和方法和本文 的主要工作 第二章讨论平面地图平面h a l i n 地图是一类应用很广的地图，作为它的一个推 广，本章研究了平面边界三正则地图的计数问题我们首先得到了边界三正则内森林 地图以非根面的边数为参数的计数公式考虑一种特例，边界三正则内树地图以根面 次和边数为参数一个简洁计数公式被得到接着，根据对偶理论，我们给出了外平面 地图的相应结果最后，文中分别给出了边界三正则地图以非根面的边数为参数，和 以根面次及边数为参数的两个计数公式并且，两个著名的t u t t e 已知计数公式也很容 易从中被导出 第三章讨论给定瞌面上非平面地图的计数对于不可定向雎面上地图的计数，大 部分的文献都是集中在小亏格的曲面上，如射影平面，k l e i n 瓶等直到2 0 0 0 年，d a r q u e s 【3 】3 最先得到了亏格为3 和4 的不可定向曲面上一般地图的计数公式本章主要 研究了不可定向曲面上本质地图的计数给出了不可定向曲面上亏格为2 ，3 ，4 和5 的本质地图的精确计数公式，并最先得到了亏格为5 的不可定向曲面上地图的精确计 数公式同时，本章也得到可定向曲面上亏格为2 的本质地图的精确计数公式最后， 文中给出了任意亏格的两种曲面( 可定向和不可定向) 上本质地图的一般计数方程及其 解的结构 第四章主要研究了所有曲面( 可定向和不可定向) 上一般地图的计数刘彦佩【6 7 】 研究了所有曲面上一般地图的计数问题，得到了以边数为参数的计数方程在此基础 上，本章首先给出了所有曲面上一般地图以点数和边数为参数的计数方程，它是一个 r c c a t i 型方程对于r i c c a t i 型方程，现在无法得到它的分析解，甚至级数解都难得到 本章通过构造个函数方程序列，得到了它的一种以连分数形式表示的新颖的解同 时，考虑了两个特例，回答了文献( 6 7 个公开的问题 第五章是结论和展望本章首先总结了这篇论文的工作，接着展望了下一步要研 究的问题，它包括以下问题。 北京交通大学博士学位论文 中文摘要 问题1 ：任意亏格的不可定向曲面上本质地图的计数； 问题2 ：任意亏格的不可定向曲面上一般地图的计数； 问题3 ：曲面上无根地图的计数； 问题4 ：r i c c a t i 型方程的级数解 关键词：根地图；曲面；计数函数；欧拉公式；l a g r a n g i a n 反演 分类号：0 1 5 7 5 a na s y m m e t r i cc e n s u so fm a p so i ls u r f a c e s a b s t r a c t a b s t r a c t ：s t a r t i n gw i t hw t t u t t e ss e m i n a lw o r k so nt h ep l a n a rt r i a n g u l a t i o n i nt h eb e g i n n i n go f1 9 6 0 s ，e n u m e r a t i v et h e o r yo fm a p sh a sb e e ns t u d i e di n t e n s i v e l y i nt h ep a s to fo v e rf i f t yy e a r st h et h e o r yw a sd e v e l o p e da n de n r i c h e ds t e pb ys t e p n o w ，e n u m e r a t i v et h e o r yo fm a p si n c l u d e st h ee e n s l l so fm a p s ，t h ec h r o m a t i cs u m ， d i c h r o m a t i cs t u no fm a p sa n ds oo n t h i st h e s i sm a i n l yf o c u s e so na na s y m m e t r i c e o l l s l l so fm a p so ns u r f a c e s b o t hp l a n a rm a p sa n dn o n p l a n a rm a p sa r ei n v e s t i g a t e d a n ds o m en e wr e s n l t sa r eo b t a i n e d i nc h a p t e r1 ，i ti sb r i e f l yi n t r o d u c e dt h a tt h eb a c k g r o u n da n ds i g n i f i c a n c eo ft h e p r o b l e mc o n s i d e r e d ，s o m eb a s i cd e f i n i t i o n sa n dt h et e c h n o l o g i e se m p l o y e di nt h e t h e s i s t h e nt h es k e l e t o no ft h et h e s i si sd e s c r i b e d c h a p t e r2i sm a i n l yc o n c e r n e d 硒t hp l a n a rm a p s i ti s w e l lk n o w nt h a tp l a n a r h a l i nm a p sa r es oi m p o r t a n tt h a tt h e ya r ew i d e l ya p p l i e di nm a n yf i e l d s i nt h i s c h a p t e r b o u n d a r yc u b i cr o o t e dp l a n a rm a p s ，a st h ee x t e n s i o n so fp l a n a rh a l i nm a p s ， a r ei n v e s t i g a t e da n de x a c te n u m e r a t i v ef o r m u l a ea r eg i v e n f i r s t ，a ne n u m e r a t i v e f o r m u l af o rb o u n d a r yc u b i ci n n e r - f o r e s tm a p sw i t ht h es i z ea sap a r a m e t e ri sd e r i v e d t h e n ，f o rt h es p e c i a lc a s eo fb o u n d a r yc u b i ci n n e r - t r e em a p s ，as i m p l ef o r m u l aw i t h t w op a r a m e t e r si sp r e s e n t e d f u r t h e r ，a z c o r d i n gt ot h ed u a l i t y , ac o r r e s p o n d i n gr e s u l t f o ro u t e r - p l a n a rm a p si so b t a i n e d f i n a l l y , s o m er e s u l t sf o rb o u n d a r yc u b i cp l a n a r m a p sa r eo b t a i n e d f u r t h e r m o r e t w ok n o w n t u t t e sf o r m u l a ea r ee a s i l yd e d u c e di n t h ec h a p t e r w ed i s z u s sn o n p l a n a rm a p si nc h a p t e r3 o nt h ee n u m e r a t i o no fm a p so nt h e n o n o r i e n t a b l es u r f a c e s m o s to ff i t e r a t u r e se o n c e n t r a t e do ns u c hs u r f a c e sn st h ep r o j e c - t n ep l a n ea n dt h ek l e i nb o t t l e i n2 0 0 0 ，d a r q u e s 【3 】f i r s tp r e s e n t e dt h ef o r m u l a ef o r c o u n t i n gm a p so nt h en o n o r i e n t a b l es u r f a c e sw i t hg e n u s3a n d4 ，i nt h i sc h a p t e r ，w e i n v e s t i g a t ee s s e n t i a lm a p so ns u r f a c e sw h i c hp h yi m p o r t a n tr o l e si nt h es t u d yo fg e n - e r a lm a p so ns u r f a c e s f i r s t ，e x a c te n u m e r a t i n gf o r m u l a eo fh s s e n t i a lm a p so n ， n t i a lm a p so n a n d4 - e ：s s e n t i a lm a p so n 心a r ed e r i v e d t h e n ，t h ef o r m u l a f o rc o u n t i n gg _ e s s e n t i a lm a p so n 豫i sp r e s e n t e d ，w h i c hi st h ef i r s te n u m e r a t i v er e s u l t o fm a p so n 5 i nt h es m et i m e ，t h ec o r r e s p o n d i n gr e s u l tf o rc o u n t i n g2 - e s s e n t i a l m a p so n i sa l s oo b t a i n e d f i n a l l y , g e n e r a lf u n c t i o n a le q u a t i o n so fe s s e n t i a lm a p s o nt w ok i n d so fs u r f a c e s ( o r i e n t a b l ea n dn o n o r i e n t a b l e ) a r ed e d u c e da n dt h e i rf o r m a l s o l u t i o n sa r ep r e s e n t e d i nc h a p t e r4 ，r o o t e dg e n e r a lm a p so na l ls u r f a c e s ( o r i e n t a b l ea n dn o n o r i e n t a b l e ) a l ec o n s i d e r e d l i u 6 7 h a do b t a i n e dt h ee n u m e r a t i n ge q u a t i o nw i t ht h ee d g ea sa p a r a m e t e rf o rr o o t e dg e n e r a lm a p so na l ls u r f a c e sb e f o r e b a s i n go ni t ，r o o t e dg e n - e r a lm a p so na l ls u r f a c e sa r ef u r t h e ri n v e s t i g a t e da n dt h ee n u m e r a t i n ge q u a t i o nw i t h r e s p e c tt ov e r t i c e sa n de d g e si sd e r i v e d ，w h i c hi sar i c c a t i se q u a t i o n ，n o w ，n o to n l y t h ea n a l y t i c a ls o l u t i o nb u ta l s ot h es e r i e ss o l u t i o no fr i c c a t i se q u a t i o ni sh a r dt ob e o b t a i n e d t os o l v i n gi t ，an e ws o l u t i o ni nc o n t i n u e df r a c t i o nf o r mi sg i v e n a st w o e s p e c i a lc a s e s ，t h ec o r r e s p o n d i n gr e s u l t so fr o o t e dg e n e r a lm a p sa n dm o n o p o l em a p s o ns u r f a c e sw i t hr e s p e c tt oe d g e sa r eo b t a i n e d ，w h i c ha n s w e ra no p e np r o b l e mf 6 7 】 t h el a s tc h a p t e rs u m m a r i z e st h et h e s i sa n dp l a n st ot h ef u r t h e rw o r k s ，w h i c ha r e t h ef o l l o w i n gf o u rp r o b l e m s ： p r o b l e m1 ：t oc o u n te s s e n t i a lm a p so nt h en o n o r i e n t a b l es u r f a c e sw i t ha r b i t r a r y g e n u s ； p r o b l e m2 ：t oc o u n tg e n e r a lm a p so nt h en o n o r i e n t a b l es u r f a e 目w i t ha r b i t r a r y g e n u s ； p r o b l e m3 ：t oc o u n tu n r o o t c dm a p so l ls u r f a c e s ； p r o b l e m4 ：t h e8 e r i e ss o l u t i o no ft h er i c c a t i se q u a t i o n k e y v c o r d s ：r o o t e dm a p ；s u r f a c e ；e n u f u n c t i o n ；e u l e rf o r m u l a ；l a g r a n g i a n i n v e r s i o n c l a s s n o ：0 1 5 7 5 致谢 本论文的工作是在我的导师刘彦佩教授悉心指导下完成的刘彦佩教授严谨的治 学态度和深厚的数学功底以及自由活泼的讨论方式给了我极大的帮助和影响，他对科 学的献身精神和扎根科学的工作方法使我终生受益而且，在生活上，刘老师也给了 我无微不至的关怀在此衷心感谢三年来刘老师对我的关心和指导 常彦勋教授、冯衍全教授、修乃华教授、郝荣霞教授和何卫力副教授等对我的科 研工作和论文都提出了许多的宝贵意见，在此表示衷心的感谢同时，感谢理学院的 全体老师对我的支持和帮助 在撰写论文期间，万良霞、陈仪朝，许燕、周垂香、孔令臣、邵泽玲杨艳、董广 华，以及0 4 级博士班的同学对我的研究工作给予了热情帮助，在此向他们表达我的感 激之情 最后，我特别感谢我的家人在生活中给予我的无限支持和帮助他们对我的理解 和鼓励，期待和厚望，永远是我前行的动力 第一章绪论 本章首先概述了所研究同题的内容和意义、历史和现状以及一些基本定义和方 法，然后简要介绍了本文的主要工作 1 1 研究问题的内容和意义 计数，作为组合数学的重要分支，是一门研究数的艺术，它不仅应用于数学 本身，还广泛的应用于其他学科随着科技的发展，尤其是计算机科学的发展，它的 重要性日趋显示 组合地图计数理论是组合学和拓扑图论的一个交叉学科和分支，主要研究在同构 意义下，给定参数的不同地图的个数，它包括地图的计数、地图的色和、双色和等等 组合地图的计数理论与组合数学，拓扑图论，图的嵌入理论，代数学，函数论，概率 论等学科有着紧密的联系，是近几十年发展比较迅猛的一门学科，对它的研究有重大 的理论和实际意义对于地图的计数，人们首先要了解的是地图的对称性，即，自同 构群一般而言，这是一个有趣，复杂和困难的同题为了实现这个目的，就必需先 破坏其对称性为此，著名的图论学家w t t u t t e 于上世纪6 0 年代提出了一种给地 图标根的方法从此，地图的计数理论的研究便诞生了 自从地图的计数理论提出以来，受到了众多学者的关注经过半个多世纪的发展， 对它的研究已有多个方向，但主要集中在以下两个方面； 问题1 在同构意义下，给定某些性质p ( 如曲面的亏格g 曲面的定向性等) 和某 些参数( 如点数、边数或面数等) ，有多少个不同的( 无根) 地图? 问题2 在同构意义下，给定某些性质p ( 如曲面的亏格g 、曲面的定向性等) 和某 些参数( 如点数、边数或面数等) ，有多少个不同的带根地图? 1 2 研究问题的历史和现状 在本节中，我们将简要的介绍根地图计数的历史背景及发展状况为解决著名的 四色问题，图论学家w t t u t t e 在二十世纪六十年代初首次提出了平面地图的计数 理论，他最初的几篇有关平面地图计数的综述性【8 鼬8 】文章，奠定了平面地图计数理 论的基础随后，w g b r o w n 【l s - 2 0 ，r c m u u i n 【7 2 - v s ，f h a r a r y 【3 7 - 3 9 以及 北京交通大学博士学位论文第一章绪论 w t t u t t e 8 9 - 1 0 2 】本人对w t t u t t e 先前的工作进行了进一步的推广和简化先 后研究了极大平面地图，不可分离平面地图，三正则平面地图和平面树的计数问题 到上世纪八十年代初，由于平面计数方程的出现，很大程度上简化了平面地图的计数 过程和结果，是方法上的一个转折点后来，一些学者如y ，p l i u 【4 7 _ 6 7 1 ，e a b e n d e r 5 - 1 1 ，z c g a o 2 6 - 3 2 1 ，j l c a i 【2 1 2 3 等又进步研究了各种平面地图， 得到许多很好的结果 在平面地图计数提出后不久。w ，g b r o w nf 1 9 于1 9 6 6 年首次提出了非平面地 图的计数在这个方面，t w a l s h 和a b l e h m e n 1 0 4 - 1 0 6 】在上世纪七十年代做了 些基础性工作，他们深入的研究了任意亏格的可定向曲面上根地图的计数，并且给出 了单面地图的直接计数公式接着，d m j a c k s o n 【4 0 】用代数的方法也得到了任意 亏格的可定向曲面上单顶点地图计数公式后来，a b e n d e rp 1 1 ，d a r q u e s 【l - 4 1 ， y p rl i u 4 7 - 6 7 ，z c g a o 【2 8 - 3 2 ，h r e n 7 6 - 8 2 】等进一步研究了给定曲面上各 种非平面地图的计数问题对于不可定向曲面上地图的计数，大部分的文献都是集中 在小亏格的曲面上，如射影平面，k l e i n 瓶等直到2 0 0 0 年，d ，a r q u a s 【3 1 最先得 到了亏格为3 和4 的不可定向曲面上一般地图的计数公式 1 3 基本概念和方法介绍 本节首先给出一些基本概念文中出现而未解释的术语，可以参照 6 4 - 6 5 有两侧的闭曲线被称为双侧曲线；否则称为单侧曲线 啦面就是个无边界的紧致的2 - 维流形个曲面，若其上的所有闭曲线全是双 侧的，则称它是可定向曲面；否则为不可定向曲面亏格为g 的可定向( 不可定向) 曲 面同构于一个球面带有岔个手柄( 叉帽) ，记为s o ( ) ( i eg = 1 一 x 或= 2 一配 其中x 是欧拉示性数) 设x = z 1 ，2 7 2 ，) 是一个有限集，k = 1 ，p ，7 是一个k l e i n 群，即， 0 2 = 俨= 7 2 = 1 ，其中7 = o p = p a 对于z x ，k 2 7 = ( 2 7 ，q z ，p z ，7 z 如果定义 在咒口( x ) = k 观= 爿上的置换p 满足下列条件对于任意的f n 和任意的 o 石，。o t x ，a t = p 1 n ，且是r = a ，黟，7 生成的群惦在z 是可迁的。 那么m = ，尹) 就被称为一个地图如果地图m = ( z ，p ) 有一个元素，记为根 r = r ( m ) ，事先被标识出来，则称地图是带根地图被标识的边就称为根边，与 2 北京交通大学博士学位论文第一章绪论 根相连的点被称为根点，根所在的面称为根面对于个地图m ，它的根、根点 根边和根面分别表示为r ( m ) ，v r ( m ) ，e r ( m ) 和厶( m ) 本文研究的地图如无特殊说 明，都是带根地图 在这篇论文中，我们总要利用欧拉公式和l a g r a n g i a n 反演，为了方便，把它们作 为定理给出来 定理1 1 【6 6 , 定理i 1 2 】( 欧拉公式) 对于一个给定的曲面5 ，个图g 在其上的 任何一个嵌入“总有e u l ( i z g ) = u ( u a ) 一e ( u a ) + o ( u a ) 只与s 相关而与g 无关 进而。 删( 艄： 2 2 p p 0 ，5 s p i 2 一q ， q 1 ，s 在给出l a g r a n g i a n 反演之前，我们首先引进一些符号令签= ( x l ，x 2 ，z 。) 为一个m 一维向量，m 1 ，它的每个分量均为不定元和量= ( k l ，也，k ) 表示 在幺半群萨中雹的幂为，m i 1 对于，( 匐，9 1 ( 墨) ，( 曼) c 冗，兰) ，令 y ( 吼) = ( y ( m ；z 1 ) ，y ( 吼；。) ) ，其中 v ( 9 i ；) = m i n l i 硅，g i o ) ，j = 1 ，2 ，m 令 f 刍乳。艘q ； 罐= 【庐l 。，i = m e r ( m ) im 朋；j 则t m ：j ， = 朋。t ( 2 2 2 ) ( 2 2 3 ) ( 2 2 4 ) 其中，丁是所有平面树的集合，x 表示集合间c a r t e s i o n 积 证明；对于任何一个地图m 朋；f ，由m 的根边e r ( 肘) 是割边，以及集合m 的特征，m e r ( m ) 则由两个地图组成：一个是m 。中的元素，另个是丁的元素 于是m e r ( m ) m 。t 所以朋： m 。丁 反过来，对于( j ) l 矗，m 2 ) m 。丁，尬m 。，m 2 t 我们可以通过如下方 式构造地图m 7 ：添加一条新边连接m 和 如的根点，并使之为m 根边；同时选 择a n 的根点作为m 根点这样，m m ；j 且一唧( m ) = ( 矗，尬) 所以， 。丁a 4 乏f r ) 个地图被称为植树，如果它是个带根的平面树且根点次是1 设五是所有 植树的集合，矗= h ( z ，y ，。) 是它的计数函数，则， 向( 毛! ，z ) = 盯y f z “ f x y 2 z ! l ( m ) z n m e t z y 2 z ( 鲁) m m 郅一 。l 珂。i 莓 9 北京交通大学博士学位论文 第二章边界三正则平面地图的计数 于是，矗= ；( 一咧 根据引理2 2 ，m ；，对，m c 的贡献，m ；，则为， 凡 ，= 矗凡一；( 1 一瓠= 硐凡c ( 2 2 5 ) 5l 理2 3 设乏i i i = a f e r ( a ，) im , m 。e ) 贝0 m ：j i j = 3 4 。 证明：对于任何个地图m m ；m 因为根边c r ( ，) 不是割边，由m ；，的定 义可知，m e r ( m ) m 。 另一方面，对于任何一个m m 。，其根面次为i ( m ) ，从吖可以得到地图m ： 在地图m 添加一条新边作为m 的根边，新边一端连接m 的根点，另一端连接m 根面上任何个角因为有两个环与m 的根点( m ) 相关，所以一共有( i ( m ) + 1 ) 添加新边的方式 根据引理2 3 ，以及根边对于根点次的贡献：考虑根边是环与否，分别是2 或1 ， 可以得到m j ，f 对厶d c 的贡献加；。为； l ( m ) “；。= x y z ( y ) z ”z 州一x y z 凡c ( z ，1 ，z ) “c m e j t 4 i = 0 + z 2 妒z ，m c ( z ，1 ，名) a 1 c ， 化简即为； 凡= 篙( c v f m c ) 一( 1 - x ) 叫z 巩c 加， ( 2 ，2 6 ) 其中，玎d c = ，m c ( z ，1 ，z ) ，l e c ( 即) = 扩盯z 州 ( 2 2 7 ) m e a t c 引理2 4 由( 2 2 2 ) 定义的计数函数， l c ( 为y ，z ) 满足下列的函数方程 ， 。一止譬h 刊彬帕：。k 北京交通大学博士学位论文 第二章 边界三正则平面地图的计教 = 1 一y + x y z 如c 其中，f h ( 。，z ) = ，m c ( 毛1 ，z ) 证明；由( 2 2 1 ) ，( 2 2 3 ) ，( 2 2 5 ) 和( 2 2 6 ) ，我们可以得到： 加。：加；+ “；，+ 凡：，+ 尘二塑2 二塑加。 + 尚( 凡c g 加c ) 一( 1 - x ) 彬砌c 儿c ， 化简整理，即可得到( 2 28 ) 在( 2 2 8 ) 中，令z = 1 ，即得下面函数方程： ( 2 2 8 ) ( 1 - ”) ( t 一生等丝) + y 2 z h “。= l - y + y z 。， ( 2 z 9 ) 其中，乩一凡c ( 1 ，y ，z ) ，c = 加( 1 ，1 ，z ) = 如c ( 1 ，z ) 设y = f ( z ) ，代入到方程( 2 2 9 ) 中，同时令等式两边等于0 ， i e j ( ，一o ( 一! 华) + ：z ：。( 订 l 1 一+ ：，c = 0 ( i i ) 从( ) ，则有， 2 z = 幢一1 ) ( 2 一f ) 设q = f 一1 ，贝4 ， 町= 筹z 利用l a g r a n g i a n 反演，我们得到， u z 一是 行十上 北京交通大学博士学位论文 第二章 边界三正则平面地图的计数 制机c = ：o ( n - - 1 滞高( 希 2 1 _ a ( - ，i 协1 ) 2 釉刍，斜 一s ( 2 札一2 ) ! ：p! 竺二型 台n l k t ( n 一1 一) 2 = 黔瑞， 于是蛳= 互z “黔瑞巩沈 h c 2 萎z ”慕尚扩= l + 2 z + 8 2 2 + 纠+ 2 2 a 冉坝a 舢( 2 2 1 0 ) 定理2 1 边界三正则内森林地图，以去捧根面边界的边后所得到的森林的边数 n 1 ) 为参数，不同的地图的个数n m ( n ) 为； = 器， 证明；由引理2 1 和( 2 2 1 0 ) ，定理得证 边界三正则内树地图，作为它的一个特例，两个参数精确的计数公式被得到 设朋是所有边界三正则内树地图的集合，m i 是它的收缩地图集合类似的， 九。，定义为m 。的计数函数，i e 九g ( x ，y ，。) = x m ( ”) 2 ( ”) z ”( 肘) ( 2 2 1 1 ) m e h d e 引理2 5 由( 2 2 1 1 ) 定义的计数函数k 满足下面函数方程t ( 1 - y + x y z ) 九。，_ ( 1 刊x 2 y z + 巫毛型( 1 _ 咧+ 矾巾2 1 2 ) 其中，= 九。，( 曩1 ，：) ， 。 ，= ( ) = 一( 肘) z 叫) ，( 2 2 a 3 ) m v i j 北京交通大学博士学位论文 第二章边界三正则平面地图的计教 证明：集合m 被分成两个子集：朋；和朋矗，i e 朋。= m ；+ 朋知 其中， im 净 m 朋。ie r ( m ) 是割边 ； im ；尸 m m 。le , - ( m ) 不是割边 类似引理2 2 ，引理2 3 和引理2 4 ，即得下面的方程t 九一= ；( 1 一以j 再) + 鲫z ( i ( m ) - i 矿) 。州+ z 2 鲈 m e j l ，l g = l = ；( ，一乒丽) + 两x y 2 z 。一尚九。，+ ”z 化简整理，即得( 2 2 1 2 ) 引理2 6 由( 2 2 1 2 ) 定义的计数函数。，有下面精确的表达式 ( 2 2 1 4 ) 一m + 。是。篙揣比” ( 2 。) 证明；设y = f ( 卫，z ) ，代入( 2 2 1 2 ) ，令等式两边等于0 ， i e f1 一f + f z ：= 0 ( 1 ) i ( 1 - 铋护外学( 1 一- 4 f 2 z ) z z 一= 0 ( 2 ) 设”= f 一1 ，根据( 1 ) ，我们有叩= ( ，7 + 1 ) x z 设口= ( 叩+ 1 ) z 妒1 = 1 ( p ，r ) = q + 1 ，屯= 2 ( p ，r ) = ，7 + 1 ，则 于是， p = 咖l z ；田= 西2 z z 一= 鼎+ 蒜( ，一v 1 - 4 f l ( r + 1 ) ) 北京交通大学博士学位论文第二章边界三正则平面地图的计数 郇问：f ，1 。乒豢 也a 归 糕 一= 嘞+ 1 ) + 1 ) 。南) = 缁- l r 2 ( 1 + ) m + k - z + 7 ( 1 + q ) “* l ( 2 0 1 a c 1 + 町) 4 】 当= 一1 ，那么m = 2 ，则 a 掰p 1 ”2 ( 1 + q ) 一1 乩娩罐暑，= 1 ( 2 2 1 6 ) 当k 0 ，则 错h r “若揣卯刊 = 鼎( 2 。：二f 1 ) 令n = m + k ，我们有 榴= 嵩( 2 n ，= ：二f 1 ) ：! ! 兰二竺二! 卫 ( n m ) k n m + 1 ) ! 由( 2 2 1 3 ) ，( 2 2 1 6 ) 和( 2 2 1 7 ) ，即得( 2 2 1 5 ) ( 2 2 ，1 7 ) 定理2 2边界三正则内树地图以根面次z ( f 1 ) 和边数n 为参数的计数函数 h - ( ，z ) 有下面精确的表达式， 日z ( ，。) = y 2 2 3 + 。：，e 。：甜i i i ! ；i i ；! ! ；：；! 丢v l ：n ( z 。- s ) 南 = ， 堕酉音鼍 北京交通大学博士学位论文第二章边界三正则平面地图的计数 证明t 根据引理2 1 ，( 2 , 2 1 6 ) 和( 2 2 1 7 ) ，分别以# 和竹一f 替换m 和n ，则得 ( 2 2 1 8 ) ，即 l ( 玑z ) = y z 2 + + 2 y z 4 + 5 y z 5 + 1 4 y z 6 + 4 2 y z 7 + 1 3 2 y z s + 4 2 9 y z 9 + 1 4 3 0 y z l o + + 笋2 夕+ 2 + 3 y 2 2 5 + 1 0 y 2 + 3 5 y 2 2 7 + 1 2 6 y 2 z s + 4 6 2 y 2 2 ：9 + 1 7 1 6 y 2 2 1 0 + 说明在( 2 , 2 1 8 ) 中，分别以1 和n + 2 替换f 和n ，我们即得一个已知的结果 一w t t u t t e 公式 ( n ) ：以边数为参数的平面根地图的计数公式，l e 帅，= 意 设朋。是所有边界三正则内森林地图收缩集合朋。的对偶集容易看出，朋。是 外平面地图集合类似的，朋。的计数函数， 。定义为： i e 九。= f m 。( z ，y ，z ) = z “( ( m ) z n ( 川 ( 2 2 1 9 ) 盯川。 定理2 3 由( 2 2 1 9 ) 定义的计数函数厶l 。满足下列函数方程 ( 1 一z ) 1 一y ( 1 - _ 厂一+ ( 1 一，) 彤乩j + x 2 y z f 朋。 = 1 一z + x y z 。，( 2 , 2 2 0 ) 其中， 。= ，m 。( 1 ，y ，z ) 证明t 根据对偶理论，以y ，z 和 k 。分别替换( 2 2 8 ) 里的文y 和f k c ，即得 ( 2 2 2 0 ) 北京交通大学博士学位论文 第二章 边界三正则平面地目的计数 定理2 ，4 外平面地图以边数n 为参数的计数公式 k 。( ) 为 m 加苦揣 证明s 根据对偶理论和( 2 2 1 0 ) 式，定理即证 2 3 边界三正则地图 根据引理2 1 ，为了确定所有边界三正则平面地图所构成的集合的元素的个数 只需确定所有平面地图所构成集合的元素的个数 设m 。是所有平面地图的集合，m ，= ，m ，( z ，玑。) 为它的计数函数， ，m 。= x m ( m ( 吖矿( ”) m e m 。 其中m ( m ) ，l ( m ) 和n ( m ) 分别是m 根点次，根面次和边数 0 e ( 2 3 1 ) 类似计数函数，m c ( z ，f ，z ) 的推导，我们有下面引理： 引理2 7 由( 2 3 1 ) 定义的计数函数，m 。满足下面函数方程： ( 1 一) 1 - - x y 2 z h m 。+ ( 1 一z ) z z f m 。】+ z 2 。) “= 1 一+ 。2 尸m ，( 2 3 2 ) 其中，h a 。= 饥。( 1 ，y ，z ) ，。= 儿。( z ，1 ，：) 兮【2 3 n ) 甲z = 1 ，则 ( 1 一笋) 可2 。月办。一( 1 一y + 型2 z ) 目m + 1 一y + 剪名，l 朋。= 0 ( 2 3 3 ) 由( 2 3 3 ) ，能够导出下面参数表达式： ”2 两i ；2 酉希 利用l a g r a n g i a n 反演，则有。 搿h 。= ：槲 ( 南) “而d ( 播) 】 = ：稍 i f 驴6 一丽4 一尚】 = z 铲意， 北京交通大学博士学位论文第二章边界三正则平面地图的计数 所以， 2 乏z - s n 杀南z n = l + 2 z + 9 2 2 + 科蝴s 冉舢冉( 2 s 4 ) 说明( 2 3 。4 ) 是w t t u t t e 【8 8 】个已知公式：一般平面地图以边数n 为参数 的计数公式 定理2 5 边界三正则平面地图，以非根面的边数n 21 ) 为参数的计数公式 k 。( n ) 为t 酬垆z 驴茄嵩 证明；根据引理2 1 和( 2 3 4 ) ，定理即证 设集合m ：是集合朋。的对偶集，容易看出，m ：也是平面地图集合m ：的 计数函数a l ：为： 凡：( z ，y ，z ) = x m ( m ) y 州z 州， m 朋： 引理2 8 由( 2 3 5 ) 定义的计数函数，m ：满足下列函数方程， ( 1 - x ) 1 一x 2 y z ：+ ( 1 一y ) z y z h m ： + z 2 9 z ) 凡： = 1 一z + x y z h m ； 其中，乩：- “；( 1 ，y ，z ) ，：- 加池1 ，z ) ( 2 , 3 5 ) ( 2 3 6 ) 证明t 根据对偶理论和( 2 3 2 ) ，分别用y ，z ， ：和见以替换( 2 3 2 ) 中的z ，y ，k 和 。，即得定理 在( 2 3 6 ) 中。令y = 1 ，则有下面方程t ( 1 一z ) z 2 名j ：一( 1 一+ 护z ) j ：+ 1 一z + z z 州：= 0 ， ( 2 3 7 ) 其中，h m ：= 知：( 1 ，1 ，z ) 1 7 北京交通大学博士学位论文 第7 - 章边界三正则平面地图的计数 式 引理2 9 【2 3 , 定理5 1 】 由方程( 2 3 7 ) 确定的计数函数f 也有下面直接表达 其中， ：2 薹矗筹备p 扩+ 丢妒c m ，嘶_ 札 c z 矗s ， 妒( m ，n ，i ，j ，) = 仇一1 ，l i 2 ”州 k = o _ j 2 0 2 n 一一2 、 i1 馆一。一， 筹t t4 - 蔷端茜黼i 4 - ，仁s 功(1 ) ! ( 2 i 一) ! ( 一i ) ! ( 一2 ) 01 、7 定理2 6 边界三正则地图，以根面次f ( f 1 ) 和边数n 为参数的计数函数 f 如( ，z ) 有下面精确的表达式t = 揣 甜+ l 。n - ，妒( i , n - l , i j , k ) 一 l = m e r ( m ) im m i l ，则有m ”= m i 证明，对任意m 朋2 1 ，因为m e r ( m ) 是个单面地图，而且m e ，( m ) 点 数和面数与m 的相等但边数比之少1 ，由欧拉公式，m 一白( m ) 的亏格比m 少1 又因为m m ，所以m e r ( m ) m i 另一方面，任意给定m 朋i ，其边数是s ( m ) ，则从m 有1 2 s ( m ) + 1 ) 种添边 方式构造地图m m ：从m 的根点到它的根面的每个角都可以添加新边以构成新 的根边，使得m 也是个单面地图因为m m i ，由欧拉公式，m 是k l e i n 瓶 上的地图这样m m 2 1 且m = m e r ( m ) 由引理3 2 2 ，我们可以得到朋1 1 对于，鸭贡献，m ! - 是t 凡争= z ( 2 s ( m ) + 1 ) z 棚= 2 护厶i + z 加i ， ( 3 2 4 ) m e m i 其中凡i = _ d f m f t ( x ) 北京交通大学博士学位论文 第三章曲面上的本质地图 引理3 2 ，3 设m ；缈= m e r ( 肘) lm 朋笋 ，那么朋；协= 玩 证明t 对任意m 朋擎，根据定义，m e r ( m ) 是有两个面的地图而且容易看 到，m 一岛( m ) 边数比m 少1 ，面数比它多1 ，但它们点数相等根据欧拉公式， m e r ( m ) 的亏格比 少2 ，于是其亏格是0 因为 ，一e ，( m ) 具有两个面，所以 m e r ( m ) d o 反之，任意给定m 7 玩，其第二面的面次是k ( m ) ，从m 有k ( m ) 种方式构 造地图m ：通过添加一条扭边作为新的根边，新边的一端连接m 。的根点，另一端可