（交通运输规划与管理专业论文）论曲面上给定基础图的地图.pdf

中文摘要 地图源于曲面分解的研究拓扑学中有一个十分著名的定理：任意 一个曲面都可以进行三角剖分( t r a d o ，1 9 2 5 ，见 5 5 】) 这一结果使 得任意一个曲面均可以分解成一组不相交的2 维胞腔的并，同时奠定 了采用组合方法研究地图的理论，这就是拓扑图论，包括图的曲面嵌 入和曲面上地图计数两大分支 从n l t t e 于1 9 6 2 年开创性研究平面地图计数( 见【6 2 】) 以来，许多 学者相继完成了一大批地图计数，特别是平面地图计数的研究工侮 目前已经形成了一套计数理论该理论中的计数方法主要有三种：f 分 别介绍如下厂y 双射方法ft u t t e 率先将该方法用于平面标根e u l e r 地图的计数 4 4 1 证明了节点数v 、边数s 且次为2 i 的非根节点数为q i ，根次为2 m 的 平面标根e u l e r 地图数为， 告蒜蒜曩上q i 11 q ic 黜1 户( 一+ 2 ) !m ! ( m 一) ! 。怂、i ! ( i 一) 1 7 实际上，这种方法本身就是组合计数的基础，同时它还广泛地应用 于后面介绍的解析方法和代数方法中给定一个3 一连通图，通过建立 射影平面地图的平面双覆盖与3 连通平面地图的l 一1 对应，n e g a m i 得到了其在射影平面上的不等价嵌入的计数结果【6 0 】在【3 7 中，j i n h ok w a k 和j a e u nl e e 得到了图的不同余嵌入计数结果- 严格讲，文献 【3 7 】和f 6 0 】中讨论的计数并不等价于不标根地图的计数力呵一 解析方法f 这种方法，目前是地图计数，特别是标根地图计数的核 心许多学者，如t u t t e 、b r o w n 、w a l 8 h 、b e n d e r 、刘彦佩、高志成 等，曾先后在这一领域作出过贡献如今，它已经发展成为一种计数 标根地图的系统方法，分解为以下四步， 第一步，对地图集合进行适当分解； 第二步：建立函数方程； 第三步：寻找参数变换； 第四步：利用l a g r a n g e 反演求解计数函数 中文摘要 w a l s h 和l e h m a n 在七十年代初研究了曲面标根地图的计数问题他 们证明了计数函数r ( 叫= 姜f n 4 ，这里r ，；表示节点数为i + 1 ，边 数为n + i 的标根地图数，满足以下方程【8 0 】一【s 。】： n r ( z ) = z 以( 。) r k ( 。) + ( 2 n k = 0 d a r q u e s 和j f b e r a u d 证明了计数函数m ( y ，：) = m o y s z ，这 里m ( s ，j 表示可定向曲面上节点数为s ，边数为，的标根地图数，满足 r i c c a t i 方程【2 】l 舟 2 2 2 豪f ，( ，。) = - y + ( 1 一z ) m ( y ，。) 一z m ( y 。) 2 事实上，刘 4 4 j 在此之前就已经给出了这个方程在y = l 的情形，其分 解理论是相同的 对亏格为g 的可定向曲面，b e n d e r 和c a n f i e l d 证明了以边数为参数 的计数函数f ( z ，g ) 有下面形式纠， ，、2 幻只f p ) 八枷卜灭再研石蒋而而 这里，p = 饥丁西，n ，b ，e 为正整数，b ( p ) 为p 的多项式 文献【z s ，【4 4 】， 4 7 卜【5 0 】和【6 7 】- 【6 8 】中，还可以看到更多采用这种方 法进行地图计数的成功范例小7 一。 代数方法f 采用代数方法计数地图，主要包括对称群的群代数和b u r n s i d e 引理在地图计数中的应用两都份文献【3 0 】一【3 6 r 中，j a c k s o n 和 v i s e n t l n 开创了群代数理论用于地图计数的方法他们得到了以节点 数、边数和面数为参数的计数函数朋( 孔，z ，y ，。) ， ，f ( u 。，o ，y ，z ) = j u l o g r ( x ，y z ) ， 这里 n 。f ( x , y , z ) = 2 u 2 毫z f ( x u - i ，y u - 1 , 扣 和 r ( 训蜘萎莉磊，。x n 】h e ( 02 n 。) 胁( y ) n 、， 中文摘要 这里，8 表示口的阶，h e ( z ) =兀( 3 一i + 1 ) ( 日“，且口：( 口。口2 1 ) 为整数2 n 的划分，巩o ，。( ”j = z ( x + 1 ) ( 。+ n 一1 ) 作为一个特例，他们得到了 3 3 】： m ( y ：) = 2 z 豪l o g 石衰了( g + 1 ) ( + 2 n 一1 ) ：“ 与标根地图计数相比，不标根地图的计数结果从数量上则相形见 拙利用球面的自同构特性并基于b u r n s i d e 引理，l i s k o v e t s 提出了一种 计数平面不标根地图的一般方法由此，l i s k o v e t s ，l i s k o v e t s 和w a l s h 得到了关于一般平面地图、正则平面地图、e u l e r 平面地图、平面自对 偶地图和2 一连通平面地图等的许多计数结果例如，他们得到了2 一连 通不标根平面地图的如下计数公式： 去【b 7 ( 札) + ； 妒( 等) ( 9 t 2 9 t + 2 ) b ( t ) + a ( 佗) ， 。t i m ，l t _ n 。 这里，若扎为奇数，则a ( n ) = n 。+ l b 7 ( 学) ，若n 为偶数，a ( n ) = 3 n f - - 4 b 蟾) ， 州= 怒蒜 和妒( t ) 为e u l e r 函数 b i g g s 和w h i t e 在1 9 7 9 年提出了一个计算图的不等价嵌入的一般公 式通过确定任意节点”和图的自同构口的稳定集r ( o ) ，该公式后成 功应用于完全图、轮图和完全二部图的不等价嵌入数计算i n ，【5 8 】一【5 9 】 尽管这一公式是框架型的，并非对每个图都能得到简洁的计算公式， 但同样的思想用于计数曲面( 可定向或丕可定向) 上给定图的标根地 图却非常有效( 见本文第四章) ， 因任意图的嵌入可由这个图唯二一个可定向嵌入导出f 2 5 p 引由e d m o n d s 对应心m ，图的可定向嵌入与图的旋集是1 1 对应的。通过研究 图的一般旋集在其自同构群作用下的分类，我们同样可以研究曲面上 地图计数问题本文的主要目的就是研究给定一族图，计数以它们为 基础图的标根与不标根地图f 共分为五章，各章的主要结果和方法介 绍如下： i 第一章讨论了图的可定向嵌入生成的一般嵌入的代数方法证明了 两个一般嵌入同构当且仅当这两个一般嵌入下的可定向嵌入同构通 过引入图的半边自同构群的概念，这一章提出了计数曲面( 可定向或 不可定向) 上不等价嵌入和不标根地图的一般计算公式，由此可得到 中文摘要 计算给定基础图的曲面地图的步骤，同时理解第二章的论题在本文计 数不标根地图中所起的作用 第二章研究了给定一个连通图，该图的哪些自同构是地图自同构 这是计数曲面上图的不等价嵌入与不标根地图的前奏曲这一章确定 了基础图为完全图、自同构群为顾g ) h 的c a y l e y 图和半正则作用图 的地图的自同构当然，这一章的论题也可以看作是研究图的自同构 群方面一个独立问题 基于第二章关于地图自同构的结果，第三章计数了基础图为完全 图、自同构群为r ( g ) h 的c a y l e y 图和半正则作用图的不等价嵌入， 同时计数了基础图为完全图和自同构群为月( g ) xh 的c a y l e y 图不标 根地图这一章一个十分有趣的结果是，给定一个连通图，在其最大 不可定向曲面上的地图数正好等于该图在可定向曲面上的所有地图总 和，从而使得我们可以计数不可定向曲面上的地图 第四章计数了曲面( 可定向或不可定向) 上给定基础图族的标根地 图与不标根地图情形不同，曲面上给定基础图的标根地图数是无和 式，从而可用于寻找给定基础图的计数函数或方程式利用图上半边 自同构群的概念，讨论了图的亏格分布多项式与以此图为基础图的标 根地图在曲面上的分布多项式之间的关系，并由此得到了基础图为端 闭合的梯图及环束的标根地图在曲面上的分布这一章还讨论了单面 标根地图的计数 第五章一般性地讨论了地图计数中几个值得进一步研究的问题及方 向有些问题已经引起人们的重视，而有些，则还未引起人们的关注 地图计数问题几乎涉及到数学的每个角落，拓扑、几何、代数、分 析、方程等等数学中每个分支的发展对地图计数理论都会有所促进 意识到这一点，读者就会理解文献【3 】3 一 4 1 ， 9 】一【1 1 i ，【2 0 卜【2 2 】和【8 6 卜 9 3 】 在我们的研究工作中的作用卜万7 一 ( 鼢颤弓：地圈，参峒，地固瓠髻，渤l 砚抒彳 圈近 a b s t r a c t m a po r i g i n a t e sf r o mt h ed e c o m p o s i t i o no fs u r f a c e t h e r ei s aw e l l k n o w n t h e o r e mi nt o p o l o g yw h i c hs t a t e st h a te v e r ys u r f a c ec a nb e t r i a n g u l a t e d ( t r a d o ， 1 9 2 5 ，s e e1 5 5 1 ) t h i sr e s u l te n a b l e su st od e c o m p o s ea n ys u r f a c ei n t oas e to f d i s j i o n td i s k sa n df o u n d st h eb a s eo fc o m b i n a t o r i c a l l yr e s e a r c h i n gm a p s ，t h a ti s ， t o p o l o g i c a lg r a p ht h e o r y ，w h i c hi n c l u d e se m b e d d i n g s o f g r a p h a n dt h ee n u m e r a t i o n o fm a p so ns u r f a c e s t h ee n u m e r a t i o no fm a p so ns u r f a c e s e s p e c i a l l y , t h es p h e r e h a sb e e ni n t e n s i v e l yi n v e s t i g a t e db ym a n yr e s e a r c h e r ss i n c et u t t e sp i o n e e rw o r ki n1 9 6 2f s e e f 4 4 1 ) a sw ek n o w n ，t h e r ea r et h r e em a i nt e c h n i q u e si nt h ee n u m e r a t i v et h e o r y o fm a p s w h i c ha r ej n t r o d u c e da sf o l l o w s ： b i j e c t i v et e c h n i q u e ，w h i c hw a sf i r s t u s e db yt u u t ef o rt h ee n u m e r a t i o no f r o o t e dp l a n a re u l e r i a nm a p s 4 4 h ep r o v e dt h en u m b e ro fr o o t e de u l e r i a np l a n a r m a p so fo r d e r a n ds i z e w i t ht h en u m b e r o fn o n r o o t e dv e r t i c e so fv a l e n c y2 i b e i n g 毋a n dt h ev a l e n c yo f t h er o o t e dv e r t e xb e i n g2 mi s ( 一1 ) ! ( 一+ 2 ) ! t h i s t e c h n i q u e i sf u n d e m e n t a lf o rc o m b i n a t o r i c a le n u m e r a t i o ni ng e n e r a l i t y , w h i c h i sa l s ow i d e l yu s e di nt h ea n a l y t i ct e c h n i q u ea n da l g e b r a i ct e c h n i q u e f o rp r o j e c - t i v em a p sw i t hag i v e n3 - c o n n e c t e du n d e r l y i n gg r a p h ，n e g a m ig o tt h ee n u m e r a t i o nr e s u l tf o rn o n - e q u i v a l e n te m b e d d i n g sb ye s t a b h s h i n gt h ec o r e s s p o n d e n c e o fd o u b l ep l a n a rc o v e r i n go fp r o j e c t i v em a p sw i t hp l a n a rm a p s 8 0 1 i n 3 7 j ，j i n h ok w a ka n dj a e u nl e eo b t a i n e dt h en u m b e ro fn o n c o n g r u e n te m b e d d i n g so f ag r a p h i nf a c t ，t h et o p i c sd i s c u s s e di n 【3 7 】a n d 6 0 】a r en o te q u i v a l e n tt ot h e e n u m e r a t i o no fu n r o o f e dm a p s a n a l y t i ct e c h n i q u e ，w h i c h i st h ec e n t r a lt e c h n i q u ef o rt h ee n u m e r a t i o no fm a p s ， e s p e c i a l l y , r o o t e dm a p s m a n y r e s e a r c h e r sc o n t r b i u t e df o rt h i st e c h n i q u e ，s u c ha s ， t u u t e ，b r o w n ，m u l l i n ，w a l s h ，b e n d e r ，l i uy pa n dg a o z c n o wi th a sb e e n d e v e l o p e d as y s t e mm e t h o df o re n u m e r a t i n gm a p s ，w h i c hc a nb ed e c o m p o s e da s f o u rs t e p s ： s t e pl ：d e c o m p o s et h es e to fm a p s s t e p2 ：e s t a b l i s he q u a t i o ns a t i s f i e db yt h ee n u f u n c t i o n s t e p3 f i n dp r o p e r l yp a r a m e t r i c e x p r e s s i o n s e t p 4 ：s o l v i n ge q u a t i o nb yl a g r a n g ei n v e r s i o n w a l s ha n dl e h m a nc o n s i d e r e dr o o t e d m a p s o i lo r i e n t a b l es u r f a c e si n1 9 7 2 i s o l - 8 2 t h e yp r o v e dt h a tt h ee n u f u n c t i o nr ( 。) = r ，t 。，w h e r er id e n o t e st h en u m - b e ro fr o o t e dm a p sw i t hn + i e d g e sa n di + lv e r t i c e s s a t i s f y i n gt h ef o l l o w i n g n f d x ) = 。f k ( x ) f 一d x ) + ( 2 n k = 0 d i d e ra r q u 6 sa n dj e a n f r a n c o i s m ( s ，0 y 5 z 2 ，w h e r em ( s ，f ) d e n o t e s ，1 1 ) r 一，( z ) + 2 z 导只 x b s r a u dp r o v e dt h ee n u f u n c t i o nm ( y ，。) = t h en u m b e ro fr o o t e dm a p so i lo r i e n t a b l e s u r f a c e sw i t ho r d e rsa n ds i z ef ，s a t i s f y i n gr i c c a t i se q u a t i o n 2 2 。2 差 m ( y ，圳= 一y + ( 1 - - z ) m ( ，z ) 一：m ( ，。) 。 i nf a c t ，l i u 4 4 】p r o v i d e dt h ee q u a t i o nw h e ny = 1b u tw i t ht h es a m ed e c o m - p o s i t i o ne a r l i e rt h a nt h a tw h a ta p p e a r si n 【2 】 f o rm a p so no r i e n t a b es u r f a c ew i t hg e n u s g ，b e n d e ra n dc a n f i e l dp r o v e dt h a t t h ee n u f u n c t i o n ，( ，g ) w i t hs i z ea st h ep a r a m e t e rh a st h ef o l l o w i n gf o r m 7 1 ： m 圳= 万斋， w h e r e ，p = 、1 1 2 z ，a n dn ，b ，ca r ei n t e g e r sa n db ( p ) i sap o l y n o m i a lo fp m o r e t y p i c a le x a m p l e sc a nb ef o u n di nt h er e f e r e n c e s 【1 8 【4 4 ， 4 7 卜【5 0 】a n d 【6 7 】一【6 8 】 a l g e b r i ct e c h n i q u e ，i n c l u d i n gt h ea p p l i c a t i o no fg r o u pa l g e b r at h e o r yo fs y m - m e r r yg r o u pa n db u r n s i d el e m m a ，i sp o w e r f u li ne n u m e r a t i o no fr o o t e do ru n r o o t e dm a p s i nt h er e f e r e n c e s a o l 一 3 6 1 ，j a c k s o na n dv i s e n t i nd e v o l o p e da l l a p p r o a c hf o re n u m e r a t i o n o fr o o t e dm a p so ns u r f a c e so f g e n u sgw i t hp a r a m e t e r s t h eo r d e r ，s i z ea n dt h en u m b e ro ff a c e so fm a p s t h e yh a v eg o t t e nt h eg e n u s s e r i e sm ( u ，z ，y ，z ) o no r i e n t a b l es u r f a c ew i t hg e n u s g f a a l 一【3 4 j ： w h e r e a n d m ( “2 ，z ，3 ，z ) = q 。l o g r ( x ，yj ? ) n 川舢= 2 “2 瓦g o 卅u - 1 刚1 ，；删 即荆2 聂莉蒹，帅删此 w h e r e 尸d e n o t e st h eo r d e ro f0 ，h o ( x ) = l - ( x i + 1 ) ( 口“，w h e r e ，0 = i s i s l ( o ) ( 0 1 0 2 ，一口“引) i s t h ep a r t i t i o no f2 n ，0 0a n dz ( ”l = 。( r + 1 ) ( t + n 一1 ) a sas p e c i a lc a s e ，t h e yg o tm ( y ，z ) a sf o l l o w s 0 3 ： m ( y ，：) = 2 。羞1 。g 三南y ( y + 1 ) ( y + 2 n 一1 ) ：“ c o m p a r i n gw i t hr o o t e dm a p s ，o b s e r v a t i o nf o rt h ee n u m e r a t i o no fu n r o o t e d m a p s o ns u r f a c ei sn o tm u c h ，b yu s i n gt h ea u t o m o r p h l s m so fs p h e r e ，l i s k o v e t s p r e s e n t e da ne n u m e r a t i v es c h e m ef o ru n r o o t e dp l a n a rm a p sb a s e do nb u r n s i d e l e m m a ( s e e 4 1 【4 3 】) l i s k o v e t s ，w a l s ha n dl i s k o v e t sg o tm a n ye n u m e r a t i o n r e s u l t sf o rg e n e r a lp l a n a rm a p s ，r e g u l a r 。p l a n a rm a p s ，e u l e r i a np l a n a rm a p s ，s e l f d u a lp l a n a rm a p sa n d2 - c o n n e c t e dp l a n a rm a p s ，e t c f o re x a m p l e ，t h e yo b t a i n e d t h en u m b e ro fu n r o o t e d2 - c o n n e c t e dp l a n a rm a p si s 丽1 b ，( n ) + 百1 咖毛。妒( 渺2 _ 9 t + 2 ) 刖( 州 w h e r e ，a ( n ) = 旦 b ( 坐2 丝、i f ni so d d o r 3 i n - 广4 b ( i n ) i fn e v e n 州= 怒若 a n d 妒( t ) i st h ee u l e rf u n c t i o n b i g g sa n dw h i t ep r e s e n t e d af c i r m u l af o re n u m e r a t i n gn o n e q u i v a l e n te m - b e d d i n g so no r i e n t a b l es u r f a c e sw i t hag i v e nu n d e r l y i n gg r a p h ，w h i c hh a sb e e n s u c c e s s f u l l yu s e df o rt h ec o m p l e t eg r a p h ，w h e e la n dc o m p l e t eb i p a r t i t eg r a p h b yd e t e r m i n i n gt h ef i xs e t 只j ( a ) f o re a c hv e r t e x a n da u t o m o r p h i s m o to f g r a p h i n ，【5 8 卜【5 a l t h o u g ht h i sf o r m u l a i sn o tv e r ye f f i c i e n ta n dn e e dm o r ec l a r i f y i n gf o rt h ea c t u a le n u m e r a t i o n t h es a m e i d e ni 8m o r e p r a c t i c a lf o re n u m e r a t i n g r o o t e dm a p so ns u r f a c e s ( o r i e n t a b l eo rn o n o r i e n t a b l e ) w i t hg i v e nu n d e r l y i n g g r a p h s ( s e ec h p a t e r4i nt h i st h e s i s ) s i n c ea n ye m b e d d i n go fa g r a p h o ns u r f a c ec a nb e u n i q u e l yi n d u c e db y a no r i e n t a b l ee m b e d d i n go ft h es s x n eg r a p h 2 s m s l a n db ye d m o n d s c o r r e s p o n d e n c e ” t h eo r i e n t a b l ee m b e d d i n g si so n et oo n ec o r r e s p o n d e n tw i t ht h er o t a t i o ns y s t e m o ft h i sg r a p h ，w ec a ni n v e s t g a t et h en u m b e ro fm a p so ns u r f a c e sw i t hag i v e n u n d e r l 3 ，i n gg r a p hb yc l a s s i f y i n ga l lr o t a t i o ns y s t e mu n d e rt h ea c t i o no fi t s a u t o m o r p h i s mg r o u p t h em o t i v a t i o no ft h i s t h e s i sj st of i n dh o wm a n yr o o t e do r u n r o o t e dm a p so ns u r f a c e sw i t hg i v e nu n d e r l y i n gg r a p h s ，w h i c hi sd i v i d e di n t o f i v ec h a p t e r s t h em a i nt o p i c sa n dr e s u l t si ne a c hc h a p t e ra r ea sf c i l l o w s ： a b s t r a c t c h a p t e rl d i s c u s s e st h ee m b e d d i n g sg e n e r a t e db yo r i e n t a b l ee m b e d d i n g s i t i sp r o v e dt h a tt w o e m b e d d i n g s a r ei s o m o r p h i ci f ，a n do n l yi f ，t h e i rt w oo r i e n t a b l e e m b e d d i n g si s o m o r p h i c t h i sc h a p t e ra l s op r e s e n t sas c h e m ef o re n u m e r a t i n g n o n e q u i v a l e n te m b e d d i n g sa n dm a p so ns u r f a c e ( o r i e n t a b l eo rn o n o r i e n t a b l e o rb o t h ) b yt h ec o n c e p to fs e m i a r ca u t o m o r p h i s mg r o u po fg r a p h f r o mt h i s s c h e m e ，w ec a nf i n dap r o g r a m m i n gf o re n u m e r a t i n gn o n e q u i v a l e n te m b e d d i n g s a n dm a p so ns u r f a c e sw i t hg i v e nu n d e r l y i n gg r a p ha n dr e a l i z et h er o l eo ft o p i c s i nt h ec h a p t e r2 c h a p t e r2c o n s i d e r sf o rag i v e ng r a p h ，w h i c hs e m i a r ca u t o m o r p h i s mo ft h i s g r a p h i sa na u t o m o r p h i s m o f e m b e d d i n g s o rm a p s ，w h i c hi st h e p r e - s t e pf o r e n 1 一 m e r a t i n gn o n e q u i v a l e n te m b e d d i n g sa n dm a p s o fag r a p ho ns u r f a c e s c o m p l e t e g r a p h s ，c a y l e yg r a p h s w i t ht h e i ra u t o m o r p h i s m b e i n gn ( a ) 日a n ds e m i r e g u l a r a c t i o ng r a p h sa r ed e t e r m i n e df o rt h i so b j e c t t h et o p i cd i s c u s s e di nt h i sc h a p t e r c a nb ea l s os e e na sa ni n d e p e n d e n tp r o b l e mf o rr e s e a r c h c h a p t e r 3e n u m e r a t e st h en o n e q u i v a l e n te m b e d d i n g so f g r a p h s o no r i e n t a b l e ， n o n o r i e n t a b l es u r f a c e so rg e n e r a ls u r f a c e sb a s e do nt h er e s u l t si nc h a p t e r2 c o r n - p l e t eg r a p h s ，c a y l e yg r a p h sw i t ht h e i ra u t o m o r p h i s mb e i n g 露( 6 1 ) xh a n ds e m i r e g u l a ra c t i o ng r a p h sa r ee n u m e r a t e d n o t i c et h a tt h en u m b e r o fu n r o o t e dm a p s a r ea l s oo b t a i n e df o rc o m p l e t eg r a p h sa n dc a y l e yg r a p h sw h o s ea u t o m o r p h i s m b e i n gn ( a ) 日av e r yi n t e r e s t i n gr e s u l ti n t h i sc h a p t e ri st h a tt h en u m b e r o fm a p so nt h em a x i m u mn o n o r i e n t a b l es u r f a c ew i t hag i v e nu n d e r l y i n gg r a p h e q u a l st ot h en u m b e ro fm a p so no r i e n t a b l es u r f a c e sw i t ht h es a m eu n d e r l y i n g g r a p h ，w h i c he n a b l e su st og e tt h e e n u m e r a t i v er e s u l t sf o rt h eo n ef a c em a p so n n o n o r i e n t a b l es u r f a c e s c h a p t e r4d i s c u s s e st h ee n u m e r a t i o no fr o o t e dm a p s o ns u r f a c e s ( o r i e n t a b l e o rn o n o r i e n t a b l e ) w i t hg i v e nu n d e r l y i n gg r a p h s u n l i k et h eu n r o o t e dc a 5 e ，t h e f o r m u l af o rt h en u m b e ro fr o o t e dm a p so ns u r f a c e sw i t hag i v e nu n d e r l y i n gg r a p h i s8 a m - f r e e ，w h i c hc a nb eu s e df o rf i n d i n gt h ee n u f u n c t l o no re q u a t i o no fr o o t e d m a p sw i t hg i y e nu n d e r l y i n gg r a p h s b yt h ec o n c e p to fs e m i a r ca u t o m o r p h i s m g r o u po fg r a p h ，ar e l a t i o nb e t w e e nt h er o o t e dm a pp o l y n o m i a lo ng e n u sw i t h ag i v e nu n d e r l y i n gg r a p ha n dt h eg e n u sd i s t r i b u t i o np o l y n o m i a lo fg r a p hi s e s t a b l i s h e d u s i n gt h i sr e l a t i o n ，t h er o o t e dm a p so ng e n u sw i t hu n d e r l y i n gg r a p h c l o s e d e n dl a d d e r na n db o u q u e tb na l ee n u m e r a t e d t h ee n u m e r a t i o no fr o o t e d o n ef a c em a p si sa l s od i s c u s s e di nt h i sc h a p t e r c h a p t e r5d i s c u s s e st h ee n u m e r a t i o np r o b l e m so fm a p s s o m ea r es t i l l c o n s i d e r e db yu s ，a n ds o m e ，w et h i n ki ti sv a l u ef o rt h ee n u m e r a t i o no fm a p s t h ee n u m e r a t i o np r o b l e mi sn e a r l yr e l a t e dt oe v e r yc o r n e ro fm a t h e m a t i c s ， t o p o l o g y , a l g e b r a ，a n a l y t i cm a t h e m a t i c s ，d e v e l o p m e n t s i ne a c hb r a n c ho f m a t h e m a t i c si sa l s oi m p o r t a n tf o rd e v e l o p i n gt h ee n u m e r a t i v et e c h n i q u e so fm a p s n o t i c i n gt h i s f a c t ，t h e 3 】一 4 1 ， 9 】一 i l l ，【2 0 】 a b s t r a c t r e a d e rw i l lr e a l i z et h er o l eo fr e s u l t si nt h er e f e r e n c e s 【2 2 】a n d 【8 6 一【9 3 i no u rw o r k s a c k n o w l e d g e m e n t b e f o r ec o m p l e t i n gt h i st h e s i s ，lm u s ts h o wt h a n k sf r o mm yh e a r tt om ya d v i s o rp r o f e s s o rl i uy a n p e iw h od i r e c t e dm ee n t e rt h ef i e i do ft o p o l o g i c a lg r a p h t h e o r yi n c l u d i n ge m e b d d i n g so fg r a p h sa n de n u m e r a t i o no fm a p so ns u r f a c e s w i t h o u th i sg u i d e n c e1w o u l dn o tk n o wt h ef r u i t f u lt h e o r yo ft o p o l o g i c a lg r a p h s i nt h ep a s tt h r e ey e a r s ，h eh a sn e v e rs t o p p e dt oe n c o u r a g em ep r o b i n gt h et h e - o r ya n dt e c h n i q u e so fe n u m e r a t i o n0 fe m b e d d i n g so fg r a p ha n dm a p s o n